题目链接 Educational Codeforces Round 22 Problem E
题意 给定一个序列，$q$次查询，询问从$l$到$r$中出现过的数字的出现次数和$k$取较小值后的和
设$f(i, 1)$表示满足$a_{j} = a_{i}$并且$j < i$的$j$的最大值，若不存在这样的$j$则$f(i, 1) = -1$
设$f(i, j) = f(f(i, j - 1), 1), j >= 2$。
那么我们要做的就是对于每一次查询，找到$[l, r]$中，满足$l <= i <= r$且$f(i, k) < l$的$i$的个数。
对于$f(i, k)$，$O(n)$预处理，
查询在主席树上操作就可以了。
因此总时间复杂度$O(nlogn)$
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i) #define dec(i, a, b) for (int i(a); i >= (b); --i) const int N = 1e5 + 10; const int M = 3e6 + 10; int n, k, q; int a[N], c[N]; int root[N], ls[M], rs[M], s[M]; int tot = 0, ans = 0; vector <int> v[N]; void update(int &x, int y, int l, int r, int pos){ x = ++tot; ls[x] = ls[y]; rs[x] = rs[y]; s[x] = s[y] + 1; if (l == r) return; int mid = (l + r) >> 1; if (pos <= mid) update(ls[x], ls[y], l, mid, pos); else update(rs[x], rs[y], mid + 1, r, pos); } int query(int x, int y, int L, int R, int l, int r){ if (l <= L && R <= r) return s[y] - s[x]; int ret = 0; int mid = (L + R) >> 1; if (l <= mid) ret += query(ls[x], ls[y], L, mid, l, r); if (r > mid) ret += query(rs[x], rs[y], mid + 1, R, l, r); return ret; } int main(){ scanf("%d%d", &n, &k); rep(i, 1, n){ scanf("%d", a + i); v[a[i]].push_back(i); } memset(c, -1, sizeof c); rep(i, 1, 1e5){ int et = v[i].size(); rep(j, k, et - 1) c[v[i][j]] = v[i][j - k]; } rep(i, 1, n){ if (c[i] == -1) root[i] = root[i - 1]; else update(root[i], root[i - 1], 1, n, c[i]); } scanf("%d", &q); while (q--){ int x, y; scanf("%d%d", &x, &y); x = (x + ans) % n + 1; y = (y + ans) % n + 1; if (x > y) swap(x, y); printf("%d\n", ans = y - x + 1 - query(root[x - 1], root[y], 1, n, x, y)); } return 0; }
转载于:https://www.cnblogs.com/cxhscst2/p/8620864.html
相关资源：各显卡算力对照表！