题目：
Our protagonist is the handsome human prince Aragorn comes from The Lord of the Rings. One day Aragorn finds a lot of enemies who want to invade his kingdom. As Aragorn knows, the enemy has N camps out of his kingdom and M edges connect them. It is guaranteed that for any two camps, there is one and only one path connect them. At first Aragorn know the number of enemies in every camp. But the enemy is cunning , they will increase or decrease the number of soldiers in camps. Every time the enemy change the number of soldiers, they will set two camps C1 and C2. Then, for C1, C2 and all camps on the path from C1 to C2, they will increase or decrease K soldiers to these camps. Now Aragorn wants to know the number of soldiers in some particular camps real-time.
这题查找为单点查找，故可以用树状数组来维护。
|
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 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 |
#include<iostream> #include<cstdio> using namespace std; int n,m,q,tot,label,a[50010],Next[100010],head[100010],tree[100010],dep[50010],son[50010],size[50010],fa[50010]; int tid[50010],top[50010],f[50010]; bool visit[50010]; void swap(int &i,int &j) { int t=i;i=j;j=t; } void Add(int x,int y) { tot++; Next[tot]=head[x]; head[x]=tot; tree[tot]=y; } void dfs(int x,int father,int depth) { visit[x]=true;dep[x]=depth;son[x]=0;size[x]=1;fa[x]=father; int maxsize=0 ; for (int i=head[x];i;i=Next[i]) if (!visit[tree[i]]) { dfs(tree[i],x,depth+1); size[x]+=size[tree[i]]; if (size[tree[i]]>maxsize) { son[x]=tree[i]; maxsize=size[tree[i]]; } } } void dfs1(int x,int ancestor) { visit[x]=true;top[x]=ancestor;label++;tid[x]=label; if (son[x]!=0) dfs1(son[x],ancestor); for (int i=head[x];i;i=Next[i]) if (!visit[tree[i]]) dfs1(tree[i],tree[i]); } int lowbit(int x) { return x&(-x); } void update(int x,int d) { for (int i=x;i<=n;i+=lowbit(i)) f[i]+=d; } int get(int x) { int ans=0; for (int i=x;i>=1;i-=lowbit(i)) ans+=f[i]; return ans; } int query_it(int x,int y) { return get(x);//单点查询，所以这里x=y; } void change_it(int x,int y,int d) { update(x,d); update(y+1,-d); } int query(int x,int y) { int ans=0; while (top[x]!=top[y]) { if (dep[top[x]]<dep[top[y]]) swap(x,y); ans+=query_it(tid[top[x]],tid[x]);//此题查找是单点，故树状数组可以实现 x=fa[top[x]]; } if (dep[x]>dep[y]) swap(x,y); ans+=query_it(tid[x],tid[y]); return ans; } void change(int x,int y,int d) { while (top[x]!=top[y]) { if (dep[top[x]]<dep[top[y]]) swap(x,y); change_it(tid[top[x]],tid[x],d); x=fa[top[x]]; } if (dep[x]>dep[y]) swap(x,y); change_it(tid[x],tid[y],d); } int main() { while (scanf("%d%d%d",&n,&m,&q)!=EOF) { tot=0;label=0; for (int i=1;i<=n;i++) scanf("%d",&a[i]),f[i]=0,head[i]=0; int x,y,z; for (int i=1;i<=m;i++) { scanf("%d%d",&x,&y); Add(x,y);Add(y,x); } for (int i=1;i<=n;i++) visit[i]=false; dfs(1,0,1); for (int i=1;i<=n;i++) visit[i]=false; dfs1(1,1); for (int i=1;i<=n;i++) change_it(tid[i],tid[i],a[i]); char s[5]; for (int i=1;i<=q;i++) { scanf("%s",s); if (s[0]=='Q') { scanf("%d",&x); printf("%d\n",query(x,x)); } if (s[0]=='I') { scanf("%d%d%d",&x,&y,&z); change(x,y,z); } if (s[0]=='D') { scanf("%d%d%d",&x,&y,&z); change(x,y,-z); } } } return 0; } |
