L-WeChat Walk

给出一张图，一共有个时刻，每个时刻只有一个点的权值会增大。并且保证最终图里面最大的点权值。

一个人某个时刻成为冠军是和他相连的全部点这个时刻权值严格小于当前点，如果某个时刻不满足条件了那么这个人就失去了冠军，输出所有点成为冠军的时长。

Solution

题目关键信息1.每次只有一个点权值改变，2.最大权值。

那么我们按照这个边界对图中的点进行分点，记为。

我们将度数大于的叫做大点，我们将度数小于等于的叫做小点。

1. 如果当前遍历的点他是小点，那么暴力维护他连接的点叫做，并且维护和相连的最值情况，以便以后维护的得冠情况。
2. 对于大点，我们首先判断他和他相邻的大点，接下来就要去小点中更新小点信息，但是我们又不能暴力的再去枚举小点，那么关注到这信息，并且如果当前大点增加了，那么在最开始把之后，可更新的小点区间一定在之间，只有曾经在这段区间中的小点才会失去冠军，其余小点冠军情况不变，那么我们就开一个记录大点在权值为的时候连接了哪些得冠的小点，这个信息可以在1中维护。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }

const int N = 2e5 + 7;

int n, m, q;

int a[N], mx[N], du[N], id[N];

vector<int> G[N], BigG[N], SmallG[507][10007]; // G:总图, BigG:每个点连接的大点，SmallG:每个曾经获胜的小点玩家连接的旁边的大点

int ans[N], win[N]; // win[i]表示第i个人上次最近一次夺冠在什么时候

void loser(int i, int k) { // 第i个人第k天不是冠军
    if (win[i])    ans[i] += k - win[i];
    win[i] = 0;
}

int main() {
    n = read(), m = read(), q = read();
    int tot = 0, sqr = sqrt(n);
    for (int i = 1; i <= m; ++i) {
        int u = read(), v = read();
        ++du[u], ++du[v];
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for (int i = 1; i <= n; ++i) {
        if (du[i] > sqr)    id[i] = ++tot;
        for (auto& v : G[i])
            if (du[v] > sqr)    BigG[i].push_back(v);
    }
    for (int i = 1; i <= q; ++i) {
        int u = read(), w = read();
        a[u] += w;
        if (du[u] <= sqr) { // u是小点
            bool flag = 1;
            for (auto& v : G[u]) { // 直接暴力维护总图连的全部边
                if (du[v] > sqr)    mx[v] = max(mx[v], a[u]);
                if (a[v] > a[u])    flag = 0;
                else { // a[v] <= a[u] 说明v一定不是冠军了
                    if (a[v] == a[u])    flag = 0; // 说明u也不是冠军
                    loser(v, i);
                }
            }
            if (flag) {
                for (auto& v : BigG[u]) {
                    SmallG[id[v]][a[u]].push_back(u);
                }
                if (!win[u])    win[u] = i;
            }
        }
        else { // u是大点
            bool flag = 1;
            for (auto& v : BigG[u]) { // 遍历连接的大点
                if (a[v] > a[u]) flag = 0;
                else { // a[v] <= a[u] 说明v一定不是冠军了
                    if (a[v] == a[u])    flag = 0; // 说明u也不是冠军
                    loser(v, i);
                }
            }
            for (int k = a[u] - w + 1; k <= a[u]; ++k) { // 只有[a[u]-w+1,a[u]]这个区间内才可能失去冠军
                for (auto& v : SmallG[id[u]][k])
                    if (a[v] == k)    loser(v, i);
            }
            //  大点       小点
            if (flag && mx[u] < a[u] && !win[u])    win[u] = i;
        }
    }
    for (int i = 1; i <= n; ++i)    loser(i, q);
    for (int i = 1; i <= n; ++i)    print(ans[i]);

    return 0;
}