离线莫队算法
预处理出每个位置i 前一个和这个颜色相同的位置pre[i]和下一个颜色相同的位置nxt[i]
莫队转移的时候看一下区间里面还有没有这个颜色就可以转移了
最后统计的时候我用了一个分块- -其实不用也可以的,或者用了分块可以不用预处理上面的东西,分块记录和然后颜色减到0的时候该块的和减1就可以了
#include <cstdio> #include <algorithm> #include <cmath> using namespace std; const int N=50010; struct ask{int l,r,id;}q[200010]; int pre[N],nxt[N],n,c[N],tmp[1000010],sqrn,sqrc=1010,bit[2000],ans[200010],l,r,m,mx; bool cmp(ask a,ask b){return a.l/sqrn==b.l/sqrn?a.r<b.r:a.l/sqrn<b.l/sqrn;} void read(int &x){ char c; while((c=getchar())<'0' || c>'9');x=c-'0'; while((c=getchar())>='0' && c<='9') x=x*10+c-'0'; } int main(){ //freopen("1878.in","r",stdin);freopen("1878.out","w",stdout); read(n);sqrn=(int)sqrt(n); for(int i=1;i<=n;i++) read(c[i]),mx=max(c[i]+10,mx);sqrc=(int)sqrt(mx); read(m); for(int i=1;i<=m;i++) read(q[i].l),read(q[i].r),q[i].id=i; for(int i=1;i<=n;i++) pre[i]=tmp[c[i]],tmp[c[i]]=i; for(int i=0;i<=1000000;i++) tmp[i]=50010; for(int i=n;i>=1;i--) nxt[i]=tmp[c[i]],tmp[c[i]]=i;//预处理pre和nxt sort(q+1,q+m+1,cmp);l=r=1;bit[c[1]/sqrc]=1; for(int i=1;i<=m;i++){ int ret=0; for(;l<q[i].l;l++) if(nxt[l]>r) bit[c[l]/sqrc]--; for(;l>q[i].l;l--) if(nxt[l-1]>r) bit[c[l-1]/sqrc]++; for(;r<q[i].r;r++) if(pre[r+1]<l) bit[c[r+1]/sqrc]++; for(;r>q[i].r;r--) if(pre[r]<l) bit[c[r]/sqrc]--; for(int j=0;j<sqrc+10;j++) ret+=bit[j]; ans[q[i].id]=ret; } for(int i=1;i<=m;i++) printf("%d\n",ans[i]); return 0; }
学了一下整体二分,就拿这题练练手- -
线段树标记下传的时候把+=写成了=调了N久也是醉
#include <cstdio> #include <algorithm> using namespace std; const int N=50010,INF=~0u>>1; struct ask{int op,cur,ans,tmp,l,r,c,id;}qs[N],q[N*4],q1[N*4],q2[N*4]; int T[N*4],tag[N*4],L[N*4],R[N*4],ans[N*4],n,m; typedef long long LL; void up(int x){T[x]=T[x<<1]+T[x<<1|1];} void down(int x){ if(tag[x]){ T[x<<1]+=(R[x<<1]-L[x<<1]+1)*tag[x];tag[x<<1]+=tag[x]; T[x<<1|1]+=(R[x<<1|1]-L[x<<1|1]+1)*tag[x];tag[x<<1|1]+=tag[x]; tag[x]=0; } } void build(int x,int l,int r){ L[x]=l;R[x]=r; if(l==r){T[x]=0;return;} int mid=(l+r)>>1; build(x<<1,l,mid);build(x<<1|1,mid+1,r); up(x); } void change(int x,int l,int r,int d){ if(l<=L[x] && R[x]<=r) {tag[x]+=d;T[x]+=d*(R[x]-L[x]+1);return;} int mid=(L[x]+R[x])>>1; down(x); if(mid>=l) change(x<<1,l,r,d); if(mid<r) change(x<<1|1,l,r,d); up(x); } int query(int x,int l,int r){ if(l<=L[x] && R[x]<=r) {return T[x];} int mid=(L[x]+R[x])>>1,ret=0; down(x); if(mid>=l) ret+=query(x<<1,l,r); if(mid<r) ret+=query(x<<1|1,l,r); return ret; } void solve(int s,int t,LL l,LL r){ if(s>t) return ; if(l==r) {for(int i=s;i<=t;i++) if(q[i].op==2) ans[q[i].id]=l;return;} int mid=(l+r)>>1,t1=0,t2=0; for(int i=s;i<=t;i++){ if(q[i].op==1 && q[i].c>mid) change(1,q[i].l,q[i].r,1); if(q[i].op==2)q[i].tmp=query(1,q[i].l,q[i].r); } for(int i=s;i<=t;i++) if(q[i].op==1 && q[i].c>mid) change(1,q[i].l,q[i].r,-1); for(int i=s;i<=t;i++) if(q[i].op==2){ if(q[i].cur+q[i].tmp>=q[i].c) q1[++t1]=q[i]; else q[i].cur+=q[i].tmp,q2[++t2]=q[i]; }else{ if(q[i].c>mid) q1[++t1]=q[i];else q2[++t2]=q[i]; } for(int i=1;i<=t1;i++) q[s+i-1]=q1[i]; for(int i=1;i<=t2;i++) q[s+t1+i-1]=q2[i]; solve(s,s+t1-1,mid+1,r); solve(s+t1,t,l,mid); } int main(){ //freopen("3110.in","r",stdin);freopen("3110.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) scanf("%d%d%d%d",&qs[i].op,&qs[i].l,&qs[i].r,&qs[i].c),qs[i].id=i,q[i]=qs[i]; build(1,1,n); solve(1,m,-INF,INF); for(int i=1;i<=m;i++) if(qs[i].op==2)printf("%d\n",ans[i]==INF?0:ans[i]); return 0; }
在此感谢一下Claris教我这个方法,而我当时居然没看到……
CA爷说得好:学长给你讲啥你要好好听..就算听完不会也得问问..
设delta[i]=a[i]-a[i-1] 即delta[i]为delta的增量 则$a[i]=\sum_{k=1}^{i}delta[k]$
修改的时候 (令[s,t]+c) 就很显然了 delta[s]+=c,delta[t+1]-=c;
比较麻烦的是求和
我们要求区间(1,t)的和 $\sum_{k=1}^{t}a[i]=\sum_{k=1}(t-k+1)delta[k]=(t+1)\sum_{k=1}^{t}delta[k]-(\sum_{k=1}^{t}k*delta[k])$
在这里我们只要快速计算出delta[k]的前缀和 以及 k*delta[k]的前缀和即可 用两个树状数组维护这两个值就好了
至此 我们可以用两个树状数组动态维护数组的区间加减 和 求区间和了
代码的话以后等我写了再补
离散化+树状数组统计
看到这题第一个反应二维树状数组 看数据范围 这画风不对啊……
考虑离线解决这个问题
首先离散化y轴坐标
我们发现可以把一个询问拆成4个询问 一个是从(0,0)到(cj,dj)一个从(0,0)到(aj-1,bj-1)一个从(0,0)到(aj-1,dj)一个从(0,0)到(cj,bj-1),然后这个询问就可以用这几个相加减弄出来了。
将询问和树按横坐标排序后 从左往右扫一遍 遇到树就将其加入树状数组,遇到询问就查询一下,最后计算一下答案输出
#include <cstdio> #include <algorithm> using namespace std; const int N=4000000; struct query{int x,y,y0,op,id;}q[N+10]; struct tree{int x,y;}t[N+10]; int s[N+10],ans[N+10],n,m,cnt=0,tmp=0; bool cmp(query a,query b){return a.x==b.x?a.op<b.op:a.x<b.x;} bool cmp2(query a,query b){return a.y<b.y;} bool cmp3(query a,query b){return a.id<b.id;} void add(int x,int d){for(;x<=tmp;x+=x&-x) s[x]+=d;} int sum(int x){int ret=0;for(;x;x-=x&-x) ret+=s[x];return ret;} void read(int &x){char c;while((c=getchar())<'0' || c>'9');x=c-'0';while((c=getchar())>='0' && c<='9') x=x*10+c-'0';} int main(){ //freopen("1935.in","r",stdin);freopen("1935.out","w",stdout); // scanf("%d%d",&n,&m); read(n),read(m);q[0].y=-65478; for(int i=1;i<=n;i++) read(q[i].x),read(q[i].y); for(int i=1;i<=m;i++) { int x1,y1,x2,y2; read(x1);read(y1);read(x2);read(y2); // scanf("%d%d%d%d",&x1,&y1,&x2,&y2); q[n+(++cnt)].x=x1-1;//q1; q[n+cnt].y=y1-1; q[n+cnt].id=cnt; q[n+cnt].op=1; q[n+(++cnt)].x=x1-1;//q2; q[n+cnt].y=y2; q[n+cnt].id=cnt; q[n+cnt].op=1; q[n+(++cnt)].x=x2;//q3; q[n+cnt].y=y1-1; q[n+cnt].id=cnt; q[n+cnt].op=1; q[n+(++cnt)].x=x2;//q4; q[n+cnt].y=y2; q[n+cnt].id=cnt; q[n+cnt].op=1;//ans[i]=q4-q2-q3+q1 } sort(q+1,q+n+4*m+1,cmp2); for(int i=1;i<=n+4*m;i++) {if(q[i].y!=q[i-1].y) tmp++;q[i].y0=tmp;} sort(q+1,q+n+4*m+1,cmp); for(int i=1;i<=n+4*m;i++){ if(!q[i].op) add(q[i].y0,1); else ans[q[i].id]=sum(q[i].y0); } for(int i=1;i<=m;i++) printf("%d\n",ans[4*i]-ans[4*i-1]-ans[4*i-2]+ans[4*i-3]); return 0; }
线段树
打两个标记,一个记录乘法一个记录加法,根据乘法分配律可以得到:标记下传的时候要先传乘法的标记再传加法的标记,下传乘法的时候要同时将子节点的加法标记也乘对应的数。
然后总结一下我自己犯的错误
1.标记下传时 判断无标记之后直接不操作 而不是把标记加上去
2.线段树开始忘记build
3.开始的时候没有看到要取模
代码
#include <cstdio> #include <algorithm> using namespace std; const int N=300010,NUL=-657558; typedef long long LL; LL sum[N*4],plus[N*4],mul[N*4],a[N],L[N*4],R[N*4],mod,m,op,x1,y1,z1,n; void up(int x){sum[x]=(sum[x<<1]+sum[x<<1|1])%mod;} void down(int x){ if(mul[x]!=NUL) { (sum[x<<1]*=mul[x])%=mod; if(mul[x<<1]!=NUL) (mul[x<<1]*=mul[x])%=mod;else mul[x<<1]=mul[x]%mod; if(plus[x<<1]!=NUL) (plus[x<<1]*=mul[x])%=mod; (sum[x<<1|1]*=mul[x])%=mod; if(mul[x<<1|1]!=NUL) (mul[x<<1|1]*=mul[x])%=mod;else mul[x<<1|1]=mul[x]%mod; if(plus[x<<1|1]!=NUL) (plus[x<<1|1]*=mul[x])%=mod; } if(plus[x]!=NUL) { (sum[x<<1]+=plus[x]*(R[x<<1]-L[x<<1]+1)%mod)%=mod; if(plus[x<<1]!=NUL) (plus[x<<1]+=plus[x])%=mod;else plus[x<<1]=plus[x]%mod; (sum[x<<1|1]+=plus[x]*(R[x<<1|1]-L[x<<1|1]+1)%mod)%=mod; if(plus[x<<1|1]!=NUL) (plus[x<<1|1]+=plus[x])%=mod;else plus[x<<1|1]=plus[x]%mod; } mul[x]=plus[x]=NUL; } void build(int x,int l,int r){ plus[x]=mul[x]=NUL;L[x]=l;R[x]=r; if(l==r) {sum[x]=a[l]; return;} int mid=(l+r)>>1; build(x<<1,l,mid);build(x<<1|1,mid+1,r); up(x); } void change1(int x,int l,int r,int d){//plus int mid=(L[x]+R[x])>>1; if(l<=L[x] && R[x]<=r) { if(plus[x]!=NUL) (plus[x]+=d)%=mod;else plus[x]=d%mod; (sum[x]+=d*(R[x]-L[x]+1)%mod)%=mod; return; } down(x); if(mid<r) change1(x<<1|1,l,r,d); if(mid>=l) change1(x<<1,l,r,d); up(x); } void change2(int x,int l,int r,int d){//multiply int mid=(L[x]+R[x])>>1; if(l<=L[x] && R[x]<=r) { (sum[x]*=d%mod)%=mod; if(plus[x]!=NUL) (plus[x]*=d)%=mod; if(mul[x]!=NUL) (mul[x]*=d)%=mod; else mul[x]=d%mod; return; } down(x); if(mid<r) change2(x<<1|1,l,r,d); if(mid>=l) change2(x<<1,l,r,d); up(x); } LL ask(int x,int l,int r){ int mid=(L[x]+R[x])>>1; LL ret=0; if(l<=L[x] && R[x]<=r) return sum[x]; down(x); if(mid<r) (ret+=ask(x<<1|1,l,r))%=mod; if(mid>=l) (ret+=ask(x<<1,l,r))%=mod; return ret; } void print(){ for(int i=1;i<=n;i++) printf("%lld ",ask(1,i,i)); printf("\n"); } int main(){ //freopen("1798.in","r",stdin);freopen("1798.out","w",stdout); scanf("%lld%lld",&n,&mod); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); build(1,1,n); scanf("%lld",&m); for(int i=1;i<=m;i++){ scanf("%lld%lld%lld",&op,&x1,&y1); if(op==1) {scanf("%lld",&z1);change2(1,x1,y1,z1);} if(op==2) {scanf("%lld",&z1);change1(1,x1,y1,z1);} if(op==3) {printf("%lld\n",ask(1,x1,y1));} // print(); } return 0; }
这题 可以splay 也可以块状链表
我打了一个块状链表时间复杂度是$n\sqrt{n}$ 具体的使用方法详见论文 信息学中的分块思想.pdf
这里要注意的是 split前要标记下传一下 s[0]是无意义的 要从s[0].nxt开始弄
还有这题很坑的是 修改的时候可能把一个区间修改成0 和 最大子段和至少要有一个数 也就是全负数的时候不能输出0而要输出最大那个负数
没加读入优化在我E3 cpu的电脑上跑了25s 加了读入优化变成了2.95s ……
反倒是输出优化没什么效果 加了变成 2.93s……
接下来是代码 处理操作那里写的比较丑……
#include <cstdio> #include <algorithm> #include <cassert> using std::swap; using std::min; const int N=500,birth=19990616,INF=2099999999; typedef long long LL; struct node{ int a[N+10]; int sum,lm,rm,tag,rev,nxt,pre,sz,maxsum,mx; }s[1000*2+10]; int trash[20000],inbin,nnode,tmp[500000],n,m,cnt; LL max(LL a,LL b){return a>b?a:b;} int newnode(){ int ret=0; if(inbin) ret=trash[inbin--];else ret=++nnode; for(int i=0;i<=N;i++) s[ret].a[i]=0; s[ret].sum=s[ret].lm=s[ret].rm=s[ret].rev=s[ret].pre=s[ret].nxt=s[ret].sz=0;s[ret].mx=-INF; s[ret].tag=birth; return ret; } int find(int &pos){int i;for(i=s[0].nxt;s[i].nxt && pos>s[i].sz;pos-=s[i].sz,i=s[i].nxt);return i;} void up(int x){ int tmax=0,tmin=0,maxsum=0,ms=0; s[x].sum=0,s[x].mx=-INF; for(int i=1;i<=s[x].sz;i++) { maxsum+=s[x].a[i]; s[x].mx=max(s[x].mx,s[x].a[i]); if(maxsum > ms) ms=maxsum; if(maxsum<0) maxsum=0; s[x].sum+=s[x].a[i],tmax=max(tmax,s[x].sum),tmin=min(tmin,s[x].sum); } s[x].lm=tmax;s[x].rm=s[x].sum-tmin;s[x].maxsum=ms; } void down(int x){ int i,j; if(s[x].rev) for(i=1,j=s[x].sz;i<j;i++,j--) swap(s[x].a[i],s[x].a[j]);s[x].rev=0; if(s[x].tag!=birth) for(i=1;i<=s[x].sz;i++) s[x].a[i]=s[x].tag;s[x].tag=birth; up(x); } void merge(int x){ int t=s[x].nxt; if(!t) return; down(x);down(t); for(int i=1;i<=s[t].sz;i++) s[x].a[++s[x].sz]=s[t].a[i]; if(s[t].nxt) s[s[t].nxt].pre=x;s[x].nxt=s[t].nxt; trash[++inbin]=t; up(x); } void maintain(){ for(int i=s[0].nxt;i&&s[i].nxt;i=s[i].nxt){ while(s[i].sz+s[s[i].nxt].sz<=N && s[i].nxt) merge(i); } } void split(int x,int loc){//x 的第loc后分裂 int t=newnode(),i,j; down(x); s[t].pre=x;s[t].nxt=s[x].nxt;s[x].nxt=t; if(s[t].nxt) s[s[t].nxt].pre=t; for(i=loc+1,j=1;i<=s[x].sz;i++,j++) s[t].a[j]=s[x].a[i],s[t].sz++; s[x].sz=loc; up(x);up(t); } void insert(int pos,int tot){ int x=find(pos); split(x,pos); for(int i=1;i<=tot;i++){ if(s[x].sz==N){ int t=newnode();up(x); s[t].pre=x;s[t].nxt=s[x].nxt;s[x].nxt=t;x=t; } s[x].a[++s[x].sz]=tmp[i]; } up(x); if(s[x].nxt) s[s[x].nxt].pre=x; maintain(); } void remove(int pos,int tot){ int t1=pos-1,t2=pos+tot-1; int x1=find(t1),x2=find(t2); if(x1==x2) {down(x1);s[x1].sz-=tot;for(int i=t1+1;i<=s[x1].sz;i++) s[x1].a[i]=s[x1].a[i+tot];up(x1);} else { split(x1,t1); split(x2,t2); for(int i=s[x1].nxt;i!=s[x2].nxt;i=s[i].nxt) trash[++inbin]=i; s[x1].nxt=s[x2].nxt;s[s[x2].nxt].pre=x1; } maintain(); } void change(int pos,int tot,int c){ int t1=pos,t2=pos+tot-1; int x1=find(t1),x2=find(t2); if(x1==x2){down(x1);for(int i=t1;i<=t2;i++) s[x1].a[i]=c;up(x1);} else{ down(x1),down(x2); for(int i=t1;i<=s[x1].sz;i++) s[x1].a[i]=c;up(x1); for(int i=1;i<=t2;i++) s[x2].a[i]=c;up(x2); for(int i=s[x1].nxt;i!=x2;i=s[i].nxt) s[i].tag=c,s[i].sum=c*s[i].sz,s[i].lm=c>0?s[i].sum:0,s[i].rm=c>0?s[i].sum:0,s[i].maxsum=c>0?s[i].sum:0; } } void flip(int pos,int tot){ int t1=pos-1,t2=pos+tot-1,i,j; int x1=find(t1),x2=find(t2); if(x1==x2){ down(x1); for(i=t1+1,j=t2;i<j;i++,j--) swap(s[x1].a[i],s[x1].a[j]); up(x1); } else{ split(x1,t1),split(x2,t2); int tt=s[x1].nxt,ttt=s[x2].nxt; for(int i=x2;i!=x1;i=s[i].nxt) swap(s[i].lm,s[i].rm),swap(s[i].nxt,s[i].pre),s[i].rev^=1; s[x1].nxt=x2;s[x2].pre=x1;s[tt].nxt=ttt;s[ttt].pre=tt; //up(x1),up(ttt); } maintain(); } LL sum(int pos,int tot){ int t1=pos,t2=pos+tot-1; int x1=find(t1),x2=find(t2); LL ret=0; if(x1==x2){ down(x1); for(int i=t1;i<=t2;i++) ret+=s[x1].a[i]; } else { down(x1),down(x2); for(int i=t1;i<=s[x1].sz;i++) ret+=s[x1].a[i]; for(int i=1;i<=t2;i++)ret+=s[x2].a[i]; for(int i=s[x1].nxt;i!=x2;i=s[i].nxt)ret+=s[i].sum; } return ret; } LL maxsum(){ LL lm=s[0].lm,rm=s[0].rm,sum=s[0].sum,maxsum=s[0].maxsum,mx=-INF; for(int i=s[0].nxt;i;i=s[i].nxt){ LL lm2,rm2,sum2,maxsum2; mx=max(mx,s[i].mx); sum2=sum+s[i].sum; lm2=max(lm,sum+s[i].lm); rm2=max(s[i].rm,s[i].sum+rm); maxsum2=max(maxsum,s[i].maxsum); maxsum2=max(maxsum2,rm+s[i].lm); sum=sum2;lm=lm2;rm=rm2,maxsum=maxsum2; } return mx<0?mx:maxsum; } void print(){ for(int i=s[0].nxt;i;i=s[i].nxt) { down(i); for(int j=1;j<=s[i].sz;j++) printf("%d ",s[i].a[j]); } printf("\n"); } void read(int &x){ char c; bool fu=false; while((c=getchar())<'0' || c>'9') if(c=='-') fu=true;x=c-'0'; while((c=getchar())>='0'&&c<='9') x=x*10+c-'0'; if(fu) x=-x; } int main(){ //freopen("1500.in","r",stdin);freopen("1500.out","w",stdout); read(n);read(m); for(int i=1;i<=n;i++)read(tmp[i]); s[0].nxt=newnode(); insert(0,n); for(int i=1;i<=m;i++) { char op=getchar(); switch(cnt++,op){ int pos,tot,c; case 'I':{ for(int i=1;i<=6;i++) getchar(); read(pos),read(tot); for(int i=1;i<=tot;i++) read(tmp[i]); insert(pos,tot); break; } case 'D':{ for(int i=1;i<=6;i++) getchar(); read(pos),read(tot); remove(pos,tot); break; } case 'M':{ getchar(); char op2=getchar(); if(op2=='K'){ for(int i=1;i<=7;i++) getchar(); read(pos),read(tot),read(c); change(pos,tot,c); } if(op2=='X'){ for(int i=1;i<=5;i++) getchar(); printf("%lld\n",maxsum()); } break; } case 'R':{ for(int i=1;i<=7;i++) getchar(); read(pos),read(tot); flip(pos,tot); break; } case 'G':{ for(int i=1;i<=6;i++) getchar(); read(pos),read(tot); printf("%lld\n",sum(pos,tot)); break; } } } return 0; }