[Ynoi2016]镜中的昆虫

柔情只为你懂 2022-01-06 16:04 146阅读 0赞

[https://www.luogu.org/problemnew/show/P4690][https_www.luogu.org_problemnew_show_P4690]

### 题解 ###

区间不用种类的数的个数。

这个问题可以转化为对每个点维护一个\\(pre\\),询问\\(l \\sim r\\)中，有多少个位置是在\\(0\\sim l-1\\)之间的。

这个问题可以用二维偏序做。

然后对于区间赋值的操作，可以证明，如果我们找到所有有变化的位置并且把它改掉，它的总更改次数为\\(O(n+m)\\)级别的。

那具体实现可以用\\(set\\)维护区间，注意新加入一个区间时其他区间可能是被这个区间包含，包含这个区间，和这个区间有交，讨论比较麻烦。。

### 代码 ###

#include<bits/stdc++.h> #define N 100009 #define ls tr[cnt].l #define rs tr[cnt].r using namespace std; typedef long long ll; int a[N],n,m,pre[N],now[N<<1],b[N<<1],rot[N]; inline ll rd(){ ll x=0;char c=getchar();bool f=0; while(!isdigit(c)){if(c=='-')f=1;c=getchar();} while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();} return f?-x:x; } struct node{ int opt,l,r,x; }c[N]; struct setnode{ int l,r,col; inline bool operator <(const setnode &b)const{ return l<b.l; } }; set<setnode>s,col[N<<1]; struct seg{ struct ment{ int l,r,val; }tr[N*200]; int tott; inline void upd(int &cnt,int l,int r,int x,int y){ if(!cnt)cnt=++tott; tr[cnt].val+=y; if(l==r)return; int mid=(l+r)>>1; if(mid>=x)upd(ls,l,mid,x,y); else upd(rs,mid+1,r,x,y); } inline int query(int cnt,int l,int r,int R){ if(r<=R)return tr[cnt].val; int mid=(l+r)>>1,ans=0; if(mid<R)ans+=query(rs,mid+1,r,R); ans+=query(ls,l,mid,R); return ans; } }T; struct BIT{ inline void add(int x,int y,int z){ while(x<=n)T.upd(rot[x],0,n,y,z),x+=x&-x; } inline int query(int x,int num){ int ans=0; while(x)ans+=T.query(rot[x],0,n,num),x-=x&-x; return ans; } inline int calc(int l,int r){ // cout<<query(r,l-1)<<" "; return query(r,l-1)-l+1; } }bit; inline void gg(int x,int y){ if(pre[x]==y)return; bit.add(x,pre[x],-1); pre[x]=y; bit.add(x,pre[x],1); } int main(){ n=rd();m=rd(); for(int i=1;i<=n;++i)a[i]=rd(),b[++b[0]]=a[i]; for(int i=1;i<=m;++i){ c[i].opt=rd(); c[i].l=rd(); c[i].r=rd(); if(c[i].opt==1)c[i].x=rd(),b[++b[0]]=c[i].x; } sort(b+1,b+b[0]+1); b[0]=unique(b+1,b+b[0]+1)-b-1; for(int i=1;i<=n;++i){ a[i]=lower_bound(b+1,b+b[0]+1,a[i])-b; pre[i]=now[a[i]]; now[a[i]]=i; s.insert(setnode{i,i,a[i]});col[a[i]].insert(setnode{i,i,a[i]}); bit.add(i,pre[i],1); } for(int i=1;i<=m;++i){ if(c[i].opt==1){ int l=c[i].l,r=c[i].r,x=c[i].x; x=lower_bound(b+1,b+b[0]+1,x)-b; int tg=0,tg2=0; set<setnode>::iterator it; while(1){ it=s.lower_bound(setnode{l,r,x}); if(it==s.end())break; if(it->l>r)break; if(it->r<=r){ int lss=it->l,rss=it->r,co=it->col; if(lss>l)gg(lss,lss-1); s.erase(it);col[co].erase(setnode{lss,rss,co}); it=col[co].lower_bound(setnode{rss,rss,co}); if(it!=col[co].end()){ int xx=it->l; if(it!=col[co].begin()){ --it; gg(xx,it->r); } else gg(xx,0); } } else{ int lss=it->l,rss=it->r,co=it->col; if(lss>l)gg(lss,lss-1); s.erase(it);col[co].erase(setnode{lss,rss,co}); tg=r+1;tg2=co; s.insert(setnode{r+1,rss,co});col[co].insert(setnode{r+1,rss,co}); break; } } it=s.lower_bound(setnode{l,r,x}); if(it!=s.begin()){ --it; if(it->r>r){ int lss=it->l,rss=it->r,co=it->col; s.erase(it);col[co].erase(setnode{lss,rss,co}); gg(r+1,l-1); s.insert(setnode{lss,l-1,co});s.insert(setnode{r+1,rss,co}); col[co].insert(setnode{lss,l-1,co});col[co].insert(setnode{r+1,rss,co}); } else if(it->r>=l){ int lss=it->l,rss=it->r,co=it->col; s.erase(it);col[co].erase(setnode{lss,rss,co}); it=col[co].lower_bound(setnode{rss,rss,co}); if(it!=col[co].end()){ gg(it->l,l-1); } s.insert(setnode{lss,l-1,co});col[co].insert(setnode{lss,l-1,co}); } } s.insert(setnode{l,r,x});col[x].insert(setnode{l,r,x}); if(tg){ it=col[tg2].lower_bound(setnode{r+1,r+1,tg2}); if(it!=col[tg2].begin()){ it--; gg(tg,it->r); } else gg(tg,0); } it=col[x].lower_bound(setnode{l,r,x}); if(it!=col[x].begin()){ --it; gg(l,it->r); it++; } else gg(l,0); it++; if(it!=col[x].end()){ gg(it->l,r); } } else{ printf("%d\n",bit.calc(c[i].l,c[i].r)); } } return 0; }

转载于:https://www.cnblogs.com/ZH-comld/p/10932390.html

[https_www.luogu.org_problemnew_show_P4690]: https://www.luogu.org/problemnew/show/P4690