HDU 4858 프로젝트 관리 (점 블록)

제목: 그림 한 장, 두 가지 조작 1. 점 x 에 가중치 y 2. 점 x 와 인접 한 점 의 가중치 와
분석: 점 을 중점 과 경 점 으로 나 누고 도 수 는 sqrt (m) 보다 크 며 작은 것 은 경 점 이다. 중점 과 인접 중점 을 연결 하고 가 벼 운 변 과 인접 한 모든 변 의 연결 변 을 규칙 적 으로 얻 을 수 있다. 중점 적 인 답 은 주위 중점 과 가 벼 운 점 이 그 에 대한 부가 로 구성 되 고 가 벼 운 답 은 바로 인접 점 으로 구성 되 며 복잡 도 O (q * 8727). sqrt (m))

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
//#pragma comment(linker, "/STACK:1024000000,1024000000");

using namespace std;

#define INF 0x3f3f3f3f
#define maxn 200004

int n,m;
int x[maxn],y[maxn];
int fir[maxn],nex[maxn],v[maxn],e_max;
int in[maxn];
int sum[maxn],val[maxn];
bool heavy[maxn];

void init()
{
    memset(sum,0,sizeof sum);
    memset(val,0,sizeof val);
    memset(heavy,false,sizeof heavy);
    memset(in,0,sizeof in);
    memset(fir,-1,sizeof fir);
    e_max=0;
}

void add_edge(int s,int t)
{
    int e=e_max++;
    v[e]=t;
    nex[e]=fir[s];
    fir[s]=e;
}

void build()
{
    int block=sqrt(m);
    for(int i=1; i<=n; i++)
    {
        if(in[i]>=block) heavy[i]=true;
    }
    for(int i=0; iint u=x[i],v=y[i];
        if(heavy[u]&&heavy[v])
        {
            add_edge(u,v);
            add_edge(v,u);
        }
        if(!heavy[u]) add_edge(u,v);
        if(!heavy[v]) add_edge(v,u);
    }
}

void update(int x,int y)
{
    val[x]+=y;
    if(!heavy[x])
    {
        for(int i=fir[x]; ~i; i=nex[i])
        {
            int e=v[i];
            sum[e]+=y;
        }
    }
}

int query(int x)
{
    int ans=0;
    if(heavy[x]) ans+=sum[x];
    for(int i=fir[x]; ~i; i=nex[i])
    {
        int e=v[i];
        ans+=val[e];
    }
    return ans;
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        init();
        scanf("%d%d",&n,&m);
        for(int i=0; iscanf("%d%d",&x[i],&y[i]);
            in[x[i]]++;
            in[y[i]]++;
        }
        build();
        int q;
        scanf("%d",&q);
        while(q--)
        {
            int op;
            scanf("%d",&op);
            if(!op)
            {
                int x,y;
                scanf("%d%d",&x,&y);
                update(x,y);
            }
            else
            {
                int x;
                scanf("%d",&x);
                printf("%d
",query(x));
            }
        }
    }
    return 0;
}