Solution

题意

维护一个数组，支持区间加点删点，区间覆盖，区间翻转，区间求和，求和最大的子序列

fhq模板题？

学完fhq后，就再也不爱打splay了 ......

注意回收点的时候要删标记，否则神奇MLE

Code

#include
    
     #define ll long long#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))inline int read(){    int 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<<3)+(x<<1)+ch-'0';ch=getchar();}    return x*f;}#define MN 500005#define inf 550000000 int s[MN];std::queue
     
       q;class fhq{    private:        int sz;        int pri[MN],ls[MN],rs[MN],siz[MN];        int pr[MN],su[MN],tt[MN],cover[MN],V[MN],ans[MN];        /*        class QUEUE        {            private:                int q[MN<<3],top;                   public:                QUEUE(int _top=0):top(_top){}                inline void push(int x){q[top]=x;(++top)%=MN;}                inline bool empty(){return top==0;}                inline int front(){return q[top-1];}                inline void pop(){top--;}        }q;        */        bool rev[MN];        inline unsigned int random()        {            static unsigned int x=23333;            return x^=x<<13,x^=x>>17,x^=x<<5;        }        inline void up(int x)        {            siz[x]=1+siz[ls[x]]+siz[rs[x]];            tt[x]=tt[ls[x]]+tt[rs[x]]+V[x];            if(!ls[x]&&!rs[x]){pr[x]=su[x]=ans[x]=V[x];}            else if(!ls[x])            {                pr[x]=V[x]+max(0,pr[rs[x]]);                su[x]=max(su[rs[x]],tt[rs[x]]+V[x]);                ans[x]=max(ans[rs[x]],pr[x]);            }            else if(!rs[x])            {                pr[x]=max(pr[ls[x]],tt[ls[x]]+V[x]);                su[x]=V[x]+max(0,su[ls[x]]);                ans[x]=max(ans[ls[x]],su[x]);            }            else            {                pr[x]=max(pr[ls[x]],tt[ls[x]]+V[x]+max(0,pr[rs[x]]));                su[x]=max(su[rs[x]],tt[rs[x]]+V[x]+max(0,su[ls[x]]));                ans[x]=max(ans[ls[x]],ans[rs[x]]);                ans[x]=max(ans[x],max(0,su[ls[x]])+V[x]+max(0,pr[rs[x]]));            }        }        inline void update(int x,int opt)        {            if(!x) return;             if(opt==1)            {                std::swap(pr[x],su[x]);std::swap(ls[x],rs[x]);                rev[ls[x]]^=1;rev[rs[x]]^=1;            }            if(opt==3)            {                V[x]=cover[x];tt[x]=cover[x]*siz[x];                su[x]=pr[x]=ans[x]=max(cover[x],cover[x]*siz[x]);                cover[ls[x]]=cover[rs[x]]=cover[x];                rev[ls[x]]=rev[rs[x]]=0;            }        }        inline void down(int x)        {            if(cover[x]
      
       r) return;int mid=l+r>>1;            if(!q.empty()) x=q.front(),q.pop();else x=++sz;            ans[x]=tt[x]=V[x]=s[mid],cover[x]=inf,pri[x]=random();            if(l==r) return(void)(pr[x]=su[x]=V[x],siz[x]=1);            Build(ls[x],l,mid-1),Build(rs[x],mid+1,r);up(x);        }        void Reverse(int l,int len)        {            register int rt1,rt2,rt3,rt4;            Split(rt,l-1,rt1,rt2);Split(rt2,len,rt3,rt4);            rev[rt3]^=1;update(rt3,1);rt=Merge(rt1,Merge(rt3,rt4));        }        void Replace(int l,int len,int c)        {            register int rt1,rt2,rt3,rt4;            Split(rt,l-1,rt1,rt2);Split(rt2,len,rt3,rt4);            cover[rt3]=c;update(rt3,3);rev[rt3]=0;rt=Merge(rt1,Merge(rt3,rt4));        }        void Delete(int l,int len)        {            register int rt1,rt2,rt3,rt4;            Split(rt,l-1,rt1,rt2);Split(rt2,len,rt3,rt4);            rt=Merge(rt1,rt4);recycle(rt3);        }        void Insert(int pos,int r)        {            register int rt1,rt2,rt3;            Split(rt,pos,rt1,rt2);Build(rt3,1,r);            rt=Merge(rt1,Merge(rt3,rt2));        }        void QueSum(int l,int len)        {            register int rt1,rt2,rt3,rt4;            Split(rt,l-1,rt1,rt2);Split(rt2,len,rt3,rt4);            printf("%d\n",tt[rt3]);rt=Merge(rt1,Merge(rt3,rt4));        }        void QueMax(){printf("%d\n",ans[rt]);}}T;int main(){    register int i,n,m,posi,tot,c;    register char ch[50];n=read();m=read();    for(i=1;i<=n;++i) s[i]=read();    T.Build(T.rt,1,n);    while(m--)    {        scanf("%s",ch+1);        if(ch[1]=='I')        {            posi=read();tot=read();            for(i=1;i<=tot;++i) s[i]=read();            T.Insert(posi,tot);        }        if(ch[1]=='D')        {            posi=read(),tot=read();            T.Delete(posi,tot);        }        if(ch[1]=='M'&&ch[3]=='K')        {            posi=read();tot=read();c=read();            T.Replace(posi,tot,c);        }        if(ch[1]=='R')        {            posi=read();tot=read();            T.Reverse(posi,tot);        }        if(ch[1]=='G')        {            posi=read();tot=read();            T.QueSum(posi,tot);        }        if(ch[1]=='M'&&ch[3]=='X'){T.QueMax();}    }    return 0;}
      
     
    

---

Blog来自PaperCloud，未经允许，请勿转载，TKS！