B. Cannon

G. League of Legends

题意：给定n个区间，要求将它们分成k组，每组之间有交，最大化每组交长度之和

简化问题，对于如果一个大区间能够完整包含某个小区间，则该大区间只有两种最优决策：

单独归为一组，贡献r-l
与任意一个其包含的小区间归为一组，不对结果产生影响

可以用反证法证明结论，假如大区间和其他区间归为一组，那么将该大区间移出该组，该组的交一定不下降，再放入其包含的小区间组中，小区间所在的组的交也不下降，即大小区间在同一组的决策一定最优

于是可以把所有大区间取出来，单独讨论所有小区间，可以发现，若将剩下的区间按照左端点从小到大排序，其右端点也一定是有序的，接着考虑dp，$f[i][j]$表示考虑前i个区间，分成j组的最优答案，而一组的贡献只与最左和最右两个区间相关，显然有转移$f[k][j+1]=\max\limits_{r[i+1]-l[k]>0} \{f[i][j]+r[i+1]-l[k]\}$

是一个比较模板的单调队列优化dp，对于每个j维护一个单调队列，维护队列中$f[i][j]+r[i+1]$单调递减，可以用双向队列deque实现

最后把大小区间的情况合并，枚举单独成组的大区间个数即可统计答案

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()

using namespace std;
typedef pair<int, int> pii;

const int N = 5e3 + 5, INF = 0x3f3f3f3f;

struct Interval {
    int l, r;
    bool operator < (Interval &I) const {
        if (l != I.l) return l < I.l;
        else return r > I.r;
    }
}a[N];

int n, k, m, p;

int f[N][N];

vector<Interval> V;
vector<int> G;
int sum[N];

deque<int> q[N];

int main() {
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &a[i].l, &a[i].r);
    }
    sort(a + 1, a + 1 + n);
    int nr;
    for (int i = n; i >= 1; i--) {
        if (i == n || a[i].r < nr) {
            V.push_back(a[i]);
            nr = a[i].r;
        }
        else G.push_back(a[i].r - a[i].l);
    }

    V.push_back({-1, -1});
    sort(all(V));

    sort(all(G), [&](int u, int v) {
        return u > v;
    });
    m = V.size() - 1; p = G.size();
    for (int i = 1; i <= p; i++) sum[i] = sum[i - 1] + G[i - 1];
    memset(f, -0x3f, sizeof f);

    for (int i = 1; i <= m; i++) {
        for (int j = min(i, k); j >= 2; j--) {
            while(!q[j - 1].empty() && V[q[j - 1].front() + 1].r <= V[i].l) q[j - 1].pop_front();
            if (!q[j - 1].empty()) {
                f[i][j] = f[q[j - 1].front()][j - 1] + V[q[j - 1].front() + 1].r - V[i].l;
                while(!q[j].empty() && (f[i][j] + V[i + 1].r >= f[q[j].back()][j] + V[q[j].back() + 1].r)) q[j].pop_back();
                q[j].push_back(i);
            }
        }
        if (V[1].r - V[i].l > 0) {
            f[i][1] = V[1].r - V[i].l;
            while(!q[1].empty() && (f[i][1] + V[i + 1].r >= f[q[1].back()][1] + V[q[1].back() + 1].r)) q[1].pop_back();
            q[1].push_back(i);
        }
    }
    int ans = 0;
    for (int i = 0; i <= min(p, k); i++) ans = max(ans, f[m][k - i] + sum[i]);
    cout << ans << endl;
    return 0;
}

J. Product of GCDs

K. Stack

L. WeChat Walk

题意：给定n个人之间的好友关系，每次单点增加一个人的步数，求每个人在自己列表里保持冠军的时间

考虑临界值$B=\sqrt n$，以B为基准对点分类，分为度数>=B的大点和<B的小点，同时观察到每次修改至多使一个人从非冠军变为冠军，也就是说冠军的变化次数是$O(n)$的，意味着我们可以在每次修改后都更新冠军情况，保持所有人的冠军情况是最新的，从而求出答案。

对于小点，每次修改后主动查询相邻的所有点并更新这些点的冠军情况$O(B)$，并且将修改后的权值信息传递给相邻的大点$O(B)$，记录在对应大点的集合中

对于大点，主动查询周围所有大点并更新这些点的冠军情况$O(B)$，然后查询周围所有可能对该点冠军情况相互影响的小点，这样的信息在所有大点的集合中的数量为$O(nB)$，且不会重复查询，因此复杂度保证。为了避免重复查询，可以根据权值再将集合分成多个区间，每次将点u增加v后，仅查询$[val[u]+1,val[u]+v]$区间

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5, BB = 300;

vector<int> G[N], B[N];
vector<int> vc[501][10001];

bool big[N];

int n, m, q, val[N], cha[N], ans[N], mxneigh[N], TT, mp[N];

void modify(int x, int y, int type) {
    if (type == 0) {
        if (cha[x] != -1) ans[x] += y - cha[x];
        cha[x] = -1;
    } else {
        if (cha[x] == -1) cha[x] = y;
    }
}

int main() {
    scanf("%d %d %d", &n, &m, &q);
    for (int i = 1; i <= m; i++) {
        int u, v; scanf("%d %d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) {
        if (G[i].size() >= BB) {
            big[i] = 1;
            mp[i] = TT++;
            for (int to : G[i]) {
                B[to].push_back(i);
            }
        }
    }
    memset(cha, -1, sizeof(cha));
    for (int i = 1; i <= q; i++) {
        int u, v; scanf("%d %d", &u, &v);
        if (cha[u] != -1) {
            val[u] += v;
            if (!big[u]) {
                for (int to : B[u]) {
                    vc[mp[to]][val[u]].push_back(u);
                }
            }
            continue;
        }
        if (!big[u]) {
            val[u] += v;
            bool can = 1;
            for (int to : G[u]) {
                if (cha[to] && val[to] <= val[u]) modify(to, i, 0);
                if (val[to] >= val[u]) can = 0;
            }
            if (can) {
                modify(u, i, 1);
                for (int to : B[u]) {
                    vc[mp[to]][val[u]].push_back(u);
                }
            }
        } else {
            bool can = 1;
            for (int to : B[u]) {
                if (cha[to] && val[to] <= val[u] + v) modify(to, i, 0);
                if (val[to] >= val[u] + v) can = 0;
            }
            for (int j = val[u] + 1; j <= val[u] + v; j++) {
                for (int x : vc[mp[u]][j]) {
                    if (val[x] <= val[u] + v) modify(x, i, 0);
                }
            }
            if (can) {
                modify(u, i, 1);
            }
            val[u] += v;
        }
    }
    for (int i = 1; i <= n; i++) modify(i, q, 0);
    for (int i = 1; i <= n; i++) printf("%d\n", ans[i]);
    return 0;
}