A – Lifeguards

先可以想到把所有的包含的区间给去掉，然后来关注如何进行 DP。我们可以考虑设置 \(dp[i][j]\) 为前 \(i\) 个区间里删掉了 \(j\) 个区间的最优答案。正常我们做「选择 \(j\) 个区间」的问题会比较简单，然而 \(k \leq 200\) 就很麻烦。

我们如何来进行转移呢？首先，我们转移时可以考虑从 \(dp[x][y]\) 来进行转移而不只是经典的 \(dp[i – 1][j – 1] \text{或} dp[i – 1][j]\)。如果使用经典转移，就很难去分开维护重叠信息。转移有个条件 \(i – j – 1 = x – y\)，比较显然，可以使用单调队列来进行维护。需要注意的是，我们要同时维护重叠、非重叠的信息。重叠的信息可以考虑直接在维护时减去一个右边界；而非重叠放在队列的 global array 里就可以了。

// LOJ2385.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5 + 200, MAX_K = 110;

typedef pair<int, int> pii;

int n, limit, dp[MAX_N][MAX_K], max_prod[MAX_N];
deque<pii> dq[MAX_N];

struct segment
{
    int l, r;
    bool operator<(const segment &rhs) const { return l < rhs.l || (l == rhs.l && r > rhs.r); }
} segs[MAX_N];

inline char gc()
{
    static char buf[1000000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++;
}

int read()
{
    int x = 0, f = 1;
    char ch = gc();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = gc();
    }
    while (isdigit(ch))
        x = (x << 3) + (x << 1) + ch - '0', ch = gc();
    return f * x;
}

int main()
{
    // freopen("2.in", "r", stdin);
    n = read(), limit = read();
    for (int i = 1; i <= n; i++)
        segs[i].l = read(), segs[i].r = read();
    sort(segs + 1, segs + 1 + n);
    int tot = 1;
    for (int i = 2; i <= n; i++)
        if (segs[i].r > segs[tot].r)
            segs[++tot] = segs[i];
    limit -= (n - tot), n = tot, limit = max(0, limit);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < min(limit + 1, i); j++)
        {
            int curt = i - j - 1;
            while (!dq[curt].empty() && segs[dq[curt].front().second].r < segs[i].l)
                // not overlap;
                max_prod[curt] = max(max_prod[curt], segs[dq[curt].front().second].r + dq[curt].front().first), dq[curt].pop_front();
            dp[i][j] = max(dp[i][j], max_prod[curt] + segs[i].r - segs[i].l);
            if (!dq[curt].empty())
                dp[i][j] = max(dp[i][j], segs[i].r + dq[curt].front().first);
            int val = dp[i][j] - segs[i].r;
            curt++;
            while (!dq[curt].empty() && dq[curt].back().first < val)
                dq[curt].pop_back();
            dq[curt].push_back(make_pair(val, i));
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < min(limit + 1, i); j++)
            if (i - j == n - limit)
                ans = max(ans, dp[i][j]);
    printf("%d\n", ans);
    return 0;
}

B – Cow at Large

这题就只想到了 \(\Theta(n^2)\) 的中点标记的方法，看题解发现竟然还能用点分治来搞，发现是个板子。

考虑当前根 \(u\)，对于 \(i\) 最近的叶子结点的距离为 \(g_i\)，则中点满足：

\[ g[i] \leq dep_i \text{and} dep_fa < g_i \]

然后有一个套路，就是 \(\sum d_i = 2S – 1, 1 = \sum d_i – 2\)，然后我们用艾弗森括号套上去即可。

// LOJ2386.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5 + 200;

int n, head[MAX_N], current, g[MAX_N], dep[MAX_N], deg[MAX_N], ans[MAX_N], siz[MAX_N], nodes[MAX_N << 1];
bool tag[MAX_N];

struct edge
{
    int to, nxt;
} edges[MAX_N << 1];

inline char gc()
{
    static char buf[1000000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++;
}

int read()
{
    int x = 0, f = 1;
    char ch = gc();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = gc();
    }
    while (isdigit(ch))
        x = (x << 3) + (x << 1) + ch - '0', ch = gc();
    return f * x;
}

void addpath(int src, int dst)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    head[src] = current++;
}

void dfs(int u, int fa)
{
    if (deg[u] == 1)
        g[u] = 0;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa)
            dfs(edges[i].to, u), g[u] = min(g[u], g[edges[i].to] + 1);
}

void overlap(int u, int fa)
{
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa)
            g[edges[i].to] = min(g[edges[i].to], g[u] + 1), overlap(edges[i].to, u);
}

int root, root_val;

void findRoot(int u, int fa, int capacity)
{
    siz[u] = 1;
    int max_com = 0;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa && !tag[edges[i].to])
            findRoot(edges[i].to, u, capacity), max_com = max(max_com, siz[edges[i].to]), siz[u] += siz[edges[i].to];
    if (max(max_com, capacity - siz[u]) < root_val)
        root_val = max(max_com, capacity - siz[u]), root = u;
}

int findRoot(int entry, int capacity) { return root = 0, root_val = 0x7fffffff, findRoot(entry, 0, capacity), root; }

inline int lowbit(int x) { return x & (-x); }

void update(int x, int d)
{
    x += MAX_N;
    for (; x <= MAX_N << 1; x += lowbit(x))
        nodes[x] += d;
}

int query(int x, int ret = 0)
{
    x += MAX_N;
    for (; x; x -= lowbit(x))
        ret += nodes[x];
    return ret;
}

void collect(int u, int fa, int dep)
{
    ans[u] += query(dep);
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa && !tag[edges[i].to])
            collect(edges[i].to, u, dep + 1);
}

void confirm(int u, int fa, int dep)
{
    update(g[u] - dep, 2 - deg[u]);
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa && !tag[edges[i].to])
            confirm(edges[i].to, u, dep + 1);
}

void clear(int u, int fa, int dep)
{
    update(g[u] - dep, deg[u] - 2), siz[u] = 1;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa && !tag[edges[i].to])
            clear(edges[i].to, u, dep + 1), siz[u] += siz[edges[i].to];
}

int cnt;

void solve(int u, int capacity)
{
    tag[u] = true; //, printf("TAGGED Another One: %d\n", cnt), cnt++;
    stack<int> sons;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (!tag[edges[i].to])
            collect(edges[i].to, u, 1), confirm(edges[i].to, u, 1), sons.push(edges[i].to);
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (!tag[edges[i].to])
            clear(edges[i].to, u, 1);
    update(g[u], 2 - deg[u]);
    while (!sons.empty())
    {
        int v = sons.top();
        collect(v, u, 1), confirm(v, u, 1), sons.pop();
    }
    ans[u] += query(0), update(g[u], deg[u] - 2);
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (!tag[edges[i].to])
            clear(edges[i].to, u, 1);
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (!tag[edges[i].to])
            solve(findRoot(edges[i].to, siz[edges[i].to]), siz[edges[i].to]);
}

int main()
{
    /*
    freopen("2.in", "r", stdin);
    freopen("2.out", "w", stdout);
    */
    memset(head, -1, sizeof(head)), memset(g, 0x3f, sizeof(g));
    n = read();
    for (int i = 1, u, v; i <= n - 1; i++)
        u = read(), v = read(), addpath(u, v), addpath(v, u), deg[u]++, deg[v]++;
    dfs(1, 0), overlap(1, 0), solve(findRoot(1, n), n);
    for (int i = 1; i <= n; i++)
        if (deg[i] == 1)
            puts("1");
        else
            printf("%d\n", ans[i]);
    return 0;
}

C – Sprinklers

画一下图，发现区域有点像一个反比例函数的图像，我们维护一下边界得到：

\[ \sum_{i = 1}^n \sum_{j = lft_i}^{rig_i} (c_j – i)(j – lft_i + 1) \]

其中，\(c_j\) 就是能到达的最下的下边缘。拆式子搞前缀和即可。

// LOJ2387.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5 + 200, mod = 1e9 + 7, inv2 = (mod + 1) >> 1;

typedef long long ll;

int n, yi[MAX_N], lft[MAX_N], rig[MAX_N], row[MAX_N], col[MAX_N], pre[MAX_N];

int main()
{
    scanf("%d", &n);
    for (int i = 1, x, y; i <= n; i++)
        scanf("%d%d", &x, &y), yi[x] = y;
    int val = n;
    for (int i = 0; i < n; i++)
        val = min(val, yi[i] + 1), lft[i + 1] = val;
    val = 0;
    for (int i = n - 1; i >= 0; i--)
        val = max(val, yi[i]), rig[i] = val;

    for (int i = 1, ptr = n - 1; i < n; i++)
    {
        while (i > rig[ptr])
            ptr--;
        col[i] = ptr + 1, row[i] = lft[i] - 1;
    }

    int ans = 0;
    for (int i = 1; i < n; i++)
        pre[i] = (0LL + pre[i - 1] + 1LL * col[i] * i % mod) % mod;
    for (int i = 1; i < n; i++)
        ans = (0LL + ans + (pre[rig[i]] + mod - pre[lft[i] - 1]) % mod) % mod;
    // printf("%d\n", ans);
    for (int i = 1; i < n; i++)
        ans = (0LL + ans + mod - 1LL * i * (lft[i] + rig[i]) % mod * (rig[i] - lft[i] + 1) % mod * inv2 % mod) % mod;
    // printf("%d\n", ans);
    for (int i = 1; i < n; i++)
        ans = (0LL + ans + 1LL * row[i] * i % mod * (rig[i] - lft[i] + 1) % mod) % mod;
    // printf("%d\n", ans);
    for (int i = 1; i < n; i++)
        pre[i] = (0LL + pre[i - 1] + col[i]) % mod;
    for (int i = 1; i < n; i++)
        ans = (0LL + ans + mod - 1LL * row[i] * ((0LL + pre[rig[i]] + mod - pre[lft[i] - 1]) % mod) % mod) % mod;
    printf("%d\n", ans);
    return 0;
}