BZOJ上内存小了会WA。。。。
线段树上挂链表。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 200500 using namespace std; int n,m,a[maxn],x,y,now,root,d[maxn],ans=0,q,r; int ls[maxn<<2],rs[maxn<<2],g[maxn*20],nxt[maxn*20],go[maxn*20],sum[maxn<<2],cnt=0,tot=0; void build(int &now,int left,int right) { now=++tot; if (left==right) { sum[now]=1; return; } int mid=(left+right)>>1; build(ls[now],left,mid); build(rs[now],mid+1,right); sum[now]=sum[ls[now]]+sum[rs[now]]; } void modify(int now,int left,int right,int l,int r,int num) { if ((left==l) && (right==r)) { d[num]++; go[++cnt]=num; nxt[cnt]=g[now]; g[now]=cnt; return; } int mid=(left+right)>>1; if (r<=mid) modify(ls[now],left,mid,l,r,num); else if (l>=mid+1) modify(rs[now],mid+1,right,l,r,num); else { modify(ls[now],left,mid,l,mid,num); modify(rs[now],mid+1,right,mid+1,r,num); } } void change(int now,int left,int right,int pos) { sum[now]--; if (!sum[now]) { int t=g[now]; while (t) { d[go[t]]--; if (!d[go[t]]) ans++; t=nxt[t]; } } if (left==right) return; int mid=(left+right)>>1; if (pos<=mid) change(ls[now],left,mid,pos); else change(rs[now],mid+1,right,pos); } int main() { memset(d,0,sizeof(d)); memset(g,0,sizeof(g)); scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) scanf("%d",&a[i]); build(root,1,n); for (int i=1;i<=m;i++) { scanf("%d%d",&x,&y); modify(root,1,n,x,y,i); } scanf("%d",&q); for (int i=1;i<=q;i++) { scanf("%d",&r); r=(r+ans-1)%n+1; a[r]--; if (!a[r]) change(root,1,n,r); printf("%d ",ans); } return 0; }