关键词：
思路：
LCT模板；
代码：
#include <bits/stdc++.h> using namespace std; #define maxn 300005 int n,m,val[maxn]; int top,ch[maxn][2],f[maxn],xr[maxn],q[maxn],rev[maxn]; inline void in(int &now) { int if_z=1;now=0; char Cget=getchar(); while(Cget>‘9‘||Cget<‘0‘) { if(Cget==‘-‘) if_z=-1; Cget=getchar(); } while(Cget>=‘0‘&&Cget<=‘9‘) { now=now*10+Cget-‘0‘; Cget=getchar(); } now*=if_z; } inline void updata(int now) { xr[now]=xr[ch[now][0]]^xr[ch[now][1]]^val[now]; } inline void downdata(int now) { int l=ch[now][0],r=ch[now][1]; if(rev[now]) { rev[l]^=1,rev[r]^=1,rev[now]^=1; swap(ch[now][0],ch[now][1]); } } inline bool isroot(int now) { return ch[f[now]][0]!=now&&ch[f[now]][1]!=now; } inline void rotate(int now) { int fa=f[now],ffa=f[fa],l,r; if(ch[fa][0]==now) l=0;else l=1;r=l^1; if(!isroot(fa)) { if(ch[ffa][0]==fa) ch[ffa][0]=now; else ch[ffa][1]=now; } f[now]=ffa,f[fa]=now,f[ch[now][r]]=fa; ch[fa][l]=ch[now][r],ch[now][r]=fa; updata(fa),updata(now); } inline void splay(int now) { top=1,q[top]=now; for(int i=now;!isroot(i);i=f[i]) q[++top]=f[i]; for(int i=top;i;i--) downdata(q[i]); while(!isroot(now)) { int fa=f[now],ffa=f[fa]; if(!isroot(fa)) { if((ch[fa][0]==now)^(ch[ffa][0]==fa)) rotate(now); else rotate(fa); } rotate(now); } } void access(int now) { for(int t=0;now;t=now,now=f[now]) { splay(now); ch[now][1]=t; updata(now); } } void makeroot(int now) { access(now); splay(now); rev[now]^=1; } int find(int now) { access(now); splay(now); while(ch[now][0]) now=ch[now][0]; return now; } void split(int x,int y) { makeroot(x); access(y); splay(y); } void cut(int x,int y) { split(x,y); if(ch[y][0]==x) ch[y][0]=0,f[x]=0; } void link(int x,int y) { makeroot(x); f[x]=y; } int main() { in(n),in(m);int op,x,y,xx,yy; for(int i=1;i<=n;i++) in(val[i]),xr[i]=val[i]; while(m--) { in(op); if(op==0) { in(x),in(y),split(x,y); printf("%d ",xr[y]); } if(op==1) { in(x),in(y),xx=find(x),yy=find(y); if(xx!=yy) link(x,y); } if(op==2) { in(x),in(y),xx=find(x),yy=find(y); if(xx==yy) cut(x,y); } if(op==3) { in(x),in(y); access(x); splay(x); val[x]=y; updata(x); } } }
ac日记——模板普通平衡树（treap/sbt）洛谷p3369
【模板】普通平衡树（Treap/SBT） 思路： 劳资敲了一个多星期； 劳资终于a了； 劳资一直不a是因为一个小错误； 劳资最后看的模板； 劳资现在很愤怒； 劳资不想谈思路！！！ 来，上代码：#include&l... 查看详情
ac日记——模板二分图匹配洛谷p3386
题目背景二分图题目描述给定一个二分图，结点个数分别为n,m，边数为e，求二分图最大匹配数输入输出格式输入格式： 第一行，n,m,e第二至e+1行，每行两个正整数u,v，表示u,v有一条连边 输出格式： 共一行，二分图最... 查看详情
ac日记——[sdoi2010]大陆争霸洛谷p3690
[SDOI2010]大陆争霸 思路： dijkstra模板； 代码：#include<bits/stdc++.h>usingnamespacestd;#definemaxn3005#definelllonglong#definemaxm70002<<2#defineINF1e13structNodeType{llid,dis;booloperator 查看详情
ac日记——文艺平衡树洛谷p3391
文艺平衡树 思路: splay翻转操作模板； 虚拟最左最右端点，然后每次都把l翻转到root，r+2翻转到root的右节点； 然后在r+2的左节点上打标记； 标记需要在旋转，rank，print时下放； 建树需要用完全平衡二叉树... 查看详情
洛谷3690：模板linkcuttree——题解(代码片段)
https://www.luogu.org/problemnew/show/P3690给定n个点以及每个点的权值，要你处理接下来的m个操作。操作有4种。操作从0到3编号。点从1到n编号。0：后接两个整数(x，y)，代表询问从x到y的路径上的点的权值的xor和。保证x到y是联通的。1：... 查看详情
洛谷p3690模板linkcuttree（lct）(代码片段)
题目背景动态树题目描述给定n个点以及每个点的权值，要你处理接下来的m个操作。操作有4种。操作从0到3编号。点从1到n编号。0：后接两个整数(x，y)，代表询问从x到y的路径上的点的权值的xor和。保证x到y是联通的。1：后接两... 查看详情
ac日记——魔方洛谷p2007
魔方 思路： 模拟； 代码：#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>usingnamespacestd;structMFType{intai[4][4];};structMFTypeci[7];intlen;chardone[50 查看详情
ac日记——dynamicranking洛谷p2617
DynamicRanking思路； 可持久化树状数组； 代码：#include<bits/stdc++.h>usingnamespacestd;#definemaxn10005#definemaxtotmaxn*600structQueryType{intl,r,k;charop[4];};structQueryTypequ[maxn];intn,m,ai[maxn],bi 查看详情
ac日记——采花洛谷p2056
采花 思路： 莫队； 代码：#include<bits/stdc++.h>usingnamespacestd;#definemaxn100005intbel[maxn];structQueryType{intl,r,id;booloperator<(constQueryTypepos)const{if(bel[l]==bel[pos.l])returnr&l 查看详情
ac日记——方差洛谷p1471
方差 思路： 线段树； 代码：#include<bits/stdc++.h>usingnamespacestd;#definemaxn100005structTreeNodeType{intl,r,mid,size;doublesum,sum2,flag;inlinevoidupdata(doublex){flag+=x;sum2+=sum*x*2+size*x* 查看详情
ac日记——国王游戏洛谷p1080
国王游戏 思路： 贪心+高精； 代码：#include<bits/stdc++.h>usingnamespacestd;#definemaxn1005structDataType{inta,b,key;booloperator<(constDataTypepos)const{returnkey<pos.key;}};structDataTypeai[m 查看详情
ac日记——逆序对洛谷p1908
逆序对 思路： 线段树水过； 代码：#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>usingnamespacestd;#definemaxn40005#definelllonglonginlinevoidin(int&now){ 查看详情
ac日记——松江1843路洛谷七月月赛
松江1843路 思路： 三分； 代码：#include<bits/stdc++.h>usingnamespacestd;#definemaxn100005#definelllonglongstructDataType{llpi,val,sumval,sumpi;booloperator<(constDataTypepos)const{return 查看详情
ac日记——色板游戏洛谷p1558
色板游戏 思路： sb题； 代码：#include<bits/stdc++.h>usingnamespacestd;#definemaxn100005structTreeNodeType{intl,r,dis,mid,flag;};structTreeNodeTypetree[maxn<<2];intn,m,T,bit[31];inlinevoidin 查看详情
刷题洛谷p3690模板linkcuttree（动态树）(代码片段)
题目背景动态树题目描述给定n个点以及每个点的权值，要你处理接下来的m个操作。操作有4种。操作从0到3编号。点从1到n编号。0：后接两个整数(x，y)，代表询问从x到y的路径上的点的权值的xor和。保证x到y是联通的。1：后接两... 查看详情
ac日记——统计和洛谷p2068
统计和 思路： 水题； 代码：#include<bits/stdc++.h>usingnamespacestd;#definemaxn100005intn,m,tree[maxn];inlinevoidin(int&now){intif_z=1;now=0;charCget=getchar();while(Cget>‘9‘||Cget<‘0‘) 查看详情
ac日记——逃离僵尸岛洛谷p3393
逃离僵尸岛 思路： spfa； 代码：#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>usingnamespacestd;#definemaxn200005#definemaxque1800056#defineINF1e12#define 查看详情
ac日记——背单词洛谷p2353
背单词 思路： KMP+统计前缀和优化； 代码：#include<bits/stdc++.h>usingnamespacestd;#definemaxn1000005intn,m,air[maxn][11],len_,len,bi[maxn],fail[maxn];intlit[11],cnt,ans[maxn];charch[maxn],T[maxn];inli 查看详情