2015
07-16

# Graph

P. T. Tigris is a student currently studying graph theory. One day, when he was studying hard, GS appeared around the corner shyly and came up with a problem:
Given a graph with n nodes and m undirected weighted edges, every node having one of two colors, namely black (denoted as 0) and white (denoted as 1), you’re to maintain q operations of either kind:
* Change x: Change the color of xth node. A black node should be changed into white one and vice versa.
* Asksum A B: Find the sum of weight of those edges whose two end points are in color A and B respectively. A and B can be either 0 or 1.
P. T. Tigris doesn’t know how to solve this problem, so he turns to you for help.

There are several test cases.
For each test case, the first line contains two integers, n and m (1 ≤ n,m ≤ 105), where n is the number of nodes and m is the number of edges.
The second line consists of n integers, the ith of which represents the color of the ith node: 0 for black and 1 for white.
The following m lines represent edges. Each line has three integer u, v and w, indicating there is an edge of weight w (1 ≤ w ≤ 231 – 1) between u and v (u != v).
The next line contains only one integer q (1 ≤ q ≤ 105), the number of operations.
Each of the following q lines describes an operation mentioned before.
Input is terminated by EOF.

There are several test cases.
For each test case, the first line contains two integers, n and m (1 ≤ n,m ≤ 105), where n is the number of nodes and m is the number of edges.
The second line consists of n integers, the ith of which represents the color of the ith node: 0 for black and 1 for white.
The following m lines represent edges. Each line has three integer u, v and w, indicating there is an edge of weight w (1 ≤ w ≤ 231 – 1) between u and v (u != v).
The next line contains only one integer q (1 ≤ q ≤ 105), the number of operations.
Each of the following q lines describes an operation mentioned before.
Input is terminated by EOF.

4 3
0 0 0 0
1 2 1
2 3 2
3 4 3
4
Change 2
4 3
0 1 0 0
1 2 1
2 3 2
3 4 3
4
Change 3
Asksum 0 1

Case 1:
6
3
3
Case 2:
3
0
4

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#define N 100005
using namespace std;
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<int,LL> PIL;

int gg[2][2] = {0,1,1,2};
char s[20];
vector<PIL> vec[N];
vector<PIL> vv[N];
int color[N];
LL sum[3], f[3][N];

struct Eg{
int l, r ,val;
Eg(){}
Eg(int _l,int _r,int _val){l=_l;r=_r;val=_val;}
bool operator <(const Eg&o)const{
if(l==o.l) return r<o.r;
return l<o.l;
}
} e[N<<2];

int main(){
int cal=0, n, m, i, iter, l, r, v, u;
LL val;
while(scanf("%d%d",&n,&m)!=EOF){
printf("Case %d:\n", ++cal);
for(i=1;i<=n;i++){
vec[i].clear();
vv[i].clear();
scanf("%d",&color[i]);
}
for(i=0;i<m;i++){
scanf("%d%d%d",&e[i<<1].l,&e[i<<1].r,&e[i<<1].val);
e[i<<1|1] = Eg(e[i<<1].r,e[i<<1].l,e[i<<1].val);
}
sort(e,e+m*2);

LL tot=e[0].val;
for(i=1;i<2*m;i++){
if(e[i].l==e[i-1].l && e[i].r==e[i-1].r) tot+=e[i].val;else{
vec[e[i-1].l].pb(mp(e[i-1].r,tot));
tot = e[i].val;
}
}
vec[e[i-1].l].pb(mp(e[i-1].r,tot));

memset(f,0,sizeof(f));
memset(sum,0,sizeof(sum));
for(i=1;i<=n;i++)
for(iter=0;iter!=vec[i].size();++iter){
v = vec[i][iter].first;
val = vec[i][iter].second;
if(vec[v].size()<vec[i].size() ||(vec[v].size()==vec[i].size() && i<v)){
sum[gg[color[i]][color[v]]] += val;
f[color[v]][i] += val;
}
else
vv[i].pb(mp(v,val));
}

int Q;
scanf("%d",&Q);
while(Q--){
scanf("%s",s);
if(s[0]=='A'){
scanf("%d%d",&l,&r);
printf("%I64d\n",sum[gg[l][r]]);
}
else {
scanf("%d",&u);
int col;
for(col=0;col<=2;col++){
sum[gg[color[u]][col]] -= f[col][u];
sum[gg[1-color[u]][col]] += f[col][u];
}
for(i=0;i<vv[u].size();i++){
v =vv[u][i].first;
val = vv[u][i].second;
f[color[u]][v] -= val;
f[1-color[u]][v] += val;
sum[gg[color[u]][color[v]]] -=val;
sum[gg[1-color[u]][color[v]]] += val;
}
color[u] = 1-color[u];
}
}
}
return 0;
}

/*
4 3
0 1 0 0
1 2 1
2 3 2
3 4 3
4
Change 3
*/