HDOJ4467 ( 分块思想 )

题目：链接：http://acm.hdu.edu.cn/showproblem.php?pid=4467

题意：给你n个点（每个点都有一个颜色，0代表黑色，1代表白色），m条边，每条边有一个权值.现在有有两个操作，一个是修改某个点的颜色（白变成黑/黑变成白），另外一个是询问那些边的两个端点都为指定颜色的权值总和

思路：将所有点分为重点和轻点，但是这次重点和重点之前的边要建在一个图中，剩余的边要建在另一个图中。对于最后访问的颜色，只有三种情况黑+黑（求和为0），黑+白（求和为1），白+白（求和为 2），所以用ans[0],ans[1],ans[2]分别对应的答案。对于重点i设置一个sum[i][2]，sum[i][0]表示所有与他相邻且颜色为0（黑）的点的边权之和，sum[i][1]同理。更新时，对于重点i来说拿sum[i][0]和sum[i][1] 去直接更新a数组，同时将其相邻的重点的sum值进行修改。而对于轻点i来说，遍历所有与i相连的边，暴力更新a数组，而当其相邻点为重点时则需要更新一下重点的sum数组。对于查询操作，直接输出 ans数组中的值即可 (转自： https://www.cnblogs.com/HDUjackyan/p/8996172.html)

#include<bits/stdc++.h>

#define LL long long

#define ULL unsigned long long

#define rep(i,j,k) for(int i=j;i<=k;i++)

#define dep(i,j,k) for(int i=k;i>=j;i--)

#define INF 0x3f3f3f3f

#define mem(i,j) memset(i,j,sizeof(i))

#define make(i,j) make_pair(i,j)

#define pb push_back

using namespace std;

const int N=1e5+;

int c[N],du[N];

LL ans[],sum[N][];

bool vis[N];

struct note {

    int u,v;

    LL w;

}a[N];

vector< pair<int,LL> > Z[N],Q[N];

bool cmp (note a,note b) {

    return a.u==b.u?a.v<b.v:a.u<b.u;

}

char op[];

int main() {

    int n,m; int cas=;

    while(~scanf("%d %d",&n,&m)) {

        rep(i,,n) scanf("%d",&c[i]);

        rep(i,,n) {

            du[i]=; vis[i]=false; sum[i][]=sum[i][]=;

            Z[i].clear(); Q[i].clear();

        }

        mem(ans,);

        rep(i,,m) {

            scanf("%d %d %lld",&a[i].u,&a[i].v,&a[i].w);

            if(a[i].u>a[i].v) swap(a[i].u,a[i].v);

            ans[c[a[i].u]+c[a[i].v]]+=a[i].w;

        }

        sort(a+,a++m,cmp);

        int I,J; int head=;

        for(I=;I<=m;I=J) {

            for(J=I+;J<=m;J++) {

                if(a[I].u==a[J].u && a[I].v==a[J].v) {

                    a[I].w+=a[J].w;

                }

                else break;

            }

            a[++head]=a[I];

        }

        int block=sqrt(head);

        rep(i,,head) {

            if(++du[a[i].u]>block) vis[a[i].u]=true;

            if(++du[a[i].v]>block) vis[a[i].v]=true;

        }

        int x,y; LL z;

        rep(i,,head) {

            x=a[i].u; y=a[i].v; z=a[i].w;

            if(vis[x]) {

                if(vis[y]) {

                    Z[x].pb(make(y,z));

                    Z[y].pb(make(x,z));

                    sum[x][c[y]]+=z;

                    sum[y][c[x]]+=z;

                }

                else {

                    Q[y].pb(make(x,z));

                    sum[x][c[y]]+=z;

                }

            }

            else {

                if(vis[y]) {

                    Q[x].pb(make(y,z));

                    sum[y][c[x]]+=z;

                }

                else {

                    Q[x].pb(make(y,z));

                    Q[y].pb(make(x,z));

                }

            }

        }

        int q;

        printf("Case %d:\n",++cas);

        scanf("%d",&q);

        while(q--) {

            scanf("%s",op);

            if(op[]=='A') {

                scanf("%d %d",&x,&y);

                printf("%lld\n",ans[x+y]);

            }

            else {

                scanf("%d",&x);

                if(vis[x]) {

                    ans[c[x]+]-=sum[x][];

                    ans[c[x]+]-=sum[x][];

                    ans[-c[x]+]+=sum[x][];

                    ans[-c[x]+]+=sum[x][];

                    int len=Z[x].size()-;

                    rep(i,,len) {

                        y=Z[x][i].first; z=Z[x][i].second;

                        sum[y][c[x]]-=z;

                        sum[y][-c[x]]+=z;

                    }

                }

                else {

                    int len=Q[x].size()-;

                    rep(i,,len) {

                        y=Q[x][i].first; z=Q[x][i].second;

                        ans[c[x]+c[y]]-=z;

                        ans[-c[x]+c[y]]+=z;

                        if(vis[y]) {

                            sum[y][c[x]]-=z;

                            sum[y][-c[x]]+=z;

                        }

                    }

                }

                c[x]=-c[x];

            }

        }

    }

    return ;

}

巴特西

HDOJ4467 ( 分块思想 )

最新文章

热门文章

巴特西

HDOJ4467 ( 分块 思想 )

最新文章

热门文章

HDOJ4467 ( 分块思想 )