(solution)
- (8 MB?),还强制在线(?)若干个区间并(?)
- 看着极其不可做,没有任何数据结构能维护,考虑用(bitset)优化暴力(以下(w = 64)指(bitset)除掉的常数)
- 考虑分块(bitset),设块大小为(S),则块有(frac{n}{S})个,考虑朴素的时间复杂度单询问就是(O(q * frac{n}{w} * frac{n}{s} + q * S)),考虑做一些预处理
- 对于这种分块,我们的优化一般有两种手段线段树或者ST表,考虑这题是静态问题,且区间并不要求不交,考虑(ST)表
- 那么时间复杂度变为(O(q * (frac{n}{w} + S) + frac{n^2}{Sw}*log(frac{n}{S}))),空间复杂度为(O(frac{n^2}{Sw}*log(frac{n}{S})))
- 因为这题空间卡的很死,我们必须考虑不追求时间最优而用非常规大小分块,此处取(S = frac{n}{w}),那么时间复杂度就是(O(frac{nq}{w} + nlog w)),空间复杂度为(O(nlog w))
- 代码先咕咕
- 本题卡常
/*雅礼集训2018 颜色*/
#include<bits/stdc++.h>
using namespace std;
int read(){
char c = getchar();
int x = 0;
while(c < '0' || c > '9') c = getchar();
while(c >= '0' && c <= '9') x = x * 10 + c - 48,c = getchar();
return x;
}
const int _ = 1e5 + 7;
int n,m,p;
int a[_];int L[69],R[69];
int b[_];
bitset<_>o[69][7],Ans;int lg2[69];
int S,t;
void solve(int l,int r){
// cout<<b[l]<<' '<<b[r]<<endl;
if(b[l] == b[r]){
for(int i = l; i <= r; ++i) Ans.set(a[i]);
return;
}
// cout<<l<<' '<<r<<' '<<b[l]<<' '<<b[r]<<"!!"<<endl;
for(int i = l; i <= R[b[l]]; ++i) Ans.set(a[i]);
for(int i = L[b[r]]; i <= r; ++i) Ans.set(a[i]);
l = b[l] + 1,r = b[r] - 1;
if(l <= r){
int k = lg2[r-l+1];
// assert(k <= 6);
// assert(k >= 0);
Ans |= o[l][k];Ans |= o[r-(1<<k)+1][k];
}
}
int main(){
// freopen("color.in","r",stdin);
// freopen("color.out","w",stdout);
n = read(),m = read(),p = read();
for(int i = 1; i <= n; ++i) a[i] = read();
for(int i = 2; i <= 65; ++i) lg2[i] = lg2[i>>1] + 1;
int ans = 0;
if(n < 64){
for(int T = 1; T <= m; ++T){
int k = read();
Ans.reset();
while(k--){
int l = read(),r = read();
if(p && T != 1){
l = (l ^ ans) % n + 1;
r = (r ^ ans) % n + 1;
}
// cout<<l<<' '<<r<<endl;
for(int i = l; i <= r; ++i) Ans.set(a[i]);
}
ans = Ans.count();
printf("%d
",ans);
}
return 0;
}
S = n / 64;t = 0;
for(int i = 1; i <= 64; ++i){
++t;
L[t] = R[t-1] + 1;
R[t] = L[t] + S - 1;
}
if(R[t] != n){
++t;L[t] = R[t-1] + 1;
R[t] = n;
}
// cout<<t<<' '<<S<<endl;
for(int i = 1; i <= t; ++i){
for(int j = L[i]; j <= R[i]; ++j){
o[i][0].set(a[j]),b[j] = i;
}
}
for(int j = 1; j <= 6; ++j)
for(int i = 1; i + (1 << j) - 1 <= t; ++i)
o[i][j] = o[i][j-1] | o[i+(1<<(j-1))][j-1];
// int ans = 0;
for(int T = 1; T <= m; ++T){
int k = read();
Ans.reset();
while(k--){
int l = read(),r = read();
if(p && T != 1){
l = (l ^ ans) % n + 1;
r = (r ^ ans) % n + 1;
}
if(l > r) swap(l,r);
solve(l,r);
}
ans = Ans.count();
printf("%d
",ans);
}
return 0;
}