Time Limit: 10000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<iostream> #include<cstdio> #include<cmath> #include<string> #include<queue> #include<algorithm> #include<stack> #include<cstring> #include<vector> #include<list> #include<set> #include<map> using namespace std; #define ll long long #define pi (4*atan(1.0)) #define eps 1e-14 #define bug(x) cout<<"bug"<<x<<endl; const int N=2e5+10,M=1e6+10,inf=1e9+10; const ll INF=1e18+10,mod=2147493647; struct edge{ int v,next; }edge[N<<1]; int head[N<<1],edg,id,n; int fa[N],dep[N],son[N],siz[N]; int a[N],ran[N],top[N],tid[N]; void init() { memset(son,-1,sizeof(son)); memset(head,-1,sizeof(head)); edg=0; id=0; } void add(int u,int v) { edg++; edge[edg].v=v; edge[edg].next=head[u]; head[u]=edg; } void dfs1(int u,int fath,int deep) { fa[u]=fath; siz[u]=1; dep[u]=deep; for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v; if(v==fath)continue; dfs1(v,u,deep+1); siz[u]+=siz[v]; if(son[u]==-1||siz[v]>siz[son[u]]) son[u]=v; } } void dfs2(int u,int tp) { tid[u]=++id; top[u]=tp; ran[tid[u]]=u; if(son[u]==-1)return; dfs2(son[u],tp); for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v; if(v==fa[u])continue; if(v!=son[u]) dfs2(v,v); } } int maxx[N<<2],lazy[N<<2]; void pushup(int pos) { maxx[pos]=max(maxx[pos<<1],maxx[pos<<1|1]); } void pushdown(int pos) { if(lazy[pos]) { lazy[pos<<1]+=lazy[pos]; lazy[pos<<1|1]+=lazy[pos]; maxx[pos<<1]+=lazy[pos]; maxx[pos<<1|1]+=lazy[pos]; lazy[pos]=0; } } void build(int l,int r,int pos) { lazy[pos]=0; if(l==r) { maxx[pos]=a[ran[l]]; return; } int mid=(l+r)>>1; build(l,mid,pos<<1); build(mid+1,r,pos<<1|1); pushup(pos); } void update(int L,int R,int c,int l,int r,int pos) { if(L<=l&&r<=R) { maxx[pos]+=c; lazy[pos]+=c; return; } pushdown(pos); int mid=(l+r)>>1; if(L<=mid) update(L,R,c,l,mid,pos<<1); if(R>mid) update(L,R,c,mid+1,r,pos<<1|1); pushup(pos); } int query(int p,int l,int r,int pos) { if(l==r)return maxx[pos]; pushdown(pos); int mid=(l+r)>>1; if(p<=mid) return query(p,l,mid,pos<<1); else return query(p,mid+1,r,pos<<1|1); } void up(int l,int r,int x) { while(top[l]!=top[r]) { if(dep[top[l]]<dep[top[r]])swap(l,r); update(tid[top[l]],tid[l],x,1,n,1); l=fa[top[l]]; } if(dep[l]<dep[r])swap(l,r); //cout<<tid[r]<<" "<<tid[l]<<" "<<x<<endl; update(tid[r],tid[l],x,1,n,1); } char s[10]; int main() { int m,q; while(~scanf("%d%d%d",&n,&m,&q)) { init(); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=m;i++) { int u,v; scanf("%d%d",&u,&v); add(u,v); add(v,u); } dfs1(1,-1,1); dfs2(1,1); build(1,n,1); while(q--) { scanf("%s",s); if(s[0]==‘Q‘) { int x; scanf("%d",&x); printf("%d\n",query(tid[x],1,n,1)); } else { int l,r,x; scanf("%d%d%d",&l,&r,&x); if(s[0]==‘D‘) x=-x; up(l,r,x); } } } return 0; }
原文:http://www.cnblogs.com/jhz033/p/6351829.html