3809: Gty的二逼妹子序列
Time Limit: 80 Sec Memory Limit: 28 MBSubmit: 1387 Solved: 400
[Submit][Status][Discuss]
Description
Autumn和Bakser又在研究Gty的妹子序列了！但他们遇到了一个难题。
对于一段妹子们，他们想让你帮忙求出这之内美丽度∈[a,b]的妹子的美丽度的种类数。
为了方便，我们规定妹子们的美丽度全都在[1,n]中。
给定一个长度为n(1<=n<=100000)的正整数序列s(1<=si<=n)，对于m(1<=m<=1000000)次询问“l,r,a,b”，每次输出sl...sr中，权值∈[a,b]的权值的种类数。
Input
第一行包括两个整数n,m(1<=n<=100000,1<=m<=1000000),表示数列s中的元素数和询问数。
第二行包括n个整数s1...sn(1<=si<=n)。
接下来m行,每行包括4个整数l,r,a,b(1<=l<=r<=n,1<=a<=b<=n),意义见题目描述。
保证涉及的所有数在C++的int内。
保证输入合法。
Output
对每个询问，单独输出一行，表示sl...sr中权值∈[a,b]的权值的种类数。
Sample Input
10 10
4 4 5 1 4 1 5 1 2 1
5 9 1 2
3 4 7 9
4 4 2 5
2 3 4 7
5 10 4 4
3 9 1 1
1 4 5 9
8 9 3 3
2 2 1 6
8 9 1 4
4 4 5 1 4 1 5 1 2 1
5 9 1 2
3 4 7 9
4 4 2 5
2 3 4 7
5 10 4 4
3 9 1 1
1 4 5 9
8 9 3 3
2 2 1 6
8 9 1 4
Sample Output
2
0
0
2
1
1
1
0
1
2
0
0
2
1
1
1
0
1
2
HINT
样例的部分解释：
5 9 1 2
子序列为4 1 5 1 2
在[1,2]里的权值有1,1,2，有2种，因此答案为2。
3 4 7 9
子序列为5 1
在[7,9]里的权值有5，有1种，因此答案为1。
4 4 2 5
子序列为1
没有权值在[2,5]中的，因此答案为0。
2 3 4 7
子序列为4 5
权值在[4,7]中的有4,5，因此答案为2。
建议使用输入/输出优化。
Source
初识莫队算法，大体记录一下。
莫队算法可以用来解决一类区间询问问题，例如一道经典的例题：
给出一个序列，还有若干次询问，每次询问在区间[l,r]中有多少个数字出现了3次及3次以上。
先考虑暴力算法，不难想到对于每个询问，扫描一遍区间，用数组记录下每个数字出现的次数并及时统计出现3次及以上的数字个数，时间复杂度O(询问数*区间大小)。
再考虑高级算法，就是维护一段区间内的数字出现次数以及3次及三次以上的数字个数，区间每次可以O(1)的向某个方向（左或右）扩展一个元素，或弹出一个元素，只需要修改该数字的出现次数，并检查是否发生了从3到2或从2到3的“质变”即可。这个算法相较于上一个暴力算法并没与在复杂度上体现出什么优势，但这是莫队算法的基础。
最后看莫队算法，采用类似于分块的sqrt(n)划分方式，先将所有询问离线，按照询问的区间左端点排序，每sqrt(n)个单位长度划分为一组，注意是按照长度。然后对于每一组询问，在组内对询问按照区间右端点排序，使其单调，然后暴力处理一个组内的所有询问即可。由于左端点相距至多sqrt(n)个长度，所有每次维护的区间的左端点最多进行sqrt(n)次改变（加入元素或删除元素），而区间的右端点由于单调性质至多移动n个单位长度，全局复杂度O(n*sqrt(n))，优秀之极。
对于这道题，一开始的想法是莫队算法+树状数组（或线段树）什么的，时间复杂度O(N*sqrt(N)*log(N))，然而亲身实践之后并没有卡过去，看来出题人没有那么友好。
考虑把树状数组的O(logN)加入和O(logN)查询做一些调整，用分块的O(1)插入和O(sqrt(N))查询替代，全局复杂度降至O(NsqrtN)。
1 #include <bits/stdc++.h> 2 3 template <class T> 4 inline void read(T &num) { 5 register int neg = false; 6 register int bit = getchar(); 7 8 while (bit <= '0') { 9 if (bit == '-') 10 neg ^= neg; 11 bit = getchar(); 12 } 13 14 num = 0; 15 16 while (bit >= '0') { 17 num = num*10 18 + bit - '0'; 19 bit = getchar(); 20 } 21 22 if (neg)num = -num; 23 } 24 25 const int N = 1e5 + 5; 26 const int M = 1e6 + 6; 27 28 int n, m, s, num[N], cnt[N], sgl[N], sum[N]; 29 30 /*<--- QRY --->*/ 31 32 struct query { 33 int l, r, a, b, id, ans; 34 }qry[M]; 35 36 inline bool cmp_lr(const query &A, const query &B) { 37 if (A.l / s != B.l / s) 38 return A.l < B.l; 39 else 40 return A.r < B.r; 41 } 42 43 inline bool cmp_id(const query &A, const query &B) { 44 return A.id < B.id; 45 } 46 47 /*<--- MO --->*/ 48 49 inline int ask(int a, int b) { 50 if (a / s == b / s) { 51 int ret = 0; 52 for (int i = a; i <= b; ++i)ret += sgl[i]; 53 return ret; 54 } 55 else { 56 int ret = 0, lt = a / s + 1, rt = b / s - 1; 57 for (int i = lt; i <= rt; ++i)ret += sum[i]; 58 for (int i = a; i / s < lt; ++i)ret += sgl[i]; 59 for (int i = b; i / s > rt; --i)ret += sgl[i]; 60 return ret; 61 } 62 } 63 64 inline void add(int k, int v) { 65 sgl[k] += v, sum[k/s] += v; 66 } 67 68 inline void insert(int k) { 69 if (++cnt[k] == 1)add(k, 1); 70 } 71 72 inline void remove(int k) { 73 if (--cnt[k] == 0)add(k, -1); 74 } 75 76 /*<--- MAIN --->*/ 77 78 signed main(void) { 79 read(n); 80 read(m); 81 82 s = sqrt(n); 83 84 for (int i = 1; i <= n; ++i) 85 read(num[i]); 86 87 for (int i = 1; i <= m; ++i) { 88 qry[i].id = i; 89 read(qry[i].l); 90 read(qry[i].r); 91 read(qry[i].a); 92 read(qry[i].b); 93 } 94 95 memset(cnt, 0, sizeof(cnt)); 96 memset(sum, 0, sizeof(sum)); 97 memset(sgl, 0, sizeof(sgl)); 98 99 std::sort(qry + 1, qry + 1 + m, cmp_lr); 100 101 for (int i = 1, x = 1, y = 0; i <= m; ++i) { 102 while (x < qry[i].l)remove(num[x]), ++x; 103 while (y > qry[i].r)remove(num[y]), --y; 104 while (x > qry[i].l)--x, insert(num[x]); 105 while (y < qry[i].r)++y, insert(num[y]); 106 qry[i].ans = ask(qry[i].a, qry[i].b); 107 } 108 109 std::sort(qry + 1, qry + 1 + m, cmp_id); 110 111 for (int i = 1; i <= m; ++i) 112 printf("%d ", qry[i].ans); 113 }
@Author: YouSiki