非旋转式Treap1500 ：）
#include <bits/stdc++.h>
#pragma GCC optimize(3) using namespace std; const int INF=0x3f3f3f3f; struct node
{
int val,key,size;
int sum,lx,rx,mx,revf,chgf;
node *l,*r;
node() { }
node(const int x)
{
mx=val=sum=x; key=rand();
size=; lx=rx=(x>?x:);
chgf=INF; revf=; l=r=;
} void push_down()
{
if(chgf!=INF)
{
sum=chgf*size;
val=chgf;
lx=rx=(chgf>=?sum:);
mx=(chgf>=?sum:chgf);
if(l) l->chgf=chgf;
if(r) r->chgf=chgf;
chgf=INF; revf=;
}
if(revf)
{
if(l)l->revf^=;
if(r)r->revf^=;
swap(l,r);
swap(lx,rx);
revf=;
} return ;
} void update()
{
if(l)l->push_down();
if(r)r->push_down();
sum=(l?l->sum:)+(r?r->sum:)+val;
size=(l?l->size:)+(r?r->size:)+;
mx=max(max((l?l->mx:-INF),(r?r->mx:-INF)),
(l?l->rx:)+(r?r->lx:)+val);
lx=max((l?l->lx:), (l?l->sum:)+val+(r?r->lx:));
rx=max((r?r->rx:), (r?r->sum:)+val+(l?l->rx:));
return ;
} }U[],*Trash[],*ALL=U; int top; node * ALLOC(const int x)
{
return new(top?Trash[top--]:++ALL)node(x);
} void RECYCLE(node * t)
{
if(!t)return ;
RECYCLE(t->l);
RECYCLE(t->r);
Trash[++top]=t;
return ;
} struct Treap
{
typedef pair<node *,node *> PNN;
public:
Treap() { root=; } private: node * root; node * merge(node * t1,node * t2)
{
if(!t1) return t2; if(!t2) return t1;
t1->push_down(); t2->push_down();
if(t1->key < t2->key)
return t1->r=merge(t1->r,t2),t1->update(),t1;
return t2->l=merge(t1,t2->l),t2->update(),t2;
} PNN split(node * t,const int pos)
{
if(t) t->push_down();
if(!t) return make_pair((node*),(node*));
if(!pos) return make_pair((node*),t);
if(t->l && t->l->size==pos)
{
node * temp=t->l;
return t->l=,t->update(),make_pair(temp,t);
}
if(t->l && t->l->size+==pos)
{
node * temp=t->r;
return t->r=,t->update(),make_pair(t,temp);
}
if(t->l && t->l->size>pos)
{
PNN temp=split(t->l,pos);
return t->l=temp.second,t->update(),
make_pair(temp.first,t);
}
if(!t->r) return make_pair(t,(node*));
PNN temp=split(t->r,pos-(t->l?t->l->size:)-);
return t->r=temp.first,t->update(),make_pair(t,temp.second);
} node * build(const int * A,const int N)
{
stack<node *> stk; node * temp=;
for(int i=;i<N;++i)
{
node * t=ALLOC(A[i]);
while(!stk.empty() && t->key<stk.top()->key)
temp=stk.top(),temp->update(),stk.pop();
if(!stk.empty())
{
t->l=stk.top()->r;
t->update();
stk.top()->r=t;
stk.top()->update();
stk.push(t);
}
else
{
t->l=temp;
t->update();
stk.push(t);
}
}
while(!stk.empty()) temp=stk.top(),temp->update(),stk.pop();
return temp;
} public:
void insert(const int pos,const int * A,const int N)
{
PNN t=split(root,pos);
t.first=merge(t.first,build(A,N));
root=merge(t.first,t.second);
return ;
} void erase(const int l,const int r)
{
PNN t1=split(root,l-);
PNN t2=split(t1.second,r-l+);
RECYCLE(t2.first);
root=merge(t1.first,t2.second);
} void make_same(const int l,const int r,const int d)
{
PNN t1=split(root,l-);
PNN t2=split(t1.second,r-l+);
t2.first->chgf=d;
t2.first->push_down();
root=merge(t1.first,merge(t2.first,t2.second));
} void reverse(const int l,const int r)
{
PNN t1=split(root,l-);
PNN t2=split(t1.second,r-l+);
t2.first->revf^=;
t2.first->push_down();
root=merge(t1.first,merge(t2.first,t2.second));
} int get_sum(const int l,const int r)
{
if(l>r)return ;
PNN t1=split(root,l-);
PNN t2=split(t1.second,r-l+);
t2.first->push_down();
int temp=t2.first->sum;
root=merge(t1.first,merge(t2.first,t2.second));
return temp;
} int max_sum()
{
PNN t1=split(root,);
PNN t2=split(t1.second,root->size);
t2.first->push_down();
int temp=t2.first->mx;
root=merge(t1.first,merge(t2.first,t2.second));
return temp;
}
}S; int n,m,x,y,z;
int a[];
char op[]; int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<n;++i) scanf("%d",&a[i]);
S.insert(,a,n);
while(m--)
{
scanf("%s",op);
if(op[]=='S') // Insert
{
scanf("%d%d",&x,&y);
for(int i=;i<y;++i) scanf("%d",&a[i]);
S.insert(x,a,y);
}
if(op[]=='L') // Delete
{
scanf("%d%d",&x,&y);
S.erase(x,x+y-);
}
if(op[]=='K') // Make_same
{
scanf("%d%d%d",&x,&y,&z);
S.make_same(x,x+y-,z);
}
if(op[]=='V') // Reverse
{
scanf("%d%d",&x,&y);
S.reverse(x,x+y-);
}
if(op[]=='T') // Get_sum
{
scanf("%d%d",&x,&y);
printf("%d\n",S.get_sum(x,x+y-));
}
if(op[]=='X') // Max_sum
{
printf("%d\n",S.max_sum());
}
} return ;
}