题目描述
给定一个长度为 的序列,有
次询问。
每次询问一个区间内,"元素出现次数" 的第 大的 "出现次数"。
强制在线。
正解
如果可以离线,有一个经典的莫队 + 值域分块做法可以做到严格 。(而且常数很小
就直接暴力移动左右端点,移动端点的修改复杂度是 的,然后单次查询是
的。
考虑在线怎么用莫队做。
预处理一些 的桶和分块数组,然后查寻就从最近的
开始移动,查寻完后还原桶和分块数组。
其实可以预处理很多 的,但由于空间原因,最多就只能预处理
个。
然后一次询问就需要移动大约 3000 次,总的复杂度有 ,实现精细一点应该可以通过。
代码
#pragma GCC optimize("O2") #include <bits/stdc++.h> #define N 100005 using namespace std; const int B1 = 1000, B2 = 1400; int n, m, type; int a[N]; int L[600], R[600]; int rec[600][N], f[600][N], g[600][B1]; int bel[N], bl[105], br[105]; inline int read() { int x = 0; char ch = getchar(); while(!isdigit(ch)) ch = getchar(); while(isdigit(ch)) x = x * 10 + ch - '0', ch = getchar(); return x; } void getFunc(int l, int r, int *rec, int *f, int *g) { f[0] = n, g[0] = n; for(int i = l; i <= r; ++i) { --f[rec[a[i]]], --g[bel[rec[a[i]]]]; ++rec[a[i]]; ++f[rec[a[i]]], ++g[bel[rec[a[i]]]]; } } void move(int l, int r, int ll, int rr, int *rec, int *f, int *g) { register int *lp = a + l, *rp = a + r, c; while(l > ll) { --lp, --l, c = ++rec[*lp]; --f[c - 1], --g[bel[c - 1]]; ++f[c], ++g[bel[c]]; } while(r < rr) { ++rp, ++r, c = ++rec[*rp]; --f[c - 1], --g[bel[c - 1]]; ++f[c], ++g[bel[c]]; } while(l < ll) { c = rec[*lp]--, ++lp, ++l; --f[c], --g[bel[c]]; ++f[c - 1], ++g[bel[c - 1]]; } while(r > rr) { c = rec[*rp]--, --rp, --r; --f[c], --g[bel[c]]; ++f[c - 1], ++g[bel[c - 1]]; } } int getAns(int *f, int *g, int rem) { if(rem > n) return 0; for(int i = bel[n]; ~i; --i) { if(rem > g[i]) { rem -= g[i]; } else { for(int j = br[i]; j >= bl[i]; --j) { rem -= f[j]; if(rem <= 0) return j; } } } return -1; } int main() { n = read(), m = read(), type = read(); for(int i = 1; i <= n; ++i) a[i] = read(); for(int i = 0; i <= n; ++i) bel[i] = i / B1; for(int i = 0; i <= n; ++i) br[bel[i]] = i; for(int i = n; i >= 0; --i) bl[bel[i]] = i; int c = 0; f[0][0] = g[0][0] = n; for(int l = B2; l <= n; l += (B2 << 1)) for(int r = l + (B2 << 1); r <= n; r += (B2 << 1)) { if(r - l <= (B2 << 1)) continue; ++c, L[c] = l, R[c] = r; getFunc(l, r, rec[c], f[c], g[c]); } int ans = 0, cnt = 0, o; for(int Case = 1, l, r, k; Case <= m; ++Case) { l = read(), r = read(), k = read(); if(type & 1) l = l ^ ans, r = r ^ ans, k = k ^ ans; if(r - l <= (B2 << 1)) { ++cnt; move(l, l - 1, l, r, rec[0], f[0], g[0]); ans = getAns(f[0], g[0], k); move(l, r, l, l - 1, rec[0], f[0], g[0]); } else { o = 0; for(int i = 1; i <= c; ++i) if(!o || abs(l - L[i]) + abs(r - R[i]) < abs(l - L[o]) + abs(r - R[o])) o = i; move(L[o], R[o], l, r, rec[o], f[o], g[o]); ans = getAns(f[o], g[o], k); move(l, r, L[o], R[o], rec[o], f[o], g[o]); } printf("%d\n", ans); } return 0; }