| 记录编号 |
251819 |
评测结果 |
AAAAAAAAAAAAAAAAAAAA |
| 题目名称 |
Toptree |
最终得分 |
100 |
| 用户昵称 |
 stdafx.h |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
2.270 s |
| 提交时间 |
2016-04-18 17:32:43 |
内存使用 |
15.93 MiB |
显示代码纯文本
#define maxn 200010ul
#define rep(a,b,c) for(int a=(b);a<(c);a++)
#include <stdio.h>
#include <algorithm>
#define L(h) (ch[h][0])
#define R(h) (ch[h][1])
const int inf=0x7fffffff;
struct info{//information
int mn,size;//max , min , sum ,size
info(){size=0,mn=inf;}
info(int x){mn=x,size=1;}
info(int mn,int size):
mn(mn),size(size){}
};
struct flag{//tag
int mul,add;
flag(){mul=1,add=0;return;}
flag(int mul,int add):
mul(mul),add(add){}
bool ex(){return mul!=1||add!=0;}
};
int atag(int x,flag p){return x*p.mul+p.add;}// val + tag
info operator + (const info &a,const flag &b){return a.size?info(atag(a.mn,b),a.size):a;}// info + tag
info operator + (const info &a,const info &b){return info(std::min(a.mn,b.mn),a.size+b.size);}// info + info
flag operator + (const flag &a,const flag &b){return flag(a.mul*b.mul,atag(a.add,b));}// tag + tag
flag ctag[maxn],ttag[maxn];// chain tag ( including self ), tree tag( not including self )
info csum[maxn],tsum[maxn],asum[maxn];// chain sum , tree sum , all sum
int n,q,tot,rub,ru[maxn],ch[maxn][4],fa[maxn],val[maxn],sta[maxn],e[maxn][2];// n , query_cnt , node_tot , rubbish ,rubbish_arr , son , fa , val , stack , edge
bool rev[maxn],in[maxn];// rev tag , A tag
bool isroot(int x,int t){
if(t) return !fa[x]||!in[fa[x]]||!in[x];// no father || fa != A || x != A , judge in splay2
return !fa[x]||(L(fa[x])!=x&&R(fa[x])!=x)||in[fa[x]]||in[x];// no father || root of splay1 || fa = A || x = A , judge in splay1
}
void giverev(int x){//give rev tag
if(!x) return;
std::swap(L(x),R(x));
rev[x]^=1;
return;
}
void tagchain(int x,flag p){// tag chain
if(!x) return;
csum[x]=csum[x]+p;// chain sum
asum[x]=csum[x]+tsum[x];// all sum
val[x]=atag(val[x],p);// change val
ctag[x]=ctag[x]+p;// chain tag
return;
}
void tagtree(int x,flag p,bool t){// tag tree
if(!x) return;
tsum[x]=tsum[x]+p;//tree sum
ttag[x]=ttag[x]+p;// tree tag
if(!in[x]&&t) tagchain(x,p);//x ! = A tree including chain
else asum[x]=csum[x]+tsum[x];//all sum
return;
}
void pushdown(int x){//pushdown
if(!x) return;
if(rev[x]) giverev(L(x)),giverev(R(x)),rev[x]=false;//rev tag
if(!in[x]&&ctag[x].ex()) tagchain(L(x),ctag[x]),tagchain(R(x),ctag[x]),ctag[x]=flag();//chain tag
if(ttag[x].ex()){
rep(i,0,2) tagtree(ch[x][i],ttag[x],0);//only chain
rep(i,2,4) tagtree(ch[x][i],ttag[x],1);//tree and tree's chain
ttag[x]=flag();
}
return;
}
void update(int x){
tsum[x]=info();
rep(i,0,2) if(ch[x][i]) tsum[x]=tsum[x]+tsum[ch[x][i]];//tree sum
rep(i,2,4) if(ch[x][i]) tsum[x]=tsum[x]+asum[ch[x][i]];//tree sum
if(in[x]) csum[x]=info(),asum[x]=tsum[x];//A node
else{
csum[x]=info(val[x]);//chain sum
rep(i,0,2) if(ch[x][i]) csum[x]=csum[x]+csum[ch[x][i]];
asum[x]=csum[x]+tsum[x];
}
return;
}
int child(int x,int t){//child x -> t
pushdown(x),pushdown(ch[x][t]);
return ch[x][t];
}
void rotate(int x,int d){//rotate x to its fa
int y=fa[x],w=(ch[y][d+1]==x)+d;//d = 0 or 2
ch[y][w]=ch[x][w^1];
if(ch[x][w^1]) fa[ch[x][w^1]]=y;
if(fa[y]) for(int z=fa[y],i=0;i<4;i++)
if(ch[z][i]==y) ch[z][i]=x;
fa[x]=fa[y],fa[y]=x,ch[x][w^1]=y,update(y);
return;
}
void splay(int x,int t=0){//splay
int top=1,i=x,y;sta[1]=x;
while(!isroot(i,t)) sta[++top]=i=fa[i];
while(top) pushdown(sta[top--]);//tag down
while(!isroot(x,t)){
y=fa[x];
if(!isroot(y,t)){
if((ch[fa[y]][t]==y)^(ch[y][t]==x)) rotate(x,t);
else rotate(y,t);
}
rotate(x,t);
}
update(x);
return;
}
int newnode(){//new A node
int x=rub?ru[rub--]:++tot;
rep(i,2,4) ch[x][i]=0;in[x]=true;
return x;
}
void setson(int x,int t,int y){//set son
ch[x][t]=y,fa[y]=x;
return;
}
int pos(int x){
rep(i,0,4) if(ch[fa[x]][i]==x) return i;//x pos
return 4;
}
void add(int x,int y){// x - > y add vistual edge , splay2 has no father - son res
if(!y) return;
pushdown(x);
rep(i,2,4) if(!ch[x][i]){
setson(x,i,y);
return;
}
while(ch[x][2]&&in[ch[x][2]]) x=child(x,2);
int z=newnode();//new A node
setson(z,2,ch[x][2]),setson(z,3,y);
setson(x,2,z),splay(z,2);
return;
}
void del(int x){// x -> x'fa del vistual edge
if(!x) return;
splay(x);
if(!fa[x]) return;
int y=fa[x];
if(in[y]){
int top=1,i=y,z=fa[y];sta[1]=y;
while(!isroot(i,2)) sta[++top]=i=fa[i];
while(top) pushdown(sta[top--]);
setson(z,pos(y),child(y,pos(x)^1)),splay(z,2);
ru[++rub]=y;
}
else ch[y][pos(x)]=0,splay(y);
fa[x]=0;
return;
}
int vf(int x){//vistual father
splay(x);
if(!fa[x]) return 0;
if(!in[fa[x]]) return fa[x];
int t=fa[x];
splay(t,2);
return fa[t];
}
int access(int x){//access
int y=0;
for(;x;y=x,x=vf(x)){
splay(x),del(y);
add(x,R(x));
setson(x,1,y),update(x);
}
return y;
}
int lca(int x,int y){//lca
access(x);
return access(y);
}
int root(int x){//root of tree
access(x),splay(x);
while(L(x)) x=L(x);
return x;
}
void makeroot(int x){//mk root
access(x),splay(x),giverev(x);
return;
}
void link(int x,int y){//link
makeroot(x),add(y,x),access(x);
return;
}
void cut(int x){//cut x -> x'fa
access(x),splay(x),pushdown(x);
fa[L(x)]=0,L(x)=0,update(x);
return;
}
void changechain(int x,int y,flag p){
makeroot(x),access(y),splay(y);
tagchain(y,p);return;
}
info askchain(int x,int y){
makeroot(x),access(y);
splay(y);return csum[y];
}
void changetree(int x,flag p){
access(x),splay(x);
val[x]=atag(val[x],p);
rep(i,2,4) if(ch[x][i]) tagtree(ch[x][i],p,1);
update(x),splay(x);
return;
}
info asktree(int x){
access(x),splay(x);
info t=info(val[x]);
rep(i,2,4) if(ch[x][i]) t=t+asum[ch[x][i]];
return t;
}
void read(int &x){
x=0;int c=getchar();bool flag=false;
while(c<'0'||c>'9'){
if(c=='-') flag=true;
c=getchar();
}
for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
if(flag) x=-x;
return;
}
int main(){
freopen("toptree.in","r",stdin);
freopen("toptree.out","w",stdout);
read(n),read(q),tot=n;
for(int i=1;i<=n;i++) read(val[i]),update(i);
for(int i=1,op,x,y,z;i<=q;i++){
read(op);
switch (op){
case 1:{
read(x),read(y);
link(x,y);
break;
}
case 2:{
read(x),read(y);
if(lca(x,y)==y) cut(x);
else cut(y);
break;
}
case 3:{
read(x),read(z);
changechain(x,x,flag(0,z));
break;
}
case 4:{
read(x),read(y);
printf("%d\n",askchain(x,y).mn);
break;
}
case 5:{
read(z),read(x),read(y);
makeroot(z),printf("%d\n",lca(x,y));
break;
}
case 6:{
read(z),read(x),makeroot(z);
printf("%d\n",asktree(x).size);
break;
}
case 7:{
read(z),read(x),makeroot(z);
printf("%d\n",asktree(x).mn);
break;
}
}
}
return 0;
}