题目连接：hdu_4467_Graph
题意：给你n个点，m条边，每条边有一个权值，有两个操作，一个是修改单点的颜色，一个是询问边的两个端点都为指定颜色的权值和
题解：这题如果暴力的话，就是维护3个ans,一个是两个端点都为0的，一个是一个为1一个为0的，最后还有个两个端点都为1的，对于每个询问，可以做到O(1)，但对于修改单点操作，极限状态下，一个单点的边最大可为1e5，这样果断T飞，如果我们对每个单点修改做到O(1)，那么询问的时候会达到1e5*1e5，也果断T飞，怎么办，这时候想想莫队的思想，将这两个操作的时间复杂度均分一下，我们设一个点的边大于sqrt(m)的为重点，小于的为轻点，这样我们对轻点进行暴力维护就sqrt(m)，重点就将他周围的权值用一个二维数组sum[i][j]维护，表示i这个重点它周围的j这个颜色的权值和，每次修改重点时，直接在三个ans上对sum加加减减就行了，当修改轻点的时候要注意，轻点周围的重点的sum要维护一下，设重点(边大于sqrt(m))的个数为x,则x*sqrt(m)/2<m,所以x<2*sqrt(m),这样总的复杂度就降到了nsqrt(m)。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<cmath> 5 #define F(i,a,b) for(int i=a;i<=b;i++) 6 typedef long long LL; 7 using namespace std; 8 9 const int N=(int)1e5+7; 10 int du[N],sp[N],type[N],g[N][2],v[N<<2],nxt[N<<2],ed,sqr; 11 LL ans[3],w[N<<2],sum[N][2]; 12 //sp表示为轻重点（边数大于sqr的为重点），type为当前的类型 13 struct edge{ 14 int u,v;LL w; 15 bool operator<(const edge &b)const{ 16 if(u==b.u)return v<b.v; 17 return u<b.u; 18 } 19 }e[N]; 20 21 inline void adg(int t,int x,int y,LL z){v[++ed]=y,w[ed]=z,nxt[ed]=g[x][t],g[x][t]=ed;} 22 23 int main(){ 24 int ic=1,n,m,x; 25 while(~scanf("%d%d",&n,&m)){ 26 F(i,1,n)scanf("%d",&x),type[i]=x; 27 F(i,0,m-1){ 28 scanf("%d%d%lld",&e[i].u,&e[i].v,&e[i].w); 29 if(e[i].u>e[i].v)swap(e[i].u,e[i].v); 30 } 31 //将边去重并将权值合并 32 sort(e,e+m); 33 int cnt=0; 34 for(int i=0,j;i<m;i=j){ 35 for(j=i+1;j<m&&e[i].u==e[j].u&&e[i].v==e[j].v;j++) 36 e[i].w+=e[j].w; 37 e[cnt++]=e[i]; 38 } 39 //建图 40 sqr=(int)sqrt(cnt<<1); 41 memset(du,0,sizeof(du)); 42 F(i,0,cnt-1)du[e[i].u]++,du[e[i].v]++; 43 F(i,1,n)sp[i]=(du[i]>=sqr); 44 memset(g,0,sizeof(g)),ed=0; 45 F(i,0,cnt-1){ 46 int x=e[i].u,y=e[i].v;LL w=e[i].w; 47 //重点是被访问的点，轻点是要访问所有的点 48 if(sp[x])adg(1,y,x,w);else adg(0,x,y,w); 49 if(sp[y])adg(1,x,y,w);else adg(0,y,x,w); 50 } 51 memset(ans,0,sizeof(ans)),memset(sum,0,sizeof(sum)); 52 //维护每一种ans和重点周围的边的权值和 53 F(i,0,cnt-1){ 54 int x=e[i].u,y=e[i].v;LL w=e[i].w; 55 if(sp[x])sum[x][type[y]]+=w; 56 if(sp[y])sum[y][type[x]]+=w; 57 ans[type[x]+type[y]]+=w; 58 } 59 printf("Case %d: ", ic++); 60 int q,a,b,x;char s[20]; 61 scanf("%d",&q); 62 while(q--){ 63 scanf("%s",s); 64 if(s[0]=='A')scanf("%d%d",&a,&b),printf("%lld ",ans[a+b]); 65 else{//修改点 66 scanf("%d",&x); 67 type[x]^=1; 68 if(sp[x]){//修改重点 69 F(i,0,1){//对于每一种sum将原来的减去，加上修改后的 70 ans[(type[x]^1)+i]-=sum[x][i]; 71 ans[type[x]+i]+=sum[x][i]; 72 } 73 }else{//修改轻点，直接暴力修改 74 for(int i=g[x][0];i;i=nxt[i]){ 75 ans[(type[x]^1)+type[v[i]]]-=w[i]; 76 ans[type[x]+type[v[i]]]+=w[i]; 77 } 78 }//更新重点的sum 79 for(int i=g[x][1];i;i=nxt[i]){ 80 sum[v[i]][type[x]^1]-=w[i]; 81 sum[v[i]][type[x]]+=w[i]; 82 } 83 } 84 } 85 } 86 return 0; 87 }