http://codeforces.com/contest/813/problem/E
题目大意：
给出长度为n的数组和k, 大小是1e5级别。
要求在线询问区间[l, r]权值, 权值定义为对于所有不同元素x在区间出现的次数和, 如果x出现次数>k, 那么按k算。
重要转换： 考虑一个区间[L, R]的某个数A[i], 它对答案有贡献 当且仅当 它前面与他权值相同的数中第k个数的位置(记为B[i]) < L
预处理B[], 每次询问就转化为 区间[L, R]中有多少个B[i] < L
可以用主席树 或者 分块解决。
也可以用此题的方法求区间不同元素个数, 其实就是k = 1的情况。
主席树代码：
1 #include <cstdio>
2 #include <cstring>
3 #include <iostream>
4 #include <cmath>
5 #include <algorithm>
6 #include <vector>
7 #include <map>
8 #include <queue>
9 using namespace std;
10
11 typedef long long ll;
12
13 #define N 100050
14 const int INF = 1 << 30;
15 const double pi = acos(-1);
16
17 int pt;
18 int a[N], b[N], root[N], lc[N * 60], rc[N * 60], cnt[N * 60];
19 vector<int> lis[N];
20
21 int Add(int y, int l, int r, int v)
22 {
23 int x = ++pt;
24 cnt[x] = cnt[y] + 1;
25 if (l < r)
26 {
27 int mid = (l + r) >> 1;
28 if (v <= mid)
29 {
30 rc[x] = rc[y];
31 lc[x] = Add(lc[y], l, mid, v);
32 }
33 else
34 {
35 lc[x] = lc[y];
36 rc[x] = Add(rc[y], mid + 1, r, v);
37 }
38 }
39 return x;
40 }
41
42 int Query(int x, int y, int L, int R, int l, int r)
43 {
44 //cout << L <<" " << R << " " << cnt[x] << " " << cnt[y] << endl;
45 if (l > R || r < L) return 0;
46 if (l <= L && r >= R) return cnt[x] - cnt[y];
47
48 int Mid = (L + R) >> 1;
49 return Query(lc[x], lc[y], L, Mid, l, r) + Query(rc[x], rc[y], Mid + 1, R, l, r);
50 }
51
52 int main()
53 {
54 //freopen("in.in", "r", stdin);
55 //freopen("out.out", "w", stdout);
56
57 int n, k, Q, lastans = 0, l, r;
58 scanf("%d %d", &n, &k);
59 for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), lis[a[i]].push_back(i);
60
61 for (int i = 1; i <= 100000; ++i)
62 {
63 if (lis[i].size() <= k) continue;
64 for (int j = k; j < lis[i].size(); ++j) b[lis[i][j]] = lis[i][j - k];
65 }
66
67 root[0] = ++pt;
68 for (int i = 1; i <= n; ++i) root[i] = Add(root[i - 1], 0, n, b[i]);
69
70
71 scanf("%d", &Q);
72 while (Q--)
73 {
74 scanf("%d %d", &l, &r);
75 l = (l + lastans) % n + 1;
76 r = (r + lastans) % n + 1;
77 if (l > r) swap(l, r);
78 lastans = Query(root[r], root[l - 1], 0, n, 0, l - 1);
79 printf("%d
", lastans);
80 }
81
82 return 0;
83 }
分块代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <cmath> 5 #include <algorithm> 6 #include <vector> 7 #include <map> 8 #include <queue> 9 using namespace std; 10 11 typedef long long ll; 12 13 #define N 100050 14 const int INF = 1 << 30; 15 const double pi = acos(-1); 16 17 int pt; 18 int a[N], b[N], id[N], dp[350][N]; 19 int bl[350], br[350]; 20 vector<int> lis[N]; 21 22 int main() 23 { 24 //freopen("in.in", "r", stdin); 25 //freopen("out.out", "w", stdout); 26 27 int n, k, Q, lastans = 0, l, r; 28 scanf("%d %d", &n, &k); 29 for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), lis[a[i]].push_back(i); 30 31 for (int i = 1; i <= 100000; ++i) 32 { 33 if (lis[i].size() <= k) continue; 34 for (int j = k; j < lis[i].size(); ++j) b[lis[i][j]] = lis[i][j - k]; 35 } 36 37 int block = (int)sqrt(n + 1); 38 39 for (int i = 1; ; ++i) 40 { 41 l = (i - 1) * block + 1; 42 r = min(n, l + block - 1); 43 bl[i] = l, br[i] = r; 44 for (int j = l; j <= r; ++j) dp[i][b[j]]++, id[j] = i; 45 for (int j = 1; j <= 100000; ++j) dp[i][j] += dp[i][j - 1]; 46 if (r == n) break; 47 } 48 49 scanf("%d", &Q); 50 while (Q--) 51 { 52 scanf("%d %d", &l, &r); 53 l = (l + lastans) % n + 1; 54 r = (r + lastans) % n + 1; 55 if (l > r) swap(l, r); 56 57 int res = 0; 58 if (id[l] == id[r]) 59 { 60 for (int i = l; i <= r; ++i) 61 res += b[i] < l; 62 } 63 else 64 { 65 for (int i = l; i <= br[id[l]]; ++i) res += b[i] < l; 66 for (int i = bl[id[r]]; i <= r; ++i) res += b[i] < l; 67 for (int i = id[l] + 1; i <= id[r] - 1; ++i) res += dp[i][l - 1]; 68 } 69 printf("%d ", res); 70 lastans = res; 71 } 72 73 return 0; 74 }