①并查集
#include<iostream> #include<cstring> #include<cstdio> using namespace std; #define e exit(0) #define re register const int M = 10005; int n,m,fa[M]; inline int fd(){ int s=1,t=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')s=-1;c=getchar();} while(c>='0'&&c<='9'){t=t*10+c-'0';c=getchar();} return s*t; } int find(int x){ if(fa[x] == x) return x; else return fa[x] = find(fa[x]); } int main() { freopen("P3367.in","r",stdin); freopen("P3367.out","w",stdout); n = fd(),m = fd(); for(re int i=1;i<=n;++i) fa[i] = i; for(re int i=1;i<=m;++i){ int c = fd(),x = fd(),y = fd(); if(c == 1){ int fa1 = find(x),fa2 = find(y); fa[fa1] = fa2; } else{ int fa1 = find(x),fa2 = find(y); if(fa1 == fa2) printf("Y "); else printf("N "); } } return 0; }
②一维树状数组.NO1.
#include<iostream> #include<cstring> #include<cstdio> using namespace std; #define e exit(0) #define re register #define LL long long const int M = 500005; int n,m,a[M],tree[M]; inline int fd(){ int s=1,t=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')s=-1;c=getchar();} while(c>='0'&&c<='9'){t=t*10+c-'0';c=getchar();} return s*t; } int lowbit(int x){return x&(-x);} void add(int x,int v){ while(x<=n){ tree[x] += v; x += lowbit(x); } } LL getsum(int x){ LL sum = 0; while(x){ sum += tree[x]; x -= lowbit(x); } return sum; } int main() { freopen("P3374.in","r",stdin); freopen("P3374.out","w",stdout); n = fd(),m = fd(); for(re int i=1;i<=n;++i){ a[i] = fd(); add(i,a[i]); } while(m--){ int c = fd(),x = fd(),y = fd(); if(c == 1) add(x,y); else printf("%lld ",getsum(y)-getsum(x-1)); } return 0; }
③一维树状数组.NO2.
#include<iostream> #include<cstring> #include<cstdio> using namespace std; #define e exit(0) #define re register #define LL long long const int M = 5e5+5; int n,m,a[M],cf[M],tree[M]; inline int fd(){ int s=1,t=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')s=-1;c=getchar();} while(c>='0'&&c<='9'){t=t*10+c-'0';c=getchar();} return s*t; } int lowbit(int x){ return x&(-x); } void add(int x,int y){ while(x<=n){ tree[x] += y; x += lowbit(x); } } LL getsum(int x){ LL s = 0; while(x){ s += tree[x]; x -= lowbit(x); } return s; } int main() { freopen("P3368.in","r",stdin); freopen("P3368.out","w",stdout); n = fd(),m = fd(); for(re int i=1;i<=n;++i){ a[i] = fd(); cf[i] = a[i] - a[i-1]; add(i,cf[i]); } while(m--){ int c = fd(); if(c == 1){ int x = fd(),y = fd(),k = fd(); add(x,k),add(y+1,-k); } else{ int x = fd(); printf("%lld ",getsum(x)); } } return 0; }
④线段树.NO1.
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; #define e exit(0) #define re register #define LL long long const LL M = 1e5+5; LL n,m,cnt,a[M]; struct shu{LL l,r,ls,rs,v,tag;}tree[M<<1]; inline LL fd(){ LL s=1,t=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')s=-1;c=getchar();} while(c>='0'&&c<='9'){t=t*10+c-'0';c=getchar();} return s*t; } void build(LL l,LL r){ LL sur = ++cnt; tree[sur].l = l,tree[sur].r = r; if(l != r){ tree[sur].ls = cnt+1; build(l,(l+r)/2); tree[sur].rs = cnt+1; build((l+r)/2+1,r); LL lc = tree[sur].ls,rc = tree[sur].rs; tree[sur].v = tree[lc].v+tree[rc].v; } else tree[sur].v = a[l],tree[sur].tag = 0; } void pushdown(int x){ LL ls = tree[x].ls,rs = tree[x].rs,d = tree[x].tag; tree[ls].v += (tree[ls].r-tree[ls].l+1)*d; tree[rs].v += (tree[rs].r-tree[rs].l+1)*d; tree[ls].tag += d,tree[rs].tag += d; tree[x].tag = 0; } void add(LL k,LL l,LL r,LL d){ if(tree[k].l == l&&tree[k].r == r){ tree[k].v += (tree[k].r-tree[k].l+1)*d; tree[k].tag += d; return; } if(tree[k].tag) pushdown(k); LL mid = (tree[k].l + tree[k].r)>>1; if(r<=mid) add(tree[k].ls,l,r,d); else if(mid<l) add(tree[k].rs,l,r,d); else add(tree[k].ls,l,mid,d),add(tree[k].rs,mid+1,r,d); tree[k].v = tree[tree[k].ls].v+tree[tree[k].rs].v; } LL ask(LL k,LL l,LL r){ if(tree[k].l == l&&tree[k].r == r) return tree[k].v; if(tree[k].tag) pushdown(k); LL mid = (tree[k].l + tree[k].r)>>1; if(r<=mid) return ask(tree[k].ls,l,r); else if(mid<l) return ask(tree[k].rs,l,r); else return (ask(tree[k].ls,l,mid)+ask(tree[k].rs,mid+1,r)); } int main() { freopen("P3372.in","r",stdin); freopen("P3372.out","w",stdout); n = fd(),m = fd(); for(re LL i=1;i<=n;++i) a[i] = fd(); build(1,n); while(m--){ LL c = fd(); if(c == 1){ LL x = fd(),y = fd(),k = fd(); add(1,x,y,k); } else{ LL x = fd(),y = fd(); printf("%lld ",ask(1,x,y)); } } return 0; }
⑤线段树.NO2.
#include<iostream> #include<cstring> #include<cstdio> using namespace std; #define e exit(0) #define re register #define LL long long const int N = 1e5+5; int n,m,cnt,M,a[N]; struct shu{LL l,r,ls,rs,v,tag1,tag2;}tree[N<<1]; inline LL fd(){ LL s=1,t=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')s=-1;c=getchar();} while(c>='0'&&c<='9'){t=t*10+c-'0';c=getchar();} return s*t; } void build(LL l,LL r){ LL sur = ++cnt; tree[sur].l = l,tree[sur].r = r,tree[sur].tag2 = 1; if(l != r){ tree[sur].ls = cnt+1; build(l,(l+r)/2); tree[sur].rs = cnt+1; build((l+r)/2+1,r); LL ls = tree[sur].ls,rs = tree[sur].rs; tree[sur].v = tree[ls].v+tree[rs].v; } else tree[sur].v = a[l]; } void pushdown(LL x){ if(tree[x].tag1||tree[x].tag2 != 1){ LL ls = tree[x].ls,rs = tree[x].rs,d1 = tree[x].tag1,d2 = tree[x].tag2; tree[ls].v = (tree[ls].v*d2%M+(tree[ls].r-tree[ls].l+1)*d1%M)%M; tree[rs].v = (tree[rs].v*d2%M+(tree[rs].r-tree[rs].l+1)*d1%M)%M; tree[ls].tag1 = (tree[ls].tag1*d2%M+d1%M)%M; tree[rs].tag1 = (tree[rs].tag1*d2%M+d1%M)%M; tree[ls].tag2 = (tree[ls].tag2%M*d2%M)%M; tree[rs].tag2 = (tree[rs].tag2%M*d2%M)%M; tree[x].tag1 = 0,tree[x].tag2 = 1; } } void Mul(LL k,LL l,LL r,LL d){ if(tree[k].l == l&&tree[k].r == r){ tree[k].v = (tree[k].v%M*d%M)%M; tree[k].tag1 = (tree[k].tag1%M*d%M)%M; tree[k].tag2 = (tree[k].tag2%M*d%M)%M; return; } pushdown(k); LL mid = (tree[k].l + tree[k].r)>>1; if(r<=mid) Mul(tree[k].ls,l,r,d); else if(mid<l) Mul(tree[k].rs,l,r,d); else Mul(tree[k].ls,l,mid,d),Mul(tree[k].rs,mid+1,r,d); tree[k].v = (tree[tree[k].ls].v%M+tree[tree[k].rs].v%M)%M; } void add(LL k,LL l,LL r,LL d){ if(tree[k].l == l&&tree[k].r == r){ tree[k].v = (tree[k].v%M+(tree[k].r-tree[k].l+1)*d%M)%M; tree[k].tag1 = (tree[k].tag1%M+d%M)%M; return; } pushdown(k); LL mid = (tree[k].l + tree[k].r)>>1; if(r<=mid) add(tree[k].ls,l,r,d); else if(mid<l) add(tree[k].rs,l,r,d); else add(tree[k].ls,l,mid,d),add(tree[k].rs,mid+1,r,d); tree[k].v = (tree[tree[k].ls].v%M+tree[tree[k].rs].v%M)%M; } LL ask(LL k,LL l,LL r){ if(tree[k].l == l&&tree[k].r == r) return tree[k].v%M; pushdown(k); LL mid = (tree[k].l + tree[k].r)>>1; if(r<=mid) return ask(tree[k].ls,l,r)%M; else if(mid<l) return ask(tree[k].rs,l,r)%M; else return (ask(tree[k].ls,l,mid)%M+ask(tree[k].rs,mid+1,r)%M)%M; } int main() { freopen("P3373.in","r",stdin); freopen("P3373.out","w",stdout); n = fd(),m = fd(),M = fd(); for(re LL i=1;i<=n;++i) a[i] = fd(); build(1,n); while(m--){ LL c = fd(); if(c == 1){ LL x = fd(),y = fd(),k = fd(); Mul(1,x,y,k); } else if(c == 2){ LL x = fd(),y = fd(),k = fd(); add(1,x,y,k); } else{ LL x = fd(),y = fd(); printf("%lld ",ask(1,x,y)%M); } } return 0; }