HDU4858 – 项目管理(图的分块)

题目链接：HDU4858

【分析】BC round#1里面的，当时没做出来，后来也没补上，最近看到了才补上。是一道分块题，当时好像可以暴力过，杭电编译器升级之后暴力似乎不太可能了(反正我是没暴力过)。

首先可以把每个点按照度数分成两类：重点和轻点，类似分块的块数和每块的大小这样分，定义>=sqrt(n)是重点，否则为轻点，这样重点最多只有sqrt(m)个，因为只有2*m条边。然后轻点可能有很多，所以需要一个sum[i]维护和i相邻的所有轻点权值之和，重点只记录他自己的权值val[i]；对于每个查询操作u：把所有相邻的重点权值相加，对于相邻的轻点直接加上sum[u]，由于重点最多只有sqrt(m)个，所以复杂度是sqrt(m); 然后对于修改操作u,v:如果u是重点则直接修改自身val[u]即可(因为sum只记录轻点)，如果u是轻点，则把u相邻的所有点的sum修改即可，复杂度也是sqrt(m)的，因为轻点的定义就是度小于sqrt(m)呀。这样总的复杂度就是q*sqrt(m)。

【AC CODE】452ms

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
//#include <unordered_set>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 100000+10, MAXM = 100000*2+20, SIZE = 150;
struct G{
	int head[MAXN], tol,nxt[MAXM],to[MAXM];
	void add_edge(int u, int v)
	{
		nxt[tol] = head[u], to[tol] = v;
		head[u] = tol++;
	}
	void clear()
	{
		clc(head,-1);
		tol = 0;
	}
}z,q;/*轻重点分开存--保证复杂度单次sqrt(n)*/
struct Edge{
	int u,v;
}edge[MAXM];
int val[MAXN], du[MAXN], sum[MAXN];//sum[i]与i相邻的所有du<SIZE的权和

int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	int t;
	scanf("%d%*c", &t);
	while(t--)
	{
		int n,m;
		scanf("%d %d%*c", &n, &m);
		clc(val,0);
		clc(du,0);
		clc(sum,0);
		rep(i,0,m)
		{
			int u,v;
			scanf("%d %d%*c", &u, &v);
			edge[i] = {u,v};
			du[v]++, du[u]++;
		}
		z.clear();
		q.clear();
		rep(i,0,m)
		{
			int u = edge[i].u,v = edge[i].v;
			if(du[v] >= SIZE) z.add_edge(u,v);
			else q.add_edge(u,v);
			if(du[u] >= SIZE) z.add_edge(v,u);
			else q.add_edge(v,u);
		}
		int cnt;
		scanf("%d%*c", &cnt);
		while(cnt--)
		{
			int op;
			scanf("%d%*c", &op);
			if(op)//查询
			{
				int u;
				scanf("%d%*c", &u);
				int ans = sum[u];
				for(int i = z.head[u]; ~i; i = z.nxt[i])
					ans += val[z.to[i]];
				printf("%d\n", ans);
			}
			else
			{
				int u,v;
				scanf("%d %d%*c", &u, &v);
				if(du[u] >= SIZE) val[u] += v;
				else
				{
					//sum[u] += v;
					for(int i = q.head[u]; ~i; i = q.nxt[i])
						sum[q.to[i]] += v;
					for(int i = z.head[u]; ~i; i = z.nxt[i])
						sum[z.to[i]] += v;
				}
			}
		}
	}
	return 0;
}