题目链接：acm.hdu.edu.cn/showproblem.php?pid=4467
#include<bits/stdc++.h>
using namespace std;#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define read(x,y) scanf("%d%d",&x,&y)
#define ll long long#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
const int maxn =2e5+5;
const int mod=1e9+7;
/*
题目大意：给定一个图，每个点都有0，1值，
然后每个边都有个权重值，给定q个查询或者修改操作，
查询是给定两个数x,y要求输出所有边的权重和，边满足两端权值相加为x+y。
修改是修改一个点的权值.分块的题目都有一种矛盾的意思在里面，
比方说我们暴力一发，一个想法是对于每个点都维护一个sum数组，
每次修改直接通过sum数组的改变来更新答案数组。
另一种想法是不维护sum数组，直接暴力遍历修改答案。两种方法都过不了，那么直接两种结合起来，分块的题目我们一定要找到
一个指标，这个指标直接影响了复杂度，那么通过观察上面两种做法，
可以知道这个指标就是点的度数，那么我们依靠点的度数对点进行划分，
重点与轻点。
对于重点，每次修改直接通过sum数组更新答案，然后暴力更新相邻重点的sum数组，
轻点则直接暴力扫描所有相邻点，然后更新答案。这样复杂度就被均摊了，因为重点的数量不超过m^(1/2)的性质。
我这份代码时间复杂度超了，下面的第二版是AC的，我
自己写的不知道为什么会一直过不了，希望大神指点。
*/
///数据域
int n,m,x,y;
ll z;
char s[20];
ll sum[maxn][2],a[3];///重点的统计数组,分别表示i重点，相邻的权重为0，1，2的边权重和.
vector<pair<int,ll>> hey[maxn];///重点和重点相连
///点的结构
struct tp
{int u,v;ll w;///边和权重bool operator==(const tp&y) const{return (u==y.u&&v==y.v)||(u==y.v&&v==y.u);}bool operator<(const tp& y) const{if(y.u==u) return v<y.v;return u<y.u;}
}jihe[maxn];
///链式前向星
struct node
{int u,nxt;ll w;
}edge[maxn<<1];
int head[maxn],tot=0;
void init()
{memset(a,0,sizeof(a));tot=0;
}
void add(int x,int y,ll z)
{edge[tot]=node{y,head[x],z};head[x]=tot++;
}
///权值数组和度数数组和是否为重点的判别数组
int v[maxn],q;
ll d[maxn],is_heavy[maxn];
int main()
{int ca=1,ub;while(scanf("%d%d",&n,&m)!=EOF){init();for(int i=0;i<=n;i++){d[i]=is_heavy[i]=0;sum[i][0]=sum[i][1]=0;hey[i].clear();memset(head,-1,sizeof(head));}for(int i=1;i<=n;i++) scanf("%d",&v[i]);for(int i=1;i<=m;i++){scanf("%d%d%lld",&x,&y,&z);jihe[i].u=x,jihe[i].v=y,jihe[i].w=z;a[v[x]+v[y]]+=1LL*z;}///去除多余的重复边sort(jihe+1,jihe+m+1);int top=1;for(int i=2;i<=m;i++){for(int j=i;j<=m&&(jihe[j]==jihe[top]);j++)jihe[top].w+=jihe[j].w;jihe[++top]=jihe[i];}ub=sqrt(top);///建边，建度for(int i=1;i<=top;i++){int u=jihe[i].u,v=jihe[i].v;ll w=jihe[i].w;add(u,v,w),add(v,u,w);d[u]++,d[v]++;/*if(d[u]>=ub&&d[v]>=ub){hey[u].push_back(make_pair(v,w));hey[v].push_back(make_pair(u,w));}*/}///建重点图并初始化sum集合for(int i=1;i<=top;i++){int u=jihe[i].u,v=jihe[i].v;ll w=jihe[i].w;if(d[u]>=ub&&d[v]>=ub){hey[u].push_back(make_pair(v,w));hey[v].push_back(make_pair(u,w));}}for(int i=1;i<=n;i++){if(d[i]>=ub)///标记为重点{is_heavy[i]=1;for(int j=head[i];~j;j=edge[j].nxt){int u=edge[j].u;sum[i][v[u]]+=edge[j].w;}}}scanf("%d",&q);printf("Case %d:\n",ca++);for(int i=0,tx,ty;i<q;i++){scanf("%s",s);if(s[0]=='A'){scanf("%d%d",&tx,&ty);printf("%lld\n",a[tx+ty]);}else{scanf("%d",&tx);if(is_heavy[tx])///如果是重点,通过预处理好的数组来更新{a[v[tx]+0]-=sum[tx][0];a[v[tx]+1]-=sum[tx][1];a[1-v[tx]+1]+=sum[tx][1];a[1-v[tx]+0]+=sum[tx][0];for(int j=0;j<hey[tx].size();j++){ll tp=hey[tx][j].first,tw=hey[tx][j].second;sum[tp][v[tx]]-=tw;sum[tp][1-v[tx]]+=tw;}v[tx]^=1;}else///轻点{for(int j=head[tx];~j;j=edge[j].nxt){int y=edge[j].u;if(is_heavy[y])///轻点和重点相连{a[v[y]+v[tx]]-=1LL*edge[j].w;sum[y][v[tx]]-=1LL*edge[j].w;v[tx]^=1;sum[y][v[tx]]+=1LL*edge[j].w;a[v[y]+v[tx]]+=1LL*edge[j].w;}else///这种情况直接修改{a[v[tx]+v[y]]-=1LL*edge[j].w;v[tx]^=1;a[v[tx]+v[y]]+=1LL*edge[j].w;}}}}}}return 0;
}
/*
4 4
0 0 0 0
1 2 1
2 3 2
3 4 3
1 2 1
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
typedef long long ll;
const ll maxn=1e5+10;
ll sum[maxn][2],a[5],color[maxn],du[maxn];
bool ok[maxn];
struct Edge{ll x,y,val;
}arr[maxn],arr_[maxn];
struct edge{ll v,val;edge(ll _v=0,ll _val=0):v(_v),val(_val) {}
};
vector<edge>G[maxn],G_[maxn];bool cmp(Edge x,Edge y)
{if ( x.x==y.x ) return x.y<y.y;return x.x<y.x;
}int main()
{ll n,m,i,j,k,x,y,z,sz,cnt,q,ans,h=0;char op[10];while ( scanf("%lld%lld",&n,&m)!=EOF ) {for ( i=1;i<=n;i++ ) {sum[i][0]=sum[i][1]=0;ok[i]=false;du[i]=0;G[i].clear();G_[i].clear();}memset(a,0,sizeof(a));for ( i=1;i<=n;i++ ) scanf("%lld",&color[i]);for ( i=1;i<=m;i++ ) {scanf("%lld%lld%lld",&x,&y,&arr[i].val);if ( x>y ) swap(x,y);arr[i].x=x;arr[i].y=y;a[color[x]+color[y]]+=arr[i].val;}sort(arr+1,arr+1+m,cmp);cnt=0;for ( i=1;i<=m;i=j ) {for ( j=i+1;j<=m;j++ ) {if ( arr[i].x==arr[j].x && arr[i].y==arr[j].y ) {arr[i].val+=arr[j].val;}else break;}arr_[++cnt]=arr[i];}sz=sqrt(cnt);for ( i=1;i<=cnt;i++ ) {du[arr_[i].x]++;du[arr_[i].y]++;}for ( i=1;i<=n;i++ ) {if ( du[i]>sz ) ok[i]=true;}for ( i=1;i<=cnt;i++ ) {x=arr_[i].x;y=arr_[i].y;if ( ok[x] ) {if ( ok[y] ) {G_[x].push_back(edge(y,arr_[i].val));G_[y].push_back(edge(x,arr_[i].val));sum[x][color[y]]+=arr_[i].val;sum[y][color[x]]+=arr_[i].val;}else {G[y].push_back(edge(x,arr_[i].val));sum[x][color[y]]+=arr_[i].val;}}else {if ( ok[y] ) {G[x].push_back(edge(y,arr_[i].val));sum[y][color[x]]+=arr_[i].val;}else {G[x].push_back(edge(y,arr_[i].val));G[y].push_back(edge(x,arr_[i].val));}}}printf("Case %lld:\n",++h);scanf("%lld",&q);while ( q-- ) {scanf("%s",op);if ( op[0]=='A' ) {scanf("%lld%lld",&x,&y);printf("%lld\n",a[x+y]);}else {scanf("%lld",&x);if ( ok[x] ) {a[color[x]+0]-=sum[x][0];a[color[x]+1]-=sum[x][1];a[1-color[x]+0]+=sum[x][0];a[1-color[x]+1]+=sum[x][1];for ( i=0;i<G_[x].size();i++ ) {y=G_[x][i].v;z=G_[x][i].val;sum[y][color[x]]-=z;sum[y][1-color[x]]+=z;}}else {for ( i=0;i<G[x].size();i++ ) {y=G[x][i].v;z=G[x][i].val;a[color[x]+color[y]]-=z;a[1-color[x]+color[y]]+=z;if ( ok[y] ) {sum[y][color[x]]-=z;sum[y][1-color[x]]+=z;}}}color[x]=1-color[x];}}}return 0;
}HDOJ4467