SurveillanceSystem

作者：聂恺辰 徐明宽

关键词：枚举 暴力 前缀和 莫队算法

题目简述

给一个长度为$N$的“X”“-”序列，X代表1这个位置有物品，每个摄像头可以看到一段长度为$L$的区间。

已知任意两个摄像头所监控的区间不完全重合，再给出每个摄像头能看到的物品数量，求序列中每个位置的状态

状态有三种，一定被摄像头监视到（+），可能被摄像头监视到（?），一定不被摄像头监视到（-）

数据范围

$N<=50$，数据保证合法

算法

我们可以先预处理出所有摄像头可能监控的区间里有多少物品，再处理出可见物品数相同的摄像头有多少个，然后把可见物品数相同的放在一起考虑

对于可见物品数相同摄像头和区间，我们可以计算出序列中的每个点在这些区间里出现过多少次。设摄像头的数量为$X$，某个点在这些区间里出现过$K$次，一共有$T$个这样的区间

则当$K+X>T$时，这个点一定被监控到

只要$X>0$，这个点就可能被监控到

所以只需要暴力扫一遍就可以统计答案了，$N$的范围很小，好像什么优化都不用加就可以过

优化

我们可以使用前缀和或莫队算法在$O(N)$的时间内预处理出所有摄像头可能监控的区间里有多少物品，再扫一遍处理出可见物品数相同的摄像头有多少个。下面来看如何快速计算每个位置的状态：

• 这个位置是否可能被监控到？

可以扫一遍处理出每个摄像头可能监控的区间是否可能有摄像头，得到一个长度为$N-L$的bool数组，这样每个点可能被监控到等价于这个bool数组的一段区间和大于0，可以使用前缀和或莫队算法在$O(N)$的时间求出。

• 这个位置是否一定被监控到？

设$K[i]$表示有多少个包含$i$个物品的区间包含这个位置，共有$X[i]$个包含$i$个物品的摄像头，一共有$T[i]$个这样的区间。使用莫队算法，记录一个变量表示有多少个$i$使得$K[i] + X[i] > T[i]$，只要这个变量不为$0$，这个位置就一定会被监控到。因为相邻两个位置的信息之间可以$O(1)$转移，所以时间复杂度为$O(N)$。

总时间复杂度为$O(N)$。