3
8
2016
5

BZOJ3282lct模板存档

终于调出了真正意义上的第一道LCT

所以说不要在意块状链表shi的弹飞绵羊

所以说不要在意并查集shi的洞穴勘测

所以说又要开始贴模板的没羞没臊的生活了

因为写access的时候只是看了定义然后自己yy的没有参考神犇的代码所以写得超级丑Orz,然后很多地方估计让R爷看了也是要被婊翻的。不过跑得好像还不错显然是R爷快啊Orz

我好像还不会写指针Orz

 

#include<cstdio>
#include<algorithm>
using namespace std;
struct tree{
    int l,r,xo,fa,s;
    bool re;
}t[300005];
int n,m,flag,x,y,fa[300005];
inline int read(){
    int ret=0;
    char c=getchar();
    while((c>'9')||(c<'0'))c=getchar();
    while((c>='0')&&(c<='9'))ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
    return ret;
}
void pushdown(int root){
    if(t[root].re){
        swap(t[root].l,t[root].r);
        if(t[root].l)t[t[root].l].re^=true;
        if(t[root].r)t[t[root].r].re^=true;
        t[root].re=false;
    }
}
void pushup(int root){t[root].xo=t[t[root].l].xo^t[t[root].r].xo^t[root].s;}
void rorate(int k,int i){
    int tmp=t[k].fa;
    if(fa[tmp]){fa[k]=fa[tmp];fa[tmp]=0;}
    t[k].fa=t[tmp].fa;
    if(t[t[tmp].fa].l==tmp)t[t[tmp].fa].l=k;
    else t[t[tmp].fa].r=k;
    t[tmp].fa=k;
    if(i==0){
        if(t[k].l>0)t[t[k].l].fa=tmp;
        t[tmp].r=t[k].l;t[k].l=tmp;
    }else{
        if(t[k].r>0)t[t[k].r].fa=tmp;
        t[tmp].l=t[k].r;t[k].r=tmp;
    }
    pushup(tmp);pushup(k);
}
void splay(int k){
    while(t[k].fa){
        int tmp=t[k].fa;
        if(t[tmp].fa==0){
            pushdown(tmp);pushdown(k);
            if(t[tmp].r==k)rorate(k,0);
            else rorate(k,1);
        }
        else{
            int Tmp=t[tmp].fa;
            pushdown(Tmp);pushdown(tmp);pushdown(k);
            if(t[Tmp].l==tmp){
                if(t[tmp].l==k)rorate(tmp,1);
                else rorate(k,0);
                rorate(k,1);
            }else{
                if(t[tmp].r==k)rorate(tmp,0);
                else rorate(k,1);
                rorate(k,0);
            }
        }
    }
}
void access(int p){
    splay(p);
    pushdown(p);
    if(t[p].r){
        fa[t[p].r]=p;
        t[t[p].r].fa=0;t[p].r=0;
        pushup(p);
    }
    while(fa[p]){
        splay(fa[p]);
        pushdown(fa[p]);
        t[p].fa=fa[p];
        if(t[fa[p]].r){
            fa[t[fa[p]].r]=fa[p];
            t[t[fa[p]].r].fa=0;
        }
        t[fa[p]].r=p;
        fa[p]=0; 
        pushup(t[p].fa);
        splay(p);
    }
}
void change_root(int x){access(x);t[x].re^=1;}
void link(int x,int y){
    change_root(x);
    fa[x]=y;
}
void cut(int x,int y){change_root(x);access(y);if(t[y].l==x)t[y].l=t[x].fa=0,pushup(y);}
inline int find(int p){for(pushdown(p),access(p);t[p].l;p=t[p].l);return p;}
int main(){
    n=read();m=read();
    for(int i=1;i<=n;i++)t[i].s=t[i].xo=read();
    for(int i=1;i<=m;i++){
        flag=read();x=read();y=read();
        if(flag==0){
            change_root(x);            access(y);
            printf("%d\n",t[y].xo);
        }
        if(flag==1)if(find(x)!=find(y))link(x,y);
        if(flag==2)if(find(x)==find(y))cut(x,y);
        if(flag==3){
            t[x].s=y;
            while(x)pushup(x),x=t[x].fa;
        }
    }
}

--------------------------------------------------------------------------------------------------

#include<cstdio>
#include<algorithm>
using namespace std;
struct tree{
	int l,r,fa,max,w;
	bool re; 
}t[150005];
struct edge{
	int u,v,a,b;
}e[100005];
int ans,n,m,cnt;
inline int read(){
    int ret=0;
    char c=getchar();
    while((c>'9')||(c<'0'))c=getchar();
    while((c>='0')&&(c<='9'))ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
    return ret;
}
inline bool cmp(edge e1,edge e2){return e1.a<e2.a;}
void pushdown(int k){
	if(t[k].re){
		swap(t[k].l,t[k].r);
		if(t[k].l)t[t[k].l].re^=1;
		if(t[k].r)t[t[k].r].re^=1;
		t[k].re=false;
	}
}
void pushup(int k){
	t[k].max=k;
	if(t[k].l)if(t[t[t[k].l].max].w>t[t[k].max].w)t[k].max=t[t[k].l].max;
	if(t[k].r)if(t[t[t[k].r].max].w>t[t[k].max].w)t[k].max=t[t[k].r].max;
}
void rorate(int k,int i){
	int tmp=t[k].fa;
	t[k].fa=t[tmp].fa;
	if(t[t[tmp].fa].l==tmp)t[t[tmp].fa].l=k;
	if(t[t[tmp].fa].r==tmp)t[t[tmp].fa].r=k;
	t[tmp].fa=k;
	if(i==0){
		if(t[k].l)t[t[k].l].fa=tmp;
		t[tmp].r=t[k].l;t[k].l=tmp;
	}
	else{
		if(t[k].r)t[t[k].r].fa=tmp;
		t[tmp].l=t[k].r;t[k].r=tmp;
	}
	pushup(tmp);pushup(k);
}
void splay(int k){
	while((t[t[k].fa].l==k)||(t[t[k].fa].r==k)){
		int tmp=t[k].fa;
		if((t[t[tmp].fa].l!=tmp)&&(t[t[tmp].fa].r!=tmp)){
			pushdown(tmp);pushdown(k);
			if(t[tmp].l==k)rorate(k,1);
			else rorate(k,0);
		}else{
			int Tmp=t[tmp].fa;
			pushdown(Tmp);pushdown(tmp);pushdown(k);
			if(t[Tmp].l==tmp){
				if(t[tmp].l==k)rorate(tmp,1);
				else rorate(k,0);
				rorate(k,1);
			}else{
				if(t[tmp].r==k)rorate(tmp,0);
				else rorate(k,1);
				rorate(k,0);
			}
		}
	}
}
void access(int k){
	splay(k);pushdown(k);t[k].r=0;pushup(k);
	while(t[k].fa){
		splay(t[k].fa);
		pushdown(t[k].fa);
		t[t[k].fa].r=k;
		pushup(t[k].fa);
		splay(k); 
	}
}
void change_root(int x){access(x);t[x].re^=1;}
void cut(int x,int y){change_root(x);access(y);t[x].r=0;t[y].fa=0;pushup(x);}
void link(int x,int y){change_root(x);t[x].fa=y;}
inline int find(int k){access(k);while(t[k].l)k=t[k].l;return k;}
inline int qmax(int x,int y){change_root(x);access(y);return t[y].max;}
void Link(int x,int y,int w){
	cnt++;
	t[cnt].w=w;
	link(x,cnt);
	link(y,cnt);
}
void work(int x,int y){
	int k=qmax(x,y);change_root(k);
	access(x);splay(k);t[t[k].r].fa=0;t[k].r=0;
	access(y);splay(k);t[t[k].r].fa=0;t[k].r=0;
}
int main(){
	n=read();m=read();
	for(int i=1;i<=m;i++)e[i].u=read(),e[i].v=read(),e[i].a=read(),e[i].b=read();
	sort(e+1,e+1+m,cmp);
	ans=2000000;
	cnt=n;
	for(int i=1;i<=m;i++){
		if(find(e[i].u)==find(e[i].v)){
			if(t[qmax(e[i].u,e[i].v)].w>e[i].b){
				work(e[i].u,e[i].v);
				Link(e[i].u,e[i].v,e[i].b);
			}
		}else Link(e[i].u,e[i].v,e[i].b);
		if(find(1)==find(n))ans=min(e[i].a+t[qmax(1,n)].w,ans);
	}
	if(ans==2000000)printf("-1");
	else printf("%d",ans);
}
Category: 存档 | Tags: 模板 LCT bzoj | Read Count: 1353
Avatar_small
对面的clc 说:
2016年3月12日 14:49

这里有诋毁您的言论,还有python交易:zhaoleyi.github.io

Avatar_small
对面的zly 说:
2016年3月12日 14:53

@对面的clc: 以上是正解

Avatar_small
对面的clc 说:
2016年3月12日 15:53

using namespace std可以加速程序运行吗?——我们机房的Z大牛说的

Avatar_small
hzq84621 说:
2016年3月14日 08:07

@对面的clc: 你不写using namespace std;就会CE我刚转C++经常干这个事

Avatar_small
AP SSC Social Model 说:
2022年9月19日 00:35

Social Study is most important students to all students of AP 10th Class, here we have provided the study material with solved question bank for all government and private school TM, EM, UM and HM students in chapter wise from past years old exams and we have provided the AP 10th Social Model Paper 2023 Pdf suggested by subject experts. AP SSC Social Model Paper All BSEAP 10th class regular and private course students can follow the list of chapters under SSC Social Study to practice study material with previous question bank to get a better score in summative assessment (SA) and formative assessment (FA) SA-1, SA-2, FA-1, FA-2, FA-3, FA-4 along with Assignments exams previously called Unit Test-1, Unit Test-2, Unit Test-3, Unit Test-4 and Three Months.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com