某谷树剖模板
#include<bits/stdc++.h> using namespace std; #define ll long long #define ull unsigend long long #define rep(k,i,j) for(int k = i;k <= j; ++k) #define FOR(k,i,j) for(int k = i;k >= j; --k) inline int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0'; ch=getchar();} return x*f; } const int mxn = 2e5+10; int n,m,root,p; int tp[mxn],fa[mxn],id[mxn],val[mxn],dep[mxn],sz[mxn],link[mxn],son[mxn]; struct edge{int nxt,y;}e[mxn<<1]; struct Tree{int l,r,tag,sum;}tree[mxn<<2]; int len,to[mxn]; int res = 0,cnt; inline void add(int xx,int yy){ e[++len].nxt = to[xx]; to[xx] = len; e[len].y = yy; } inline void pushdown(int pos,int lth){ int tag_ = tree[pos].tag; if(tag_){ tree[pos<<1].tag += tag_; tree[pos<<1|1].tag += tag_; tree[pos<<1].sum += tag_*(lth-(lth>>1)); tree[pos<<1|1].sum += tag_*(lth>>1); tree[pos<<1].sum %= p; tree[pos<<1|1].sum %= p; tree[pos].tag = 0; } } inline void build(int pos,int l,int r){ if(l==r){ tree[pos].sum = link[l]; if(tree[pos].sum > p) tree[pos].sum %= p; return; } int m = l+r >>1; build(pos<<1,l,m),build(pos<<1|1,m+1,r); tree[pos].sum = (tree[pos<<1].sum + tree[pos<<1|1].sum)%p; } inline void query(int pos,int lp,int rp,int l,int r){ if(l<=lp&&rp<=r){ res += tree[pos].sum; res %= p; return; }else{ pushdown(pos,rp-lp+1); int m = lp+rp >>1; if(l<=m) query(pos<<1,lp,m,l,r); if(r>m) query(pos<<1|1,m+1,rp,l,r); } } inline void update(int pos,int lp,int rp,int l,int r,int k){ if(l<=lp&&rp<=r){ tree[pos].tag += k; tree[pos].sum += k*(rp-lp+1); return; } pushdown(pos,rp-lp+1); int m = lp+rp >>1; if(l<=m) update(pos<<1,lp,m,l,r,k); if(r>m) update(pos<<1|1,m+1,rp,l,r,k); tree[pos].sum = (tree[pos<<1].sum+tree[pos<<1|1].sum)%p; } inline int query_2(int x,int y){ int ans = 0; while(tp[x]!=tp[y]){ if(dep[tp[x]]<dep[tp[y]]) swap(x,y); res = 0; query(1,1,n,id[tp[x]],id[x]); ans += res; ans %= p; x = fa[tp[x]]; } if(dep[x]>dep[y]) swap(x,y); res = 0; query(1,1,n,id[x],id[y]); ans += res; return ans%p; } inline void update_1(int x,int y,int k){ k %= p; while(tp[x]!=tp[y]){ if(dep[tp[x]]<dep[tp[y]]) swap(x,y); update(1,1,n,id[tp[x]],id[x],k); x = fa[tp[x]]; } if(dep[x]>dep[y]) swap(x,y); update(1,1,n,id[x],id[y],k); } inline int query_4(int x){ res = 0; query(1,1,n,id[x],id[x]+sz[x]-1); return res; } inline void update_3(int x,int k){ update(1,1,n,id[x],id[x]+sz[x]-1,k); } inline void dfs1(int x,int f,int d){ dep[x] = d,fa[x] = f; sz[x] = 1; int maxson = -1; for(int i = to[x]; i;i = e[i].nxt){ int y = e[i].y; if(y==f) continue; dfs1(y,x,d+1); sz[x] += sz[y]; if(sz[y]>maxson) son[x] = y,maxson = sz[y]; } } inline void dfs2(int x,int topf){ id[x] = ++cnt; link[cnt] = val[x]; tp[x] = topf; if(!son[x]) return; dfs2(son[x],topf); for(int i = to[x]; i;i = e[i].nxt){ int y = e[i].y; if(y==fa[x]||y==son[x]) continue; dfs2(y,y); } } int main(){ n = read(),m = read(),root = read(),p = read(); rep(i,1,n) val[i] = read(); rep(i,1,n-1){ int x = read(),y = read(); add(x,y),add(y,x); } dfs1(root,0,1); dfs2(root,root); build(1,1,n); while(m--){ int opt,x,y,z; opt = read(); if(opt==1){ x = read(),y = read(),z = read(); update_1(x,y,z); }else if(opt==2){ x = read(),y = read(); printf("%d\n",query_2(x,y)); }else if(opt==3){ x = read(),y = read(); update_3(x,y); }else{ x = read(); printf("%d\n",query_4(x)); } } }
某谷最大流模板
#include<bits/stdc++.h> using namespace std; #define File "" #define inf 1<<29 #define ll long long #define ull unsigned long long #define rep(k,i,j) for(int k = i;k <= j; ++k) #define FOR(k,i,j) for(int k = i;k >= j; --k) inline void file(){ freopen(File".in","r",stdin); freopen(File".out","w",stdout); } inline int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0'; ch=getchar();} return x*f; } const int mxn = 1e4+5; const int mxm = 1e5+5; struct edge{int nxt,y,v;}e[mxm<<1]; int to[mxn],len = 1; inline void add(int xx,int yy,int zz){ e[++len].nxt = to[xx]; to[xx] = len; e[len].y = yy; e[len].v = zz; e[++len].nxt = to[yy]; to[yy] = len; e[len].y = xx; e[len].v = 0; } int n,m,s,t,maxflow; int incf[mxn],pre[mxn],v[mxn]; bool bfs(){ memset(v,0,sizeof v); queue<int> q; q.push(s); v[s] = 1; incf[s] = inf; while(q.size()){ int x = q.front(); q.pop(); for(int i = to[x]; i;i = e[i].nxt){ int y = e[i].y,z = e[i].v; if(z){ if(v[y]) continue; incf[y] = min(incf[x],z); pre[y] = i; q.push(y),v[y] = 1; if(y==t) return 1; } } } return 0; } inline void update(){ int x = t; while(x != s){ int i = pre[x]; e[i].v -= incf[t]; e[i^1].v += incf[t]; x = e[i^1].y; } maxflow += incf[t]; } int main(){ // file(); n = read(),m = read(),s = read(),t = read(); maxflow = 0; while(m--){ int x = read(),y = read(),z = read(); add(x,y,z); } while(bfs()) update(); printf("%d\n",maxflow); return 0; }
某谷的线段树模板(1)
#include<bits/stdc++.h> using namespace std; #define File "" #define ll long long inline void file(){ freopen(File".in","r",stdin); freopen(File".out","w",stdout); } inline ll read(){ ll x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0'; ch=getchar();} return x*f; } const int mxn = 1e5+5; int n,m; struct T{ int l,r; ll dat,tg; }tr[mxn<<3]; #define ls p<<1 #define rs p<<1|1 ll a[mxn]; inline void build(int p,int l,int r){ tr[p].l = l,tr[p].r = r; if(l==r){ tr[p].dat = a[l]; return; } int mid = l+r >>1; build(ls,l,mid); build(rs,mid+1,r); tr[p].dat = tr[ls].dat + tr[rs].dat; } inline void push(int p){ ll tg = tr[p].tg; if(tg){ tr[ls].tg += tg; tr[rs].tg += tg; tr[ls].dat += tg*(tr[ls].r-tr[ls].l+1); tr[rs].dat += tg*(tr[rs].r-tr[rs].l+1); tr[p].tg = 0; return; } } inline void update(int p,int l,int r,int k){ if(l <= tr[p].l && tr[p].r <= r){ tr[p].tg += k; tr[p].dat += 1ll*(tr[p].r-tr[p].l +1)*k; return; } push(p); int mid = tr[p].l + tr[p].r >>1; if(l <= mid) update(ls,l,r,k); if(r > mid) update(rs,l,r,k); tr[p].dat = tr[ls].dat + tr[rs].dat; } inline ll ask(int p,int l,int r){ ll ans(0); if(l <= tr[p].l && tr[p].r <= r) return tr[p].dat; push(p); int mid = tr[p].l + tr[p].r >>1; if(l <= mid) ans += ask(ls,l,r); if(r > mid) ans += ask(rs,l,r); return ans; } int main(){ // file(); scanf("%d%d",&n,&m); for(int i = 1;i <= n; ++i) a[i] = read(); build(1,1,n); while(m--){ int opt = read(); if(opt==1){ int x = read(),y = read(),k = read(); update(1,x,y,k); }else{ int x = read(),y = read(); printf("%lld\n",ask(1,x,y)); } } return 0; } /* 5 5 1 5 4 2 3 2 2 4 1 2 3 2 2 3 4 1 1 5 1 2 1 4 */
某谷的线段树模板(2)
某谷的树状数组模板(1)
#include<bits/stdc++.h> using namespace std; #define File "" #define ll long long inline void file(){ freopen(File".in","r",stdin); freopen(File".out","w",stdout); } inline ll read(){ ll x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0'; ch=getchar();} return x*f; } const int mxn = 5e5+5; int n,m; ll c[mxn]; inline ll lowbit(int x){ return x&-x; } inline void update(int x,ll d){ while(x <= n) c[x] += d,x += lowbit(x); } inline ll ask(int x){ ll ans(0); while(x) ans += c[x],x -= lowbit(x); return ans; } int main(){ // file(); n = read(),m = read(); for(int i = 1;i <= n; ++i) update(i,read()); while(m--){ int opt = read(); if(opt==1){ int x = read(),k = read(); update(x,k); }else{ int x = read(),y = read(); printf("%lld\n",ask(y)-ask(x-1)); } } return 0; } /* 5 5 1 5 4 2 3 1 1 3 2 2 5 1 3 -1 1 4 2 2 1 4 */
某谷的树状数组模板(2)
