多校2L
题意
给出一张有个点条边的无向图,有个时刻,每个时刻仅有一个点的权值,询问每个点的权值是它所有直接相连的点的严格最大值的时长。
数据范围
.It's guaranteed that anydoes not appear twice in the graph and at any time nobody walks more thansteps.
题目分析
先考虑很直观的暴力做法。对于每个时刻,我们对该时刻增加权值的点查找周围所有直接相连的点的权值,判断是否是冠军,同时判断是否失去冠军。由于每个点最多有条边相连,所以复杂度为,妥妥的T飞了。
现按点的度数对点进行分块和分类,设块的大小为,则度数大于的点称为大点,小于等于的点称为小点,然后分类讨论。
若u是小点
若该时刻权值更新的点是小点,由于小点直接相邻的点数量最多不超过,所以直接暴力更新即可。这一块复杂度为
若u是大点
更新与u相邻的大点信息
由于大点最多不超过个,所以暴力更新即可。
更新与u相邻的小点信息
由于小点数量可能很多,我们不能暴力枚举小点,但是由于与相邻的点失去冠军只有在 时才有可能。
由于本题,所以我们可以用一个vector来维护,它存储点周围存在的权值为的冠军点,然后暴力搜索所有这块区域内的。
如果存有点,更新它们即可。
而的维护,在每个点获得冠军的时候更新即可。
由于是不重复的,所以这一块复杂度为,而大点数量不会超过,所以这一块复杂度为 是大点的总复杂度为。
而大点加小点总复杂度为,取,即,复杂度为
AC代码
#include <cstdio> #include <cstring> #include <cmath> #include <vector> #include <algorithm> using namespace std; typedef long long ll; const int N = 200010; int weight[N]; //点权 int ma[N]; //某点相邻点中最大值 int degree[N];//度数 int id[N];//由于开不了10000*10000的vector,所以这个用来给大点标记,然后开500*10000的vector,看不懂多看几遍 vector<int> G[N], big[N], small[510][10010]; //存图,大点,大点u周围权值为w的曾经的小点冠军 int ans[N], win[N]; // win[i]表示第i个人上次夺冠时间 void lose(int i, int k) { // 第i个人第k天失去冠军 if (win[i]) ans[i] += k - win[i]; win[i] = 0; } int main() { int n, m, q; scanf("%d%d%d", &n, &m, &q); int idx = 0, sqn = sqrt(m); while(m --> 0) { //皮 int u, v; scanf("%d%d", &u, &v); ++degree[u]; //更新度数 ++degree[v]; G[u].push_back(v); //存图 G[v].push_back(u); } //处理大点和大点周围的大点。 for (int i = 1; i <= n; ++i) { if (degree[i] > sqn) id[i] = ++idx; //大点的id,用于减小vector的大小 for (auto v : G[i]) if (degree[v] > sqn) big[i].push_back(v); //大点i周围的大点 } for(int i = 1; i <= q; ++i) { int u, w; scanf("%d%d", &u, &w); weight[u] += w; //更新点权 if (degree[u] <= sqn) { // u是小点 bool is_win = 1; for (auto v : G[u]) { // 直接暴力维护u的所有连边 if (degree[v] > sqn) ma[v] = max(ma[v], weight[u]); //更新u周围大点的周围点的最大权值 if (weight[v] > weight[u]) is_win = 0; //u不是冠军 else { // weight[u] >= weight[v] 说明v失去冠军 if (weight[v] == weight[u]) is_win = 0; //相等二者都不是冠军 lose(v, i); } } if (is_win) { //如果u是冠军 for (auto v : big[u]) { small[id[v]][weight[u]].push_back(u); //大点v存在权值为w的小点冠军 } if (!win[u]) win[u] = i; //如果不是冠军,更新成为冠军的时间点 } } else { // u是大点 bool is_win = 1; for (auto v : big[u]) { // 遍历连接的大点 if (weight[v] > weight[u]) is_win = 0; else { // weight[u] >= weight[v] 说明v失去冠军 if (weight[v] == weight[u]) is_win = 0; //相等无冠军 lose(v, i); } } for (int k = weight[u] - w + 1; k <= weight[u]; ++k) { //只有(weight[u]-w,weight[u]]即[weight[u]-w+1,weight[u]]这个区间内才可能失去冠军 for (auto v : small[id[u]][k]) if (weight[v] == k) lose(v, i); } if (is_win && ma[u] < weight[u] && !win[u]) win[u] = i; } } for (int i = 1; i <= n; ++i) lose(i, q); //更新所有点的冠军时间 for (int i = 1; i <= n; ++i) printf("%d\n", ans[i]); return 0; }
参考资料
- 官方题解
- 题解区sunrise__sunrise的题解