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的情况。
主席树代码：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
using namespace std; typedef long long ll; #define N 100050
const int INF = << ;
const double pi = acos(-); int pt;
int a[N], b[N], root[N], lc[N * ], rc[N * ], cnt[N * ];
vector<int> lis[N]; int Add(int y, int l, int r, int v)
{
int x = ++pt;
cnt[x] = cnt[y] + ;
if (l < r)
{
int mid = (l + r) >> ;
if (v <= mid)
{
rc[x] = rc[y];
lc[x] = Add(lc[y], l, mid, v);
}
else
{
lc[x] = lc[y];
rc[x] = Add(rc[y], mid + , r, v);
}
}
return x;
} int Query(int x, int y, int L, int R, int l, int r)
{
//cout << L <<" " << R << " " << cnt[x] << " " << cnt[y] << endl;
if (l > R || r < L) return ;
if (l <= L && r >= R) return cnt[x] - cnt[y]; int Mid = (L + R) >> ;
return Query(lc[x], lc[y], L, Mid, l, r) + Query(rc[x], rc[y], Mid + , R, l, r);
} int main()
{
//freopen("in.in", "r", stdin);
//freopen("out.out", "w", stdout); int n, k, Q, lastans = , l, r;
scanf("%d %d", &n, &k);
for (int i = ; i <= n; ++i) scanf("%d", &a[i]), lis[a[i]].push_back(i); for (int i = ; i <= ; ++i)
{
if (lis[i].size() <= k) continue;
for (int j = k; j < lis[i].size(); ++j) b[lis[i][j]] = lis[i][j - k];
} root[] = ++pt;
for (int i = ; i <= n; ++i) root[i] = Add(root[i - ], , n, b[i]); scanf("%d", &Q);
while (Q--)
{
scanf("%d %d", &l, &r);
l = (l + lastans) % n + ;
r = (r + lastans) % n + ;
if (l > r) swap(l, r);
lastans = Query(root[r], root[l - ], , n, , l - );
printf("%d\n", lastans);
} return ;
}
分块代码：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
using namespace std; typedef long long ll; #define N 100050
const int INF = << ;
const double pi = acos(-); int pt;
int a[N], b[N], id[N], dp[][N];
int bl[], br[];
vector<int> lis[N]; int main()
{
//freopen("in.in", "r", stdin);
//freopen("out.out", "w", stdout); int n, k, Q, lastans = , l, r;
scanf("%d %d", &n, &k);
for (int i = ; i <= n; ++i) scanf("%d", &a[i]), lis[a[i]].push_back(i); for (int i = ; i <= ; ++i)
{
if (lis[i].size() <= k) continue;
for (int j = k; j < lis[i].size(); ++j) b[lis[i][j]] = lis[i][j - k];
} int block = (int)sqrt(n + ); for (int i = ; ; ++i)
{
l = (i - ) * block + ;
r = min(n, l + block - );
bl[i] = l, br[i] = r;
for (int j = l; j <= r; ++j) dp[i][b[j]]++, id[j] = i;
for (int j = ; j <= ; ++j) dp[i][j] += dp[i][j - ];
if (r == n) break;
} scanf("%d", &Q);
while (Q--)
{
scanf("%d %d", &l, &r);
l = (l + lastans) % n + ;
r = (r + lastans) % n + ;
if (l > r) swap(l, r); int res = ;
if (id[l] == id[r])
{
for (int i = l; i <= r; ++i)
res += b[i] < l;
}
else
{
for (int i = l; i <= br[id[l]]; ++i) res += b[i] < l;
for (int i = bl[id[r]]; i <= r; ++i) res += b[i] < l;
for (int i = id[l] + ; i <= id[r] - ; ++i) res += dp[i][l - ];
}
printf("%d\n", res);
lastans = res;
} return ;
}