# 题解 [牛客练习赛62 F] 牛牛的繁星

https://ac.nowcoder.com/acm/contest/5205/F

### 代码

```#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];

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() {
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) {
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;
}```

1 收藏 评论