【分块】2021牛客暑期多校训练营2 L WeChat Walk
2021-08-27 13:47:00 # ACM

题链

题目解析

给定人数 $n$，关系数 $m$，操作数 $q$，每个人都有自己的微信步数榜单，其中只会显示和自己有关系的人，$q$ 步操作表示第 $i$ 个时间单元，第 $u_i$ 人上传 $w_i$ 步到微信运动上，累加到以往的步数上，输出每个人有几个时间单元时冠军(只有自己的步数严格大于和自己有关系的人的步数才算冠军)；

暴力分块： 将所有的点分为小点 $(deg <= \sqrt n)$ 和大点；
维护所有的点的 $w[x]$，表示 $x$ 点的步数；
维护大点的 $mx[x]$，表示大点周围的最大值；
维护大点的 $C[x][val]$，表示大点 $x$ 的权值 $val$ 下有哪些小点；
维护所有点的 $last[x]$，表示 $x$ 点上一次取得冠军的时间；
主要维护好 $last[]$ 的信息；

对于小点暴力处理周围的点的信息，如果是冠军，则将自身加入到周围大点的 $C[][ w[x] ]$；
对于大点：
  对周围的大点直接更新；
  对周围的小点直接查找 $C[x][L…R]$，其中 $L$ 是 $w[x]$，$R$ 是 $w[x]+val$；

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <bits/stdc++.h>
//#pragma GCC optimize(2)
using namespace std;
#define LL long long
#define ll long long
#define ULL unsigned long long
#define Pair pair<LL,LL>
#define ls rt<<1
#define rs rt<<1|1
#define Pi acos(-1.0)
#define eps 1e-6
#define DBINF 1e100
#define mod 1000000007
#define MAXN 10009
#define MS 200009
#define sqMS 500

int n,m,k;
vector<int > vc[MS];
vector<int > bg[MS];
vector<int > C[sqMS][MAXN];
int id[MS] ,cnt;
int sizee;
int w[MS];
int mx[MS];
int last[MS];
int ac[MS];

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m >> k;
	sizee = sqrt(n);
	for(int i=1;i<=m;i++){
		int u,v;
		cin >> u >> v;
		vc[u].push_back(v);
		vc[v].push_back(u);
	}
	for(int i=1;i<=n;i++){
		if((int)vc[i].size() > sizee){
			id[i] = ++cnt;
			for(auto v:vc[i]){
				bg[v].push_back(i);
			}
		}
	}
	for(int i=1;i<=k;i++){
		int x,val;
		cin >> x >> val;
		w[x] += val;
		if((int)vc[x].size() <= sizee){ // 是小点 
			int ischamp = 1; // ischamp只对大点有效，小点无效 
			for(auto v:vc[x]){ // 对于周围的点暴力更新 
				if(w[x] >= w[v] && last[v]){
					ac[v] += i-last[v];
					last[v] = 0;
				}
				mx[v] = max(mx[v],w[x]);
				if(w[x] <= w[v]) ischamp = 0;
			}
			if(ischamp){ // 是冠军，更新周围大点信息 
				if(!last[x]) last[x] = i;
				for(auto v:bg[x]){
					C[id[v]][w[x]].push_back(x); // 在大点的该权值下存放点 x 
				}
			}
			else if(last[x]) ac[x] += i-last[x] ,last[x] = 0;
		}
		else{ // 是大点 
			int ischamp = w[x] > mx[x]; // ischamp只对大点有效，小点无效 
			for(auto v:bg[x]){ // 对周围的大点更新 
				if(w[x] >= w[v] && last[v]){
					ac[v] += i-last[v];
					last[v] = 0;
				}
				mx[v] = max(mx[v],w[x]);
			}
			for(int j=w[x]-val+1;j<=w[x];j++){ // 扫描权值包含的小点信息，有些小点不在权值范围内，所以小点的mx没有维护 
				for(auto v:C[id[x]][j]){
					if(w[x] >= w[v] && last[v]){
						ac[v] += i-last[v];
						last[v] = 0;
					}
				}
			}
			if(ischamp && !last[x]) last[x] = i;
			if(!ischamp && last[x]) ac[x] += i-last[x] ,last[x] = 0;
		}
	}
	for(int i=1;i<=n;i++){
		if(last[i]){
			ac[i] += n-last[i];
		}
	}
	for(int i=1;i<=n;i++){
		cout << ac[i] << "\n";
	}
	
	
	return 0;
}

Prev
2021-08-27 13:47:00 # ACM
Next