多校2L

题意

给出一张有 $n$ 个点 $m$ 条边的无向图，有 $q$ 个时刻，每个时刻仅有一个点的权值 $+w$ ，询问每个点的权值是它所有直接相连的点的严格最大值的时长。

数据范围

$n,m,q≤200000,1≤x i ,y i ,u j ≤n，1≤w j ≤10000$ .It's guaranteed that $x_i\ne y_i$ any $(x_i,y_i)$ does not appear twice in the graph and at any time nobody walks more than $10000$ steps.

题目分析

先考虑很直观的暴力做法。对于每个时刻 $t$ ，我们对该时刻增加权值的点 $u$ 查找周围所有直接相连的点 $v_{i}$ 的权值，判断 $u$ 是否是冠军，同时判断 $v_{i}$ 是否失去冠军。由于每个点最多有 $n-1$ 条边相连，所以复杂度为 $O(nq)$ ，妥妥的T飞了。

现按点的度数对点进行分块和分类，设块的大小为 $B$ ，则度数大于 $B$ 的点称为大点，小于等于 $B$ 的点称为小点，然后分类讨论。

若u是小点

若该时刻权值更新的点是小点，由于小点直接相邻的点数量最多不超过 $B$ ，所以直接暴力更新即可。这一块复杂度为 $O(Bq)$

若u是大点

更新与u相邻的大点信息

由于大点最多不超过 $B$ 个，所以暴力更新即可。

更新与u相邻的小点信息

由于小点数量可能很多，我们不能暴力枚举小点，但是由于与 $u$ 相邻的点 $v_{i}$ 失去冠军只有在 $weight[u]-w < weight[v_{i}]\leq weight[u]$ 时才有可能。
由于本题 $w \le 10000$ ，所以我们可以用一个vector $small[u][w]$ 来维护，它存储 $u$ 点周围存在的权值为 $w$ 的冠军点，然后暴力搜索所有这块区域内的 $small[u][w]$ 。
如果存有点，更新它们即可。
而 $small[u][w]$ 的维护，在每个点获得冠军的时候更新即可。
由于 $small[u][w]$ 是不重复的，所以这一块复杂度为 $O(W)$ ，而大点数量不会超过 $\frac{m}{B}$ ，所以这一块复杂度为 $O(q\frac{m}{B})$ $u$ 是大点的总复杂度为 $O(W+q\frac{m}{B})$ 。
而大点加小点总复杂度为 $O(B+W+q\frac{m}{B})$ ，取 $B = \frac{m}{B}$ ，即 $B=\sqrt{m}$ ，复杂度为 $O(W+q\sqrt{m})$

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

题解 | #多校2L题解#