你需要维护一个序列，支持以下4种操作。一，将区间(u,v)的数覆盖为C；二， 将区间(u,v)的数依次加上一个以C为首项、C为公差的等差数列；三，将数C插入 第i个位置；四，查询区间(u,v)的数的和。序列最初有n个数，一共会有Q次操 作。保证结果在longlong范围内。
两个标记均可合并 顺序是先执行赋值 splay维护
#include<cstdio>#include<algorithm>#define fo(i,a,b) for(i=a;i<=b;i++)#define fd(i,a,b) for(i=a;i>=b;i--)using namespace std;typedef long long ll;const int maxn=100000+10;int father[maxn*2],tree[maxn*2][2],size[maxn*2],sta[maxn*2];ll key[maxn*2],num[maxn*2];ll st[maxn*2],sx[maxn*2],gc[maxn*2];bool bz[maxn*2];int i,j,k,l,r,mid,t,n,m,tot,top,root;ll x,ans;ll read(){ ll x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9'){ if (ch=='-') f=-1; ch=getchar(); } while (ch>='0'&&ch<='9'){ x=x*10+ch-'0'; ch=getchar(); } return x*f;}int pd(int x){ return tree[father[x]][1]==x;}void update(int x){ num[x]=num[tree[x][0]]+num[tree[x][1]]+key[x]; size[x]=size[tree[x][0]]+size[tree[x][1]]+1;}void rotate(int x){ int y=father[x],z=pd(x); father[x]=father[y]; if (father[y]) tree[father[y]][pd(y)]=x; tree[y][z]=tree[x][1-z]; if (tree[x][1-z]) father[tree[x][1-z]]=y; tree[x][1-z]=y; father[y]=x; update(y); update(x);}void marks(int x,ll v){ if (!x) return; bz[x]=1; sx[x]=gc[x]=0; st[x]=key[x]=v; num[x]=(ll)v*size[x];}ll calc(ll s,ll d,int n){ return (2*s+(ll)(n-1)*d)*n/2;}void markd(int x,ll s,ll d){ if (!x) return; sx[x]+=s; gc[x]+=d; key[x]+=(s+(ll)d*size[tree[x][0]]); num[x]+=calc(s,d,size[x]);}void clear(int x){ if (bz[x]){ marks(tree[x][0],st[x]); marks(tree[x][1],st[x]); bz[x]=0; } if (sx[x]||gc[x]){ markd(tree[x][0],sx[x],gc[x]); markd(tree[x][1],sx[x]+(ll)gc[x]*(size[tree[x][0]]+1),gc[x]); sx[x]=gc[x]=0; }}void remove(int x,int y){ top=0; while (x!=y){ sta[++top]=x; x=father[x]; } while (top){ clear(sta[top]); top--; }}void splay(int x,int y){ remove(x,y); while (father[x]!=y){ if (father[father[x]]!=y) if (pd(x)==pd(father[x])) rotate(father[x]);else rotate(x); rotate(x); }}int kth(int x,int y){ clear(x); if (y==size[tree[x][0]]+1) return x; else if (y<size[tree[x][0]]+1) return kth(tree[x][0],y); else return kth(tree[x][1],y-size[tree[x][0]]-1);}void split(int x,int j,int &l,int &r){ if (!j){ l=0; r=x; return; } int k=kth(x,j); splay(k,0); clear(k); l=k;r=tree[k][1]; father[r]=0; tree[l][1]=0; update(l);}void merge(int l,int r,int &x){ if (!l||!r){ x=l+r; return; } int k=kth(l,size[l]); splay(k,0); clear(k); tree[k][1]=r; father[r]=k; update(k); x=k;}int main(){ //freopen("3188.in","r",stdin);freopen("3188.out","w",stdout); n=read();m=read(); fo(i,1,n){ key[i]=read(); father[i]=i-1; if (i>1) tree[i-1][1]=i; } fd(i,n,1) update(i); tot=n; root=1; while (m--){ t=read(); if (t==1){ j=read();k=read();x=read(); split(root,k,l,r); split(l,j-1,l,mid); marks(mid,x); merge(l,mid,l); merge(l,r,root); } else if (t==2){ j=read();k=read();x=read(); split(root,k,l,r); split(l,j-1,l,mid); markd(mid,x,x); merge(l,mid,l); merge(l,r,root); } else if (t==3){ j=read();x=read(); split(root,j-1,l,r); key[++tot]=x; num[tot]=x; size[tot]=1; merge(l,tot,l); merge(l,r,root); } else{ j=read();k=read(); split(root,k,l,r); split(l,j-1,l,mid); PRintf("%lld/n",num[mid]); merge(l,mid,l); merge(l,r,root); } }}新闻热点
疑难解答
