开坑...最近要把朱熹树写一下,就开个大坑来记录我的脑洞吧> <
区间不同数个数(静态)
给定一个序列,给出一些对于某个区间[l,r]的询问,求这个区间内不同数的个数.
输入
int seq[];
range<int,int> query;
#define input classof
int N,M;
fon(i,N) seq[i]; ' '
fon(i,M) query[i]; '
'
#define endinput endclassof
输出
int seq[];
#define output classof
fon(i,M) answerof(query[i]); '
'
#define endoutput endclassof
数据范围
- subtask1: N,M,seq[i] 1k
- subtask2: N,M 5k seq[i] 1G
- subtask3: N,M 100k seq[i] 1G
- subtask4: N,M 500k seq[i] 1G
限制
- 时限10s/1P
- 空间2048MiB
Subtask 1
10s跑N,M,NUMLIM 1k的区间不同数个数统计怎么也跑过了...
Subtask 2
其实这个时间长度跑(O(n^2))算法没有任何问题.
开个map来判重也可以吧...
还是荐hashmap.
Subtask 3
从这里开始需要一点脑子了.
将左端点按(sqrt{n})大小分块按块排序,块内按右端点排个序. 再处理就好了.
时间复杂度分析
块内右端点单调,显然(O(sqrt{n}))每次更新.
块间也不会超过(2sqrt{n}).
注
这种分块离线求值就是莫队算法(的改进版).
莫队算法可以处理非常多(离线)的题目.