游记也在题解中
Day-6【题解】
清风（breeze）
难度：Medium
一眼性质题，但是不想推了.jpg
本题作为一道趣题，放在了题目泛刷记录3
半夜（midnight）
论文题，稍后总结
考场上写了70分的做法，不过hash被卡了.jpg
鸣蝉（cicada）
一看空间限制，好么 (8 ext{MB})，这是给人做的？
题目本来是求区间内不同的数字个数，但是出题人说是一眼秒的题
确实
然后就改成了区间并的不同的数字的个数
还nm丧心病狂的强制在线
考虑使用数据结构
个锤子啊，空间限制只有 (8 ext{MB})
还是用 ( ext{Mo's Algorithm}) 吧
我想到可以分块，然后对于每个块维护一对指针，共计维护 (997) 对
然后成功闭着眼想出来了hack数据
接着我又想到区间可以容斥，然后发现并没有什么用
最后发现每个数出不出现可以表示为 (0/1)
写了一发bitset分块，然后顺便维护一个右指针
因为空间，卡了卡发现块长最少只能调到 (400) 这个样子，再高就会MLE
交上去了
中午有人说这是雅礼集训原题，然后在上面交了一发，TLE
然后把块长调到了 (150)，一发AC，空间占用 (2.5 ext{MB})
wdnmd明明不是这样的啊
下午出成绩这题果然挂到 (20) 了，块长一调就 (100) 了
这题的话大力分块，对于每个块维护一个bitset
对于整块直接用ans与其或，散块暴力set
之后处理区间重叠问题，这题就做完了
#include<bits/stdc++.h>
#define fx(l,n) inline l n
using std::cin;
using std::cout;
using std::bitset;
const int N=100100,len=1097;
fx(int,gi)(){
char c=getchar();int s=0,f=1;
while(c>'9'||c<'0'){
if(c=='-') f=-f;
c=getchar();
}
while(c<='9'&&c>='0') s=(s<<3)+(s<<1)+(c-'0'),c=getchar();
return s*f;
}
int n,m,p,d[N],bel[N],l[N],r[N],las,mr,cnt;
struct query{
int l,r;
fx(bool,operator) < (const query &b) const{
return l==b.l?r<b.r:l<b.l;
}
}q[N];
bitset<N>blo[len],ans;
fx(void,solve)(int ql,int qr){
int i;
if(bel[qr]-bel[ql]>=2){
for(i=bel[ql]+1;i<=bel[qr]-1;i++) ans|=blo[i];
for(i=ql;i<=r[bel[ql]];i++) ans.set(d[i],1);
for(i=l[bel[qr]];i<=qr;i++) ans.set(d[i],1);
} else if(bel[qr]-bel[ql]==1&&qr==r[bel[qr]]){
ans|=blo[bel[qr]];
for(i=ql;i<=r[bel[ql]];i++) ans.set(d[i],1);
} else if(bel[qr]-bel[ql]==1&&ql==l[bel[ql]]){
ans|=blo[bel[ql]];
for(i=l[bel[qr]];i<=qr;i++) ans.set(d[i],1);
} else for(i=ql;i<=qr;i++) ans.set(d[i],1);
}
signed main(){
n=gi(),m=gi(),p=gi();
int i,o,tms,now;
for(i=1;i<=n;i++) d[i]=gi();
for(i=1,tms=1;i<=n;i+=len,tms++){
l[tms]=i,r[tms]=(i+len-1>n?n:i+len-1);
for(o=l[tms];o<=r[tms];o++){
bel[o]=tms;
blo[tms].set(d[o],1);
}
}
for(now=1;now<=m;now++){
ans&=0;
cnt=gi();mr=0;
for(i=1;i<=cnt;i++){
q[i].l=gi(),q[i].r=gi();
if(p&&now!=1){
q[i].l=(q[i].l^las)%n+1;
q[i].r=(q[i].r^las)%n+1;
if(q[i].l>q[i].r) std::swap(q[i].l,q[i].r);
}
}
std::sort(q+1,q+cnt+1);
for(i=1;i<=cnt;i++){
if(q[i].r<=mr) continue;
else q[i].l=(q[i].l>mr+1?q[i].l:mr+1),mr=q[i].r;
solve(q[i].l,q[i].r);
}
printf("%d
",las=ans.count());
}
return 0;
}