我只是来学区间修改区间查询的ZKW线段树的
大概就是每次修改和查询之前把两端点到根节点上的标记下传一下
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 |
// <4034.cpp> - 09/02/16 19:07:09 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int gi(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=100010; const int MAXM=200010; const int INF=1e9; int bt,b[MAXN],next[MAXM],to[MAXM]; inline void add(int x,int y){ next[++bt]=b[x];b[x]=bt;to[bt]=y; next[++bt]=b[y];b[y]=bt;to[bt]=x; } int lb[MAXN<<2]; int tot,a[MAXN],f[MAXN],son[MAXN],top[MAXN],id[MAXN],size[MAXN],end[MAXN]; void dfs1(int x){ size[x]=1; for(int i=b[x];i;i=next[i]){ if(to[i]==f[x])continue; f[to[i]]=x; dfs1(to[i]); size[x]+=size[to[i]]; if(size[to[i]]>size[son[x]])son[x]=to[i]; } } void dfs2(int x,int t){ top[x]=t; id[x]=++tot; if(son[x])dfs2(son[x],t); for(int i=b[x];i;i=next[i]){ if(to[i]==f[x]||to[i]==son[x])continue; dfs2(to[i],to[i]); } end[x]=tot; } int K; lol val[MAXN<<2],lazy[MAXN<<2]; int st[MAXN]; inline void update(int x){val[x]=val[x<<1]+val[x<<1|1];} inline void pushdown(int x){ int t=0; for(x>>=1;x;x>>=1)st[++t]=x; lol len=K>>1; for(int i=t;i;i--,len>>=1){ if(!lazy[st[i]])continue; val[st[i]<<1]+=len*lazy[st[i]]; val[st[i]<<1|1]+=len*lazy[st[i]]; lazy[st[i]<<1]+=lazy[st[i]]; lazy[st[i]<<1|1]+=lazy[st[i]]; lazy[st[i]]=0; } } void mod(int l,int r,int x){ int ll=l=K+l-1,rr=r=K+r+1; pushdown(ll);pushdown(rr); lol len=1; for(;l^r^1;l>>=1,r>>=1,len<<=1){ if(~l&1)val[l^1]+=x*len,lazy[l^1]+=x; if( r&1)val[r^1]+=x*len,lazy[r^1]+=x; } for(ll>>=1;ll;ll>>=1)update(ll); for(rr>>=1;rr;rr>>=1)update(rr); } lol query(int l,int r){ pushdown(l=K+l-1);pushdown(r=K+r+1); lol res=0; for(;l^r^1;l>>=1,r>>=1){ if(~l&1)res+=val[l^1]; if( r&1)res+=val[r^1]; } return res; } lol ask(int x){ lol res=0; for(;x;x=f[top[x]])res+=query(id[top[x]],id[x]); return res; } int main(){ int n=gi(),m=gi(); for(int i=1;i<=n;i++)a[i]=gi(); for(int i=1;i<n;i++)add(gi(),gi()); dfs1(1); dfs2(1,1); for(int i=2;i<=n<<2;i++)lb[i]=lb[i>>1]+1; K=2<<lb[n+1]; for(int i=1;i<=n;i++)val[K+id[i]]=a[i]; for(int i=K-1;i;i--)update(i); while(m--){ int tp=gi(),x=gi(); if(tp==1)mod(id[x],id[x],gi()); else if(tp==2)mod(id[x],end[x],gi()); else printf("%lld\n",ask(x)); } return 0; } |
说点什么