多校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的题解