题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4467
题意：给定n个点m条边的无向图，点被染色(黑0/白1)，边带边权。然后q个询问。询问分为两种： Change u:把点u的颜色反转(黑变白，白变黑)，Asksum a b(a,b的值为0/1):统计所以边的权值和,边的两个点满足一个点的颜色为a,一个点的颜色为b。
思路：考虑暴力的做法。修改可以做法O(1),但是查询就得O(m).所以总复杂度为O(m*q)会TLE。然后考虑图分块。参考HDU 4858的做法，将点分为重点和轻点。重点(度数>=sqrt(m))，轻点(度数sqrt(m))。 由于此题查询比较大，所以需要预处理一下优化之后的运算。我们定义每个顶点维护3个属性:顶点的颜色color,与该点相连的边并且另外一个点是白点的边权和W, 同理B是黑色点的边权和。 然后维护3个变量ansWW:边上两个点都是白色的边权和。同理ansWB,ansBB。
修改：
轻点更新自己的color，W,B。同时更新所有的邻点的W,B值
重点更新自己的color，W,B。同时只更新相邻重点的W,B值（所以重点不需要连边到轻点）
对于更新。若未更新时该点的颜色为白色，那么更新后该点的颜色为黑色。那么对于相邻的点的W就要减去对应边的权值，相邻点的B就要加上对应边的权值。
对于更新。若未更新时该点的颜色为白色，那么更新后该点的颜色为黑色。那么边为WW的答案就要减去与该点相连的W的总和，边WB的答案就要减去与该点相邻的B的总和。 并且边为BB的答案就要加上与该点相邻的B的总和，边为WB的答案就要加上与该点相邻的W的总和。
查询：
直接输出对应的值
性质：
与重点相邻的重点不超过sqrt(m)个。
与轻点相邻的所有点不超过sqrt(m)个。
注意：
该题会有重边，如果不合并重边的话会TLE。所以用个map来合并下重边的值即可。
#define _CRT_SECURE_NO_DEPRECATE
#include<stdio.h>
#include<string.h>
#include<cstring>
#include<algorithm>
#include<queue>
#include<math.h>
#include<time.h>
#include<vector>
#include<iostream>
#include<map>
using namespace std;
typedef long long int LL;
const int MAXN = + ;
struct Edges{
int u, v; LL w;
Edges(int u = , int v = ,LL w=) :u(u), v(v),w(w){};
};vector<Edges>G[MAXN];
map<pair<int, int>, LL>edge;
struct Node{
int val;
LL W, B;
Node(int val = , LL W = , LL B = ) :val(val), W(W), B(B){};
}node[MAXN];
LL ansWB, ansWW, ansBB;
int du[MAXN], block;
void init(int n,int m){
edge.clear(); ansWB = ansWW = ansBB = ;
block = (int)sqrt(m + 0.5);
for (int i = ; i <= n; i++){
G[i].clear(); du[i] = ; node[i].W = node[i].B = ;
}
}
void makeGraph(int n, int m){
for (map<pair<int,int>,LL>::iterator it=edge.begin(); it!=edge.end(); it++){
int u = it->first.first, v = it->first.second; LL w = it->second;
if (du[u] >= block&&du[v] >= block){
G[u].push_back(Edges(u, v, w)); G[v].push_back(Edges(v, u, w));
}
if (du[u] < block){
G[u].push_back(Edges(u, v, w));
}
if (du[v] < block){
G[v].push_back(Edges(v, u, w));
}
if (node[u].val&&node[v].val){
ansWW += w; node[u].W += w; node[v].W += w;
}
else if (!node[u].val&&!node[v].val){
ansBB += w; node[u].B += w; node[v].B += w;
}
else{
ansWB += w;
if (node[u].val){
node[u].B += w; node[v].W += w;
}
else{
node[u].W += w; node[v].B += w;
}
}
}
}
void modify(int pos){
if (node[pos].val){
ansWW -= node[pos].W; ansWB -= node[pos].B;
ansBB += node[pos].B; ansWB += node[pos].W;
for (int i = ; i < G[pos].size(); i++){
node[G[pos][i].v].W -= G[pos][i].w;
node[G[pos][i].v].B += G[pos][i].w;
}
}
else{
ansBB -= node[pos].B; ansWB -= node[pos].W;
ansWW += node[pos].W; ansWB += node[pos].B;
for (int i = ; i < G[pos].size(); i++){
node[G[pos][i].v].W += G[pos][i].w;
node[G[pos][i].v].B -= G[pos][i].w;
}
}
node[pos].val = !node[pos].val;
}
LL query(int u, int v){
if (u&&v){ return ansWW; }
if (!u&&!v){ return ansBB; }
return ansWB;
}
int main(){
//#ifdef kirito
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
//#endif
int n, m, q,Case=;
while (~scanf("%d%d", &n, &m)){
init(n, m);
for (int i = ; i <= n; i++)
scanf("%d", &node[i].val);
for (int i = ; i <= m; i++){
int u, v; LL w; scanf("%d%d%I64d", &u, &v, &w);
if (u > v){ swap(u, v); }
if (edge.find(make_pair(u, v)) == edge.end()){
du[u]++; du[v]++;
edge.insert(make_pair(make_pair(u, v), w));
}
else{
edge[make_pair(u, v)] += w;
}
}
makeGraph(n, m);
printf("Case %d:\n", Case++);
scanf("%d", &q);
while (q--){
int u,v; char type[];
scanf("%s", type);
if (type[]=='A'){
scanf("%d%d", &u, &v);
printf("%I64d\n", query(u, v));
}
else{
scanf("%d", &u); modify(u);
}
//Debug:printf("BB=%I64d WB=%I64d WW=%I64d\n", ansBB, ansWB, ansWW);
}
}
return ;
}