让我们响应王学长的号召勇敢的分开写splay和lct吧！
分开写大法好！！！！！！！！！！！杜教的ch[4]弱爆了！！！！
#include <stdio.h>
#include <algorithm>
char ch;
inline void read(int &x)
{
x=;ch=getchar();
while(ch<=) ch=getchar();
while(ch>) x=x*+ch-,ch=getchar();
}; inline void G(int x){while(x--) getchar();} #define MAXN 50005
#define MAXM 250005 int n,q; struct Info{
int mi,size;
long long sum;
}; const int NULL_TAG=;
const Info NULL_INFO=(Info){,,}; inline Info operator + (const Info &a,const Info &b)
{
return (Info){std::min(a.mi,b.mi),a.size+b.size,a.sum+b.sum};
}; inline Info operator * (const Info &a,const int &b)
{
return a.size ? (Info){a.mi+b,a.size,a.sum+1LL*a.size*b}: a;
}; struct TopTree{ struct splay_node{
splay_node *ch[],*fa;
Info x,sum;
int tag,tag_sum; inline void add_tag(int t)
{
tag=tag+t;tag_sum=tag_sum+t;
x=x*t;sum=sum*t;
}; inline void down()
{
if(ch[]) ch[]->add_tag(tag);
if(ch[]) ch[]->add_tag(tag);
tag=NULL_TAG;
}; inline void update()
{
sum=x;
if(ch[]) sum=sum+ch[]->sum;
if(ch[]) sum=sum+ch[]->sum;
}; }; splay_node _nodes[MAXN]; inline int get_parent(splay_node *x,splay_node *&fa)
{
return (fa=x->fa) ? fa->ch[]==x : -;
}; inline void rotate(splay_node *x)
{
int t1,t2;
splay_node *fa,*gfa;
t1=get_parent(x,fa);
t2=get_parent(fa,gfa);
if((fa->ch[t1]=x->ch[t1^])) fa->ch[t1]->fa=fa;
fa->fa=x;x->fa=gfa;x->ch[t1^]=fa;
if(t2!=-) gfa->ch[t2]=x;
fa->update();
}; inline void pushdown(splay_node *x)
{
static splay_node *stack[MAXN];
int cnt=;
while(x) stack[cnt++]=x,x=x->fa;
while(cnt--) stack[cnt]-> down();
}; inline splay_node * splay(splay_node *x)
{
pushdown(x);
while(){
int t1,t2;
splay_node *fa,*gfa;
t1=get_parent(x,fa);
if(t1==-) break;
t2=get_parent(fa,gfa);
if(t2==-){
rotate(x);break;
}else if(t1==t2){
rotate(fa);rotate(x);
}else{
rotate(x);rotate(x);
};
};
x->update();
return x;
}; inline splay_node * join(splay_node *L,splay_node *R)
{
if(!L) return R;
if(!R) return L;
while(L->ch[]) L-> down(),L=L->ch[];
splay(L)->ch[]=R;
R->fa=L;
L->update();
return L;
}; static splay_node *root[MAXN]; struct lct_node{
lct_node *ch[],*fa,*first,*last;
bool rev; Info x,sum,tree,all;
int chain_tag,tree_tag; inline void add_rev_tag()
{
std::swap(ch[],ch[]);
std::swap(first,last);
rev^=;
}; inline void add_chain_tag(int t)
{
x=x*t;sum=sum*t;
chain_tag=chain_tag+t;
all=sum+tree;
}; inline void add_tree_tag(int t); inline void down()
{
if(rev){
if(ch[]) ch[]->add_rev_tag();
if(ch[]) ch[]->add_rev_tag();
rev=;
};
if(ch[]) ch[]->add_chain_tag(chain_tag),ch[]->add_tree_tag(tree_tag);
if(ch[]) ch[]->add_chain_tag(chain_tag),ch[]->add_tree_tag(tree_tag);
chain_tag=tree_tag=NULL_TAG;
}; inline void update();
}; static lct_node lct[MAXN]; inline int get_parent(lct_node *x,lct_node *&fa)
{
return (fa=x->fa) ? fa->ch[]==x?:fa->ch[]==x?:- : -;
}; inline void rotate(lct_node *x)
{
int t1,t2;
lct_node *fa,*gfa;
t1=get_parent(x,fa);
t2=get_parent(fa,gfa);
if((fa->ch[t1]=x->ch[t1^])) fa->ch[t1]->fa=fa;
fa->fa=x;x->fa=gfa;x->ch[t1^]=fa;
if(t2!=-) gfa->ch[t2]=x;
fa->update();
}; inline void pushdown(lct_node *x)
{
static lct_node *stack[MAXN];
int cnt=;
while(){
stack[cnt++]=x;
lct_node *fa=x->fa;
if(!fa || (fa->ch[]!=x && fa->ch[]!=x)) break;
x=fa;
};
while(cnt--) stack[cnt]-> down();
}; inline lct_node * splay(lct_node *x)
{
pushdown(x);
while(){
int t1,t2;
lct_node *fa,*gfa;
t1=get_parent(x,fa);
if(t1==-) break;
t2=get_parent(fa,gfa);
if(t2==-){
rotate(x);break;
}else if(t1==t2){
rotate(fa);rotate(x);
}else{
rotate(x);rotate(x);
};
};
x->update();
return x;
}; inline lct_node * access(lct_node *x);
inline void setroot(int x);
inline void modifychain(int x,int y,int t);
inline void modifysubtree(int x,int y,int t);
inline Info query_chain(int x,int y);
inline Info query_subtree(int x,int y);
inline void link(int x,int y);
inline void cut(int x,int y);
inline void init(int *a); }_toptree; TopTree::lct_node TopTree::lct[MAXN];
TopTree::splay_node *TopTree::root[MAXN]; inline void TopTree::lct_node::add_tree_tag(int t)
{
tree=tree*t;
tree_tag=tree_tag+t;
all=sum+tree;
int id=this-TopTree::lct;
if(root[id]){
root[id]->add_tag(t);
};
}; inline void TopTree::lct_node::update()
{
sum=x;tree=NULL_INFO;
int id=this-TopTree::lct;
if(root[id]){
tree=tree+root[id]->sum;
};
if(ch[]) sum=sum+ch[]->sum,tree=tree+ch[]->tree;
if(ch[]) sum=sum+ch[]->sum,tree=tree+ch[]->tree;
all=sum+tree;
first=ch[]?ch[]->first:this;
last=ch[]?ch[]->last:this;
}; inline TopTree::lct_node * TopTree::access(TopTree::lct_node *x)
{
TopTree::lct_node *ret=NULL;
while(x){
splay(x);
int X=x-TopTree::lct;
if(x->ch[]){
int id=x->ch[]->first-TopTree::lct;
splay_node *p=_nodes+id;
p->ch[]=root[X];
if(root[X]) root[X]->fa=p;
p->ch[]=NULL;
p->fa=NULL;
p->x=x->ch[]->all;
p->tag=p->tag_sum=NULL_TAG;
p->update();
root[X]=p;
x->ch[]=NULL;
};
if(ret){
int id=ret->first-TopTree::lct;
splay_node *p=_nodes+id;
splay(p);
if(p->ch[]) p->ch[]->fa=NULL;
if(p->ch[]) p->ch[]->fa=NULL;
root[X]=join(p->ch[],p->ch[]);
ret->add_chain_tag(p->tag_sum),ret->add_tree_tag(p->tag_sum);
x->ch[]=ret;
};
x->update();
ret=x;x=x->fa;
};
return ret;
}; inline void TopTree::setroot(int x)
{
access(TopTree::lct+x)->add_rev_tag();
}; inline void TopTree::modifychain(int x,int y,int t)
{
setroot(x);
access(TopTree::lct+y)->add_chain_tag(t);
}; inline void TopTree::modifysubtree(int x,int y,int t)
{
setroot(x);
access(TopTree::lct+y),splay(TopTree::lct+y);
TopTree::lct[y].x=TopTree::lct[y].x*t;
if(root[y]) root[y]->add_tag(t);
TopTree::lct[y].update();
}; inline Info TopTree::query_chain(int x,int y)
{
setroot(x);
return access(TopTree::lct+y)->sum;
}; inline Info TopTree::query_subtree(int x,int y)
{
setroot(x);
access(TopTree::lct+y),splay(TopTree::lct+y);
return root[y] ? TopTree::lct[y].x+root[y]->sum : TopTree::lct[y].x;
}; inline void TopTree::link(int x,int y)
{
setroot(x);
splay(TopTree::lct+x)->fa=TopTree::lct+y;
access(TopTree::lct+y);
splay(TopTree::lct+y)->ch[]=TopTree::lct+x;
TopTree::lct[y].update();
}; inline void TopTree::cut(int x,int y)
{
setroot(x);
access(TopTree::lct+y);
TopTree::lct_node *t=splay(TopTree::lct+y);
t->ch[]->fa=NULL;t->ch[]=NULL;
t->update();
}; inline void TopTree::init(int *a)
{
int i;
for(i=;i<=n;i++){
TopTree::lct[i].first=TopTree::lct[i].last=TopTree::lct+i;
TopTree::lct[i].x=TopTree::lct[i].sum=TopTree::lct[i].all=(Info){a[i],,a[i]};
TopTree::lct[i].tree=NULL_INFO;
TopTree::lct[i].chain_tag=TopTree::lct[i].tree_tag=NULL_TAG;
};
};