Solution
题意
维护一个数组，支持区间加点删点，区间覆盖，区间翻转，区间求和，求和最大的子序列
fhq模板题？
学完fhq后，就再也不爱打splay了 ......
注意回收点的时候要删标记，否则神奇MLE
Code
#include<bits/stdc++.h>
#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<int> 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]<inf) update(ls[x],3),update(rs[x],3),cover[x]=inf;
if(rev[x]) update(ls[x],1),update(rs[x],1),rev[x]=0;
}
inline void recycle(int p)
{
if(!p) return;
int L=ls[p],R=rs[p];
recycle(L);recycle(R);q.push(p);
ls[p]=rs[p]=rev[p]=0;
}
public:
int rt;
int Merge(int rt1,int rt2)
{
if(rt1) down(rt1);
if(rt2) down(rt2);
if(!rt1||!rt2) return rt2|rt1;
if(pri[rt1]<pri[rt2])
{
rs[rt1]=Merge(rs[rt1],rt2);
up(rt1);return rt1;
}
else
{
ls[rt2]=Merge(rt1,ls[rt2]);
up(rt2);return rt2;
}
}
void Split(int x,int k,int&rt1,int&rt2)
{
if(!x) return (void)(rt1=rt2=0);
down(x);
if(k<=siz[ls[x]])
{
Split(ls[x],k,rt1,rt2);
ls[x]=rt2;up(x);rt2=x;
}
else
{
Split(rs[x],k-siz[ls[x]]-1,rt1,rt2);
rs[x]=rt1;up(x);rt1=x;
}
}
void Build(int &x,int l,int r)
{
if(l>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
",tt[rt3]);rt=Merge(rt1,Merge(rt3,rt4));
}
void QueMax(){printf("%d
",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！