网站收录需要多久,网站建设功能图,从事网页设计工资高吗,电商网站源码文章目录前言数据结构模板并查集带权并查集堆hash表RMQ线段树树状数组树状数组区间修改版分块主席树有旋TreapSplay替罪羊树文艺平衡树-Splay点分治树链剖分可持久化并查集LCT左偏树前言
因为老是懒得打模板的时候老是扣不到自己的标(因为之前的都打得太丑了)#xff0c;所以…
文章目录前言数据结构模板并查集带权并查集堆hash表RMQ线段树树状数组树状数组区间修改版分块主席树有旋TreapSplay替罪羊树文艺平衡树-Splay点分治树链剖分可持久化并查集LCT左偏树前言
因为老是懒得打模板的时候老是扣不到自己的标(因为之前的都打得太丑了)所以导致我十分的不爽。便打算开一个模板库。会不断更新的 数据结构模板
并查集
int find(int x)//并查集
{return f[x]x?x:(f[x]find(f[x]));}
void unionn(int x,int y)//连接
{int fafind(x),fbfind(y);if(fafb) f[fa]fb;else f[fb]fa;
}带权并查集
int find(int x)
{if (father[x]x) {return x;}else{int fafather[x];father[x]find(father[x]);far[x]far[x]far[fa]0;return father[x];}
}
void unionn(int x,int y,int w)
{int fafind(x),fbfind(y);father[fb]fa;far[fb]far[x]-far[y]w;
}堆
#includecstdio
#includealgorithm
using namespace std;
int a[1000010],num,x,n,v;
void up(int x)
{int t;while (x1 a[x]a[x/2]){ta[x];a[x]a[x/2];a[x/2]t;x/2;}
}
void down(int x)
{int t,y;while (x*2num a[x]a[x*2] || x*21num a[x]a[x*21]){yx*2;if (x*21num a[x*2]a[x*21]) y;ta[x];a[x]a[y];a[y]t;xy;}
}
void insert(int x)
{a[num]x;up(num);}
int main()
{scanf(%d,n);for(int i1;in;i){scanf(%d,v);if(v1){scanf(%d,x);a[num]x;up(num);}else if(v2){printf(%d\n,a[1]);}else{swap(a[1],a[num]);num--;down(1);}}
}hash表
int n,s,hash[maxn10],a[5001];
bool v[maxn10];
int hashmath(int x)
{return (x%maxnmaxn)%maxn;}
int locate(int x)//查找位置
{int i0,whashmath(x);while (imaxnv[(wi)%maxn]hash[(wi)%maxn]!x)i;return (wi)%maxn;
}
void ins(int x)//插入
{int wlocate(x);hash[w]x;v[w]true;
}
bool find(int x)//查找
{int wlocate(x);if (hash[w]xv[w]) return true;else return false;
}RMQ
#includecstdio
#includecmath
//开log用
#includeiostream
using namespace std;
int f[100001][21],n,m,z,x,y;
int main()
{scanf(%d%d,n,m);for (int i1;in;i)scanf(%d,f[i][0]);//输出for (int j1;(1j)n;j)for (int i1;i(1j)-1n;i){f[i][j]max(f[i][j-1],f[i(1j-1)][j-1]);//动态转移}for (int i1;im;i){scanf(%d%d,x,y);z(int)(log(y-x1)/log(2));//计算xprintf(%d\n,max(f[x][z],f[y1-(1z)][z]));//输出}
}线段树
#includecstdio
#includealgorithm
#define N 100010
#define ll long long
using namespace std;
struct treenode{int l,r;ll val,lazy;
}t[N*4];
int n,m,l,r;
ll x;
char c[2];
void build(int x,int l,int r)//建树
{t[x].ll;t[x].rr;if(lr){scanf(%lld,t[x].val);return;}int mid(lr)1;build(x*2,l,mid);build(x*21,mid1,r);t[x].valt[x*2].valt[x*21].val;
}
void downdata(int x)//下传标记
{if(t[x].lazy){t[x*2].lazyt[x].lazy;t[x*2].valt[x].lazy*(t[x*2].r-t[x*2].l1);t[x*21].lazyt[x].lazy;t[x*21].valt[x].lazy*(t[x*21].r-t[x*21].l1);t[x].lazy0;}
}
void change(int x,int l,int r,ll num)//区间修改
{if(t[x].llt[x].rr){t[x].valnum*(t[x].r-t[x].l1);t[x].lazynum;return;}downdata(x);int mid(t[x].lt[x].r)1;if(rmid) change(x*2,l,r,num);else if(lmid) change(x*21,l,r,num);else change(x*2,l,mid,num),change(x*21,mid1,r,num);t[x].valt[x*2].valt[x*21].val;
}
ll find(int x,int l,int r)//区间查询
{if(t[x].llt[x].rr)return t[x].val;downdata(x);int mid(t[x].lt[x].r)1;if(rmid) return find(x*2,l,r);else if(lmid) return find(x*21,l,r);else return find(x*2,l,mid)find(x*21,mid1,r);
}
int main()
{scanf(%d%d,n,m);build(1,1,n);for(int i1;im;i){scanf(%s %d %d,c,l,r);if(c[0]Q) printf(%lld\n,find(1,l,r));else{scanf(%lld,x);change(1,l,r,x);}}
}树状数组
int lowbit(int x)
{return x(x^(x-1));}
void change(int x,int num)//修改
{int ix;while(i82000){c[i]num;ilowbit(i);}
}
int getsum(int x)//求值
{int sum0;while (x0){sumc[x];x-lowbit(x);}return sum;
}树状数组区间修改版
#includecstdio
#includealgorithm
#includeiostream
#define lobit(x) x-x
using namespace std;
long long t[2][100010],x,a[100010],sum[100010];
int n,m,l,r;
void add(int k,int x,int num)//修改
{while(xn){t[k][x]num;xlobit(x);}
}
long long ask(int k,int x)//查询
{long long sum0;while(x0){sumt[k][x];x-lobit(x);}return sum;
}
int main()
{scanf(%d%d,n,m);for(int i1;in;i){scanf(%lld,a[i]);sum[i]sum[i-1]a[i];}for(int i1;im;i){char c[2];scanf(%s %d %d,c,l,r);if(c[0]Q){long long anssum[r](r1)*ask(0,r)-ask(1,r);ans-sum[l-1]l*ask(0,l-1)-ask(1,l-1);//查询printf(%lld\n,ans);}else{scanf(%d,x);add(0,l,x);add(0,r1,-x);add(1,l,l*x);add(1,r1,-(r1)*x);//修改}}
}分块
#includecstdio
#includealgorithm
#includecmath
#define ll long long
#define N 100010
using namespace std;
ll a[N],sum[N],add[N];
int L[N],R[N],d;
int pos[N];
int n,m,t,l,r;
char op[3];
void change(int l,int r,long long d)
{int ppos[l],qpos[r];if(pq){for(int il;ir;i) a[i]d;sum[p]d*(r-l1);}//全都在一块中else{for(int ip1;iq-1;i) add[i]d;//维护中间段落for(int il;iR[p];i) a[i]d;sum[p]d*(R[p]-l1);for(int iL[q];ir;i) a[i]d;sum[q]d*(r-L[q]1);//暴力局部修改}
}
ll ask(int l,int r)
{int ppos[l],qpos[r];ll ans0;if(pq){for(int il;ir;i) ansa[i];ansadd[p]*(r-l1);}//全部都在一块中else{for(int ip1;iq-1;i)anssum[i]add[i]*(R[i]-L[i]1);//累加中间段落for(int il;iR[p];i) ansa[i];ansadd[p]*(R[p]-l1);for(int iL[q];ir;i) ansa[i];ansadd[q]*(r-L[q]1);//暴力局部累加}return ans;
}
int main()
{scanf(%d%d,n,m);for(int i1;in;i)scanf(%lld,a[i]);tsqrt(n);for(int i1;it;i){L[i](i-1)*t1;R[i]i*t;}//标记每块左右if(R[t]n) t,L[t]R[t-1]1,R[t]n;//补足尾部for(int i1;it;i)for(int jL[i];jR[i];j){pos[j]i;//表示属于哪个块sum[i]a[j];//计算段落和}for(int i1;im;i){scanf(%s %d %d,op,l,r);if(op[0]C){scanf(%d,d);change(l,r,d);}else printf(%lld\n,ask(l,r));}
}主席树
#includecstdio
#includealgorithm
#define MN 200010
using namespace std;
struct tnode{int w,l,r,ls,rs;
}t[MN5];
int n,m,x,y,k,a[MN],b[MN],root[MN],num,q,w;
int build(int l,int r)//建立一棵空树
{int knum;t[k].ll,t[k].rr;if (lr) return k;int mid(lr)1;t[k].lsbuild(l,mid);t[k].rsbuild(mid1,r);//左右分区return k;//返回编号
}
int addt(int k,int z)//建立一条新链
{int nbnum;t[nb]t[k];t[nb].w;//动态开点if (t[k].lzt[k].rz) return nb;//到达节点int mid(t[k].lt[k].r)1;if (zmid) t[nb].lsaddt(t[k].ls,z);else t[nb].rsaddt(t[k].rs,z);//建立下一个节点return nb;
}
int query(int k1,int k2,int k)//前缀和询问区间
{if (t[k1].lt[k1].r) return t[k1].l;wt[t[k2].ls].w-t[t[k1].ls].w;//计算左子树在这个区间内的数字数量if (kw) return query(t[k1].ls,t[k2].ls,k);else return query(t[k1].rs,t[k2].rs,k-w);//向下询问
}
int main()
{scanf(%d%d,n,m);for (int i1;in;i)scanf(%d,a[i]),b[i]a[i];sort(b1,b1n);//排序离散化1int qunique(b1,b1n)-b-1;//去重离散化root[0]build(1,q);//建立空树for (int i1;in;i){int telower_bound(b1,b1q,a[i])-b;//二分寻找原来的位置root[i]addt(root[i-1],te);//建立一条链}for (int i1;im;i){scanf(%d%d%d,x,y,k);printf(%d\n,b[query(root[x-1],root[y],k)]);//询问区间}
}有旋Treap
#includecstdio
#includealgorithm
#define INF 2147483647/3
#define N 100010
using namespace std;
int n,root;
struct Treap_node{int l[N],r[N];int val[N],dat[N];int cnt[N],size[N];int tot;int New(int new_val){val[tot]new_val;dat[tot]rand();cnt[tot]size[tot]1;return tot;}void Updata(int p){size[p]size[l[p]]size[r[p]]cnt[p];}void Build(){New(-INF);New(INF);root1;r[1]2;Updata(root);}int GetRankByVal(int p,int num){if(p0) return 0;if(numval[p]) return size[l[p]]1;if(numval[p]) return GetRankByVal(l[p],num);return GetRankByVal(r[p],num)size[l[p]]cnt[p];}int GetValByRank(int p,int rank){if (p0) return INF;if(size[l[p]]rank) return GetValByRank(l[p],rank);if(size[l[p]]cnt[p]rank) return val[p];return GetValByRank(r[p],rank-size[l[p]]-cnt[p]);}void zig(int p){int ql[p];l[p]r[q];r[q]p;pq;Updata(r[p]);Updata(p);}void zag(int p){int qr[p];r[p]l[q];l[q]p;pq;Updata(l[p]);Updata(p);}void Insert(int p,int num){if(p0){pNew(num);return;}if(numval[p]){cnt[p];Updata(p);return;}if(numval[p]){Insert(l[p],num);if(dat[p]dat[l[p]]) zig(p);}else{Insert(r[p],num);if(dat[p]dat[r[p]]) zag(p);}Updata(p);}int GetPre(int num){int ans1;int proot;while(p){if(numval[p]){if(l[p]0){pl[p];while(r[p]0) pr[p];ansp;}break;}if(val[p]numval[p]val[ans]) ansp;pnumval[p]?l[p]:r[p];}return val[ans];}int GetNext(int num){int ans2;int proot;while(p){if(numval[p]){if(r[p]0){pr[p];while(l[p]0) pl[p];ansp;}break;}if(val[p]numval[p]val[ans]) ansp;pnumval[p]?l[p]:r[p];}return val[ans];}void Remove(int p,int num){if(p0) return;if(numval[p]){if(cnt[p]1){cnt[p]--;Updata(p);return;}if(l[p]||r[p]){if(r[p]0||dat[l[p]]dat[r[p]])zig(p),Remove(r[p],num);elsezag(p),Remove(l[p],num);Updata(p);}else p0;return;}numval[p]?Remove(l[p],num):Remove(r[p],num);Updata(p);}
}a;
int main()
{a.Build();scanf(%d,n);while(n--){int opt,x;scanf(%d%d,opt,x);switch(opt){case 1:a.Insert(root,x);break;case 2:a.Remove(root,x);break;case 3:printf(%d\n,a.GetRankByVal(root,x)-1);break;case 4:printf(%d\n,a.GetValByRank(root,x1));break;case 5:printf(%d\n,a.GetPre(x));break;case 6:printf(%d\n,a.GetNext(x));break;}}
}Splay
#includecstdio
#includealgorithm
#define INF 2100000000
#define N 100010
using namespace std;
struct splay{int v[N],father[N];int l[N],r[N];int sum[N],recy[N];int n,points;#define root r[0]void Updata(int x){sum[x]sum[l[x]]sum[r[x]]recy[x];}int Identify(int x){return l[father[x]]x?0:1;}void Connect(int x,int f,int son){father[x]f;if(son) r[f]x;else l[f]x;}void Rotate(int x){int yfather[x];int mrootfather[y];int mrootsonIdentify(y);int ysonIdentify(x);int B(yson?l[x]:r[x]);Connect(B,y,yson);Connect(y,x,(yson^1));Connect(x,mroot,mrootson);Updata(y);Updata(x);}void Splay(int at,int to){tofather[to];while(father[at]!to){int upfather[at];if(father[up]to) Rotate(at);else if(Identify(up)Identify(at)){Rotate(up);Rotate(at);}else{Rotate(at);Rotate(at);}}}int CrePoint(int vs,int fathers){n;v[n]vs;father[n]fathers;sum[n]recy[n]1;return n;}void Destory(int x){v[x]l[x]r[x]sum[x]father[x]recy[x]0;if(xn)n--;}int getroot(){return root;}int FindVal(int vs){int nowroot;if(!now) return 0;while(true){if(v[now]vs){Splay(now,root);return root;}int nextvsv[now]?0:1;if(!(next?r[now]:l[now])) return 0;now(next?r[now]:l[now]);}}int Build(int vs){points;if(!n){root1;CrePoint(vs,0);}else{int nowroot;while(1){sum[now];if(vsv[now]){recy[now];return now;}int nextvsv[now]?0:1;if(!(next?r[now]:l[now])){CrePoint(vs,now);if(next) r[now]n;else l[now]n;return n;}nownext?r[now]:l[now];}}return 0;}void Insert(int vs){int addBuild(vs);Splay(add,root);}void Remove(int vs){int dealFindVal(vs);if(!deal) return;points--;if(recy[deal]1){recy[deal]--;sum[deal]--;return;}if(!l[deal]){rootr[deal];father[root]0;}else{int lefl[deal];while(r[lef]) lefr[lef];Splay(lef,l[deal]);int rigr[deal];Connect(rig,lef,1);Connect(lef,0,1);Updata(lef);}Destory(deal);}int GetRankByVal(int vs){int nowroot;if(!now) return 0;while((vsv[now]?r[now]:l[now])vs!v[now])now(vsv[now]?r[now]:l[now]);Splay(now,root);return sum[l[root]];}int GetValByRank(int x){if(xpoints) return -INF;int nowroot;while(1){int minusedsum[now]-sum[r[now]];if(xsum[l[now]]xminused) break;if(xminused)nowl[now];else{x-minused;nowr[now];}}Splay(now,root);return v[now];}int Upper(int vs){int nowroot;int resultINF;while(now){if(v[now]vsv[now]result) resultv[now];if(vsv[now]) nowl[now];else nowr[now];}return result;}int Lower(int vs){int nowroot;int result-INF;while(now){if(v[now]vsv[now]result) resultv[now];if(vsv[now]) nowr[now];else nowl[now];}return result;}#undef root
}a;
int main(){freopen(testdata.in,r,stdin);freopen(data.out,w,stdout);a.Insert(-INF);a.Insert(INF);int m;scanf(%d,m);while(m--){int opt,x;scanf(%d%d,opt,x);if(opt1) a.Insert(x);if(opt2) a.Remove(x);if(opt3) printf(%d\n,a.GetRankByVal(x));if(opt4) printf(%d\n,a.GetValByRank(x1));if(opt5) printf(%d\n,a.Lower(x));if(opt6) printf(%d\n,a.Upper(x));}
}替罪羊树
#includecstdio
#includealgorithm
#includecctype
#define alpha 0.8
#define N 100010
using namespace std;
inline int read(){int x(0),sign(0);char chgetchar();while(!isdigit(ch)){if(ch-) sign1;chgetchar();}while(isdigit(ch)) x(x3)(x1)(ch^48),chgetchar();return sign?-x:x;
}
struct goat_Tree{int l[N],r[N],size[N],val[N],valid[N],total[N];int cur[N],memory[N];bool exist[N];int root,poi,pool,cnt;void ReMemory(){for(int iN-10;i1;i--)memory[pool]i;}bool Isbad(int now){if((double)valid[now]*alpha(double)max(valid[l[now]],valid[r[now]]))return true;else return false;}void Beat(int now){if(!now) return;Beat(l[now]);if(exist[now]) cur[poi]now;else memory[pool]now;Beat(r[now]);}void New(int x){l[x]r[x]0;total[x]valid[x]1;}void Build(int ls,int rs,int now){int mid(lsrs)1;nowcur[mid];if(lsrs){New(now);return;}if(lsmid) Build(ls,mid-1,l[now]);else l[now]0;Build(mid1,rs,r[now]);total[now]total[l[now]]total[r[now]]1;valid[now]valid[l[now]]valid[r[now]]1;}void ReBuild(int now){poi0;Beat(now);if(poi) Build(1,poi,now);else now0;}int GetRankByVal(int k){int nowroot;int ans1;while(now){if(val[now]k) nowl[now];else{ansvalid[l[now]]exist[now];nowr[now];}}return ans;}int GetValByRank(int k){int nowroot;while(now){if(exist[now]valid[l[now]]1k)return val[now];if(valid[l[now]]k) nowl[now];else{k-valid[l[now]]exist[now];nowr[now];}}}void Insert(int now,int num){if(!now){nowmemory[pool--];val[now]num;New(now);exist[now]1;return;}total[now];valid[now];if(val[now]num) Insert(l[now],num);else Insert(r[now],num);if(Isbad(now))ReBuild(now);}void Remove_z(int now,int tar){if(exist[now]valid[l[now]]1tar){exist[now]0;valid[now]--;return;}valid[now]--;if(valid[l[now]]exist[now]tar)Remove_z(l[now],tar);else Remove_z(r[now],tar-valid[l[now]]-exist[now]);}void Remove(int tar){Remove_z(root,GetRankByVal(tar));if((double)total[root]*alphavalid[root])ReBuild(root);}
}a;
int main()
{int opt,x,m;a.ReMemory();scanf(%d,m);while(m--){optread();xread();if(opt1) a.Insert(a.root,x);if(opt2) a.Remove(x);if(opt3) printf(%d\n,a.GetRankByVal(x));if(opt4) printf(%d\n,a.GetValByRank(x));if(opt5) printf(%d\n,a.GetValByRank(a.GetRankByVal(x)-1));if(opt6) printf(%d\n,a.GetValByRank(a.GetRankByVal(x1)));}
}
文艺平衡树-Splay
#includecstdio
#includealgorithm
#define INF 2100000000
#define N 100010
using namespace std;
struct splay{int v[N],father[N],root;int l[N],r[N];int sum[N],mark[N];int n,points;void Updata(int x){sum[x]sum[l[x]]sum[r[x]]1;}void Downdata(int x){if(mark[x]){mark[l[x]]^1;mark[r[x]]^1;mark[x]0;swap(l[x],r[x]);}}void New(int x,int vs,int fa){l[x]r[x]0;sum[x]1;v[x]vs;father[x]fa;}void Rotate(int x){int yfather[x];int zfather[y];int kr[y]x;if(r[z]y) r[z]x;else l[z]x;father[x]z;if(k) r[y]l[x];else l[y]r[x];father[k?l[x]:r[x]]y;if(k) l[x]y;else r[x]y;father[y]x;Updata(y);Updata(x);}void Splay(int at,int to){while(father[at]!to){int yfather[at];int zfather[y];if(z!to)(r[z]y)^(r[z]at)?Rotate(at):Rotate(y);Rotate(at);}if(to0)rootat;}void Insert(int x){int nowroot,ff0;while(now)ffnow,now(xv[now]?r[now]:l[now]);nown;if(ffxv[now]) r[ff]now;else if(ff) l[ff]now;New(now,x,ff);Splay(now,0);}int GetValByRank(int k){int nowroot;while(1){Downdata(now);if(sum[l[now]]k) nowl[now];else if(sum[l[now]]1k) return now;else k-sum[l[now]]1,nowr[now];}}void Work(int ls,int rs){lsGetValByRank(ls);rsGetValByRank(rs2);Splay(ls,0);Splay(rs,ls);mark[l[r[root]]]^1;}void Write(int x,int mn){Downdata(x);if(l[x]) Write(l[x],mn);if(v[x]1v[x]mn2) printf(%d ,v[x]-1);if(r[x]) Write(r[x],mn);}
}a;
int main(){//freopen(testdata.in,r,stdin);//freopen(data.out,w,stdout);int n,m;scanf(%d%d,n,m);for(int i1;in2;i)a.Insert(i);while(m--){int l,r;scanf(%d%d,l,r);a.Work(l,r);}a.Write(a.root,n);
}
点分治
#includecstdio
#includealgorithm
#includecstring
#define N 100010
#define inf 10000000
using namespace std;
struct node{int to,next,w;
}a[N*2];
int n,m,que[1010],ok[inf],tot,sum,num,q[N];
int root,siz[N],f[N],ls[N],st[N],dis[N];
int lon[inf];
bool v[N];
void addl(int x,int y,int w)
{a[tot].toy;a[tot].nextls[x];a[tot].ww;ls[x]tot;
}
void groot(int x,int fa)
{siz[x]1;f[x]0;for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa||v[y]) continue;groot(y,x);siz[x]siz[y];f[x]max(f[x],siz[y]);}f[x]max(f[x],sum-siz[x]);if(f[x]f[root]) rootx;
}
void get_dis(int x,int fa)
{st[num]dis[x];for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa||v[y]) continue;dis[y]dis[x]a[i].w;get_dis(y,x);}
}
void calc(int x)
{int p0;for(int ils[x];i;ia[i].next){int ya[i].to;if(v[y]) continue;num0;dis[y]a[i].w;get_dis(y,x);for(int jnum;j;j--)for(int k1;km;k)ok[k]|lon[que[k]-st[j]];for(int jnum;j;j--)q[p]st[j],lon[st[j]]1;}for(int i1;ip;i)lon[q[i]]0;
}
void solve(int x)
{v[x]lon[0]1;calc(x);for(int ils[x];i;ia[i].next){int ya[i].to;if(v[y]) continue;sumsiz[y];f[root0]n;groot(y,0);solve(y);}
}
int main()
{scanf(%d%d,n,m);for(int i1;in;i){int x,y,w;scanf(%d%d%d,x,y,w);addl(x,y,w);addl(y,x,w);}for(int i1;im;i)scanf(%d,que[i]);f[0]n;sumn;groot(1,0);solve(root);for(int i1;im;i)if(ok[i]) printf(AYE\n);else printf(NAY\n);
} 树链剖分
#includecstdio
#includealgorithm
using namespace std;
const int N200000;
int tot,cnt,n,m,s,p,ls[N],pw[N],id[N];
int siz[N],dep[N],f[N],son[N],seg[N],top[N];
struct treenode{int l,r,lazy,val;
};
struct LineTree{treenode t[N*2];void build(int x,int l,int r){t[x].ll;t[x].rr;if(lr){t[x].valpw[id[l]]%p;return;}int mid(lr)1;build(x*2,l,mid);build(x*21,mid1,r);t[x].val(t[x*2].valt[x*21].val)%p;}void downdata(int x){if(t[x].lazy){(t[x*2].lazyt[x].lazy)%p;(t[x*2].valt[x].lazy*(t[x*2].r-t[x*2].l1))%p;(t[x*21].lazyt[x].lazy)%p;(t[x*21].valt[x].lazy*(t[x*21].r-t[x*21].l1))%p;t[x].lazy0;}}void change(int x,int l,int r,int num){if(t[x].llt[x].rr){(t[x].valnum*(t[x].r-t[x].l1))%p;(t[x].lazynum)%p;return;}downdata(x);int mid(t[x].lt[x].r)1;if(rmid) change(x*2,l,r,num);else if(lmid) change(x*21,l,r,num);else change(x*2,l,mid,num),change(x*21,mid1,r,num);t[x].val(t[x*2].valt[x*21].val)%p;}int find(int x,int l,int r){if(t[x].llt[x].rr)return t[x].val;downdata(x);int mid(t[x].lt[x].r)1;if(rmid) return find(x*2,l,r);else if(lmid) return find(x*21,l,r);else return (find(x*2,l,mid)find(x*21,mid1,r))%p; }
}LT;
struct edge_node{int to,next;
}a[N*2];
void addl(int x,int y)
{a[tot].toy;a[tot].nextls[x];ls[x]tot;
}
void dfs1(int x,int fa)
{siz[x]1;for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa) continue;dep[y]dep[x]1;f[y]x;dfs1(y,x);siz[x]siz[y];if(siz[y]siz[son[x]])son[x]y;}
}
void dfs2(int x,int fa)
{seg[x]cnt;id[cnt]x;if(son[x]){top[son[x]]top[x];dfs2(son[x],x);}for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa||yson[x]) continue;top[y]y;dfs2(y,x);}
}
void path_change(int x,int y,int z)
{while(top[x]!top[y]){if(dep[top[x]]dep[top[y]]) swap(x,y);LT.change(1,seg[top[x]],seg[x],z);xf[top[x]];}if(dep[x]dep[y]) swap(x,y);LT.change(1,seg[x],seg[y],z);return;
}
int path_ask(int x,int y)
{int ans0;while(top[x]!top[y]){if(dep[top[x]]dep[top[y]]) swap(x,y);(ansLT.find(1,seg[top[x]],seg[x]))%p;xf[top[x]];}if(dep[x]dep[y]) swap(x,y);(ansLT.find(1,seg[x],seg[y]))%p;return ans;
}
int main()
{scanf(%d%d%d%d,n,m,s,p);for(int i1;in;i)scanf(%d,pw[i]);for(int i1;in;i){int x,y;scanf(%d%d,x,y);addl(x,y);addl(y,x);}dfs1(s,0);top[s]s;dfs2(s,0);LT.build(1,1,n);for(int i1;im;i){int t,x,y,z;scanf(%d%d,t,x);if(t1){scanf(%d%d,y,z);path_change(x,y,z);}if(t2){scanf(%d,y);printf(%d\n,path_ask(x,y));}if(t3){scanf(%d,z);LT.change(1,seg[x],seg[x]siz[x]-1,z);}if(t4){printf(%d\n,LT.find(1,seg[x],seg[x]siz[x]-1));}}
}可持久化并查集
// luogu-judger-enable-o2
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N2e5100;
struct Tree_node{int ls,rs,l,r,deep,fa;
};
int n,m,cnt,root[N],edt;
struct Keep_tree{Tree_node t[N*40];void Build(int x,int l,int r){xcnt;t[x].ll;t[x].rr;if(lr){t[x].fal;return;}int mid(t[x].lt[x].r)/2;Build(t[x].ls,l,mid);Build(t[x].rs,mid1,r);}Tree_node Query(int x,int pos){if(t[x].lt[x].r)return t[x];if(post[t[x].ls].r) return Query(t[x].ls,pos);return Query(t[x].rs,pos);}void Insert(int x,int y,int pos,int nef){ycnt;t[y]t[x];if(t[x].lt[x].r){t[y].fanef;return;}if(post[t[x].ls].r) Insert(t[x].ls,t[y].ls,pos,nef);else Insert(t[x].rs,t[y].rs,pos,nef);}void add(int x,int pos){if(t[x].lt[x].r){t[x].deep;return;}if(post[t[x].ls].r) add(t[x].ls,pos);else add(t[x].rs,pos);}
}Tree;
Tree_node find_fa(int ed,int x)
{Tree_node FaTree.Query(root[ed],x);if(xFa.fa) return Fa;return find_fa(ed,Fa.fa);
}
void unionn(int x,int y)
{Tree_node Fafind_fa(edt-1,x),Fbfind_fa(edt-1,y);if(Fa.faFb.fa) return;if(Fa.deepFb.deep) swap(Fa,Fb);Tree.Insert(root[edt-1],root[edt],Fb.fa,Fa.fa);if(Fa.deepFb.deep)Tree.add(root[edt],Fa.fa);
}
int main()
{scanf(%d%d,n,m);Tree.Build(root[0],1,n);for(int i1;im;i){int op,x,y;scanf(%d,op);edt;root[edt]root[edt-1];if(op1){scanf(%d%d,x,y);unionn(x,y);}if(op2){scanf(%d,x);root[edt]root[x];}if(op3){scanf(%d%d,x,y);if(find_fa(edt,x).fafind_fa(edt,y).fa) printf(1);else printf(0);putchar(\n);}}
}LCT
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N3e5100;
int n,m,v[N];
struct Link_Cut_Tree{int w[N],fa[N],son[N][2];bool r[N];#define ls son[x][0]#define rs son[x][1]bool nroot(int x){return son[fa[x]][0]x||son[fa[x]][1]x;}void PushUp(int x){w[x]w[ls]^w[rs]^v[x];return;}void PushR(int x){swap(ls,rs);r[x]^1;return;}void PushDown(int x){if(r[x]){if(ls) PushR(ls);if(rs) PushR(rs);r[x]0;}return;}void Rotate(int x){int yfa[x],zfa[y],k(son[y][1]x),wson[x][!k];if(nroot(y)) son[z][son[z][1]y]x;son[x][!k]y;son[y][k]w;if(w) fa[w]y;fa[y]x;fa[x]z;PushUp(y);return;}void PushHall(int x){if(nroot(x)) PushHall(fa[x]);PushDown(x); return;}void Splay(int x){int yx,z0;PushHall(x);while(nroot(x)){yfa[x];zfa[y];if(nroot(y))Rotate((son[y][0]x)^(son[z][0]y)?x:y);Rotate(x);} PushUp(x);return;}void Access(int x){for(int y0;x;xfa[yx])Splay(x),rsy,PushUp(x);return;}void MakeRoot(int x){Access(x);Splay(x);PushR(x);return;}int FindRoot(int x){Access(x);Splay(x);while(ls) PushDown(x),xls;Splay(x);return x;}void Split(int x,int y){MakeRoot(x);Access(y);Splay(y);return;}void Link(int x,int y){MakeRoot(x);if(FindRoot(y)!x) fa[x]y;}void Cut(int x,int y){MakeRoot(x);if(FindRoot(y)xfa[y]x!son[y][0]){fa[y]son[x][1]0;PushUp(x);} }#undef ls#undef rs
}LCT;
int main()
{scanf(%d%d,n,m);for(int i1;in;i)scanf(%d,v[i]);while(m--){int op,x,y;scanf(%d%d%d,op,x,y);if(op0){LCT.Split(x,y);printf(%d\n,LCT.w[y]);}if(op1){LCT.Link(x,y);}if(op2){LCT.Cut(x,y);}if(op3){LCT.Splay(x);v[x]y;}}
} 左偏树
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N1e510;
int n,m,val[N];
struct Left_tree{int dis[N],fa[N],t[N][2];int Merge(int x,int y){if(!x||!y) return xy;if(val[x]val[y]||(val[x]val[y]xy))swap(x,y);int lst[x][0],rst[x][1];rsMerge(rs,y);if(dis[ls]dis[rs]) swap(ls,rs);fa[rs]fa[ls]x;dis[x]dis[rs]1;return x;}void Del(int x){int lst[x][0],rst[x][1];fa[ls]ls;fa[rs]rs;val[x]-1;fa[x]Merge(ls,rs);}int Get(int x){return (fa[x]x)?(x):(fa[x]Get(fa[x]));}
}T;
int main()
{scanf(%d%d,n,m);for(int i1;in;i)scanf(%d,val[i]),T.fa[i]i;while(m--){int op,x,y;scanf(%d%d,op,x);if(op1){scanf(%d,y);if(val[x]-1||val[y]-1)continue;xT.Get(x);yT.Get(y);T.Merge(x,y);}if(op2){if(val[x]-1){printf(-1\n);continue;}xT.Get(x);printf(%d\n,val[x]);T.Del(x);}}
}
