标签：return int 题解 void ret SON Jan 2018 define

USACO 2018 Jan Solution

目录

• USACO 2018 Jan Solution
  • 更好的阅读体验戳此进入
  • 题面 Luogu 链接
  • LG-P4188 [USACO18JAN]Lifeguards S
    • 题面
    • Solution
    • Code
  • LG-P4182 [USACO18JAN]Lifeguards P
    • 题面
    • Examples
    • Solution
    • Code
  • LG-P4181 [USACO18JAN]Rental Service S
    • 题面
    • Examples
    • Solution
    • Code
  • LG-P6111 [USACO18JAN]MooTube S
    • 题面
    • Examples
    • Solution
    • Code
  • LG-P4185 [USACO18JAN]MooTube G
    • 题面
    • Examples
    • Solution
    • Code
  • LG-P4184 [USACO18JAN]Sprinklers P
    • 题面
    • Examples
    • Solution
    • Code
  • LG-P4187 [USACO18JAN]Stamp Painting G
    • 题面
    • Examples
    • Solution
    • Code
  • LG-P4186 [USACO18JAN]Cow at Large G
    • 题面
    • Examples
    • Solution
    • Code
  • LG-P4183 [USACO18JAN]Cow at Large P
    • 题面
    • Examples
    • Solution
    • Code
  • UPD

更好的阅读体验戳此进入

题面 Luogu 链接

LG-P4188 [USACO18JAN]Lifeguards S

题面

给定 $ n $ 个左闭右开的区间，在范围 $ [0, 10^{9}] $（Luogu 上的翻译写错了，多写了个 $ 0 $）内，最大化删去其中一个区间后剩下区间并起来的长度，求最大值。

$ 1 \le n \le 10^5 $。

Input_1

3
5 9
1 4
3 7

Output_1

7

Solution

估计你们读完题之后也能想到线段树的做法，线段树做法十分显然，离散化之后建个权值线段树，然后所有线段插进去再每次删一个区间求 $ \ge 1 $ 的对应的真实区间长度和，常数比较大但是是妥妥的 $ O(n \log n) $ 能过，不过有一个更好写的做法，不难想到可以转化为求哪个线段独立覆盖的范围最小，于是考虑建立一个差分数组，把每段区间糊上去，差分加一下之后再求个前缀和，注意这里的前缀和是若 $ d_i = 1 $ 那么加上 $ i $ 到 $ i + 1 $ 对应的真实区间的长度，否则加 $ 0 $，这样就可以查出来每个线段的独立覆盖范围，然后取最优即可，离散化是 $ O(n \log n) $，求解是线性的，常数极小。

Code

#define _USE_MATH_DEFINES
#include <bits/extc++.h>

#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}

using namespace std;
using namespace __gnu_pbds;

mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

template< typename T = int >
inline T read(void);

struct Line{
    int l, r;
    friend const bool operator < (const Line &a, const Line &b){return a.l < b.l;}
}a[110000];
vector < int > pos;
int N;
int d[210000];
int sum[210000];

int main(){
    N = read();
    for(int i = 1; i <= N; ++i)a[i].l = read(), a[i].r = read(), pos.emplace_back(a[i].l), pos.emplace_back(a[i].r);
    sort(pos.begin(), pos.end());
    auto endpos = unique(pos.begin(), pos.end());
    int siz = distance(pos.begin(), endpos);
    for(int i = 1; i <= N; ++i)
        a[i].l = distance(pos.begin(), upper_bound(pos.begin(), endpos, a[i].l)),
        a[i].r = distance(pos.begin(), upper_bound(pos.begin(), endpos, a[i].r));
    for(int i = 1; i <= N; ++i)d[a[i].l]++, d[a[i].r]--;
    int tot(0);
    for(int i = 1; i < siz; ++i){
        d[i] += d[i - 1];
        if(d[i])tot += pos.at(i + 1 - 1) - pos.at(i - 1);
        if(d[i] == 1)sum[i] += pos.at(i + 1 - 1) - pos.at(i - 1);
        sum[i] += sum[i - 1];
    }int mx(-1);
    for(int i = 1; i <= N; ++i)mx = max(mx, tot - (sum[a[i].r - 1] - sum[a[i].l - 1]));
    printf("%d\n", mx);
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    short flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

LG-P4182 [USACO18JAN]Lifeguards P

题面

加强版来咯

给定 $ n $ 个左闭右开的区间，在范围 $ [0, 10^{9}] $ 内，最大化删去其中 $ k $ 个区间后剩下区间并起来的长度，求最大值。

$ 1 \le n \le 10^5, 1 \le k \le \min(100, n) $。

Examples

Input_1

3 2
1 8
7 15
2 14

Output_1

12

Solution

首先不难想到对于区间 $ [l_1, r_1), [l_2, r_2) $ 且 $ l_1 \le l_2 \land r_2 \le r_1 $ 那么删去 $ [l_2, r_2] $ 答案一定不变，于是可以直接全部删去，并将 $ k \leftarrow k - 1 $。

然后 DP 显然，也很好想到一个状态 $ dp(i, k) $ 表示考虑前 $ i $ 个区间，删去其中的 $ k $ 个的最优值，然后发现这玩意没有固定具体怎么删没法转移，然后就想到在原来的状态基础上钦定必须选择第 $ i $ 个区间，然后需要把区间优先按左端点，再按右端点排序，这样我们就会发现最开始去掉那些区间的作用了，去掉之后现在我们剩下的区间排序后一定满足对于 $ l $ 的升序一定也满足 $ r $ 升序，不满足的已经被我们删掉了。于是此时转移比较显然：$ dp(i, k) = \max{ dp(j, k - (i - j - 1)) + r_i - \max(l_i, r_j) }, j \in [i - k - 1, i - 1] $。这玩意复杂度显然是 $ O(nk^2) $ 的，显然不正确。

考虑优化，状态没什么可优化的，于是考虑优化转移，我们尝试提出来与转移时的 $ j $ 无关的项，令 $ \xi = i - k - 1 $，于是有 $ dp(i, k) = \max{ dp(j, j - \xi) + r_i - \max(l_i, r_j) }, j \in [i - k - 1, i - 1] $。也就是说我们要在 $ \xi = i - k - 1 $ 的前提下，换句话说就是以前的 $ dp $ 中前后索引的差为 $ \xi $ 的值中找到后面式子的最大值进行转移，这个东西简单分类讨论一下就是如果 $ l_i \ge r_j $（或者理解为区间无交）那么就是要最大化 $ dp(j, j - \xi) $。反之需要最大化 $ dp(j, j - \xi) - r_j $。

所以我们直接对前者维护一个最大值（因为我们的区间之间使有序的，所以如果对于之前的区间已经无交了，对于现在的一定也无交），后者则维护一个单调队列单调栈单调双端队列，每次处理时先把对应单调双端队列队头中所有不合法的，也就是不交的弹出然后更新不交区间里面的最大值。然后用交的和不交的里的最大值更新当前 $ dp $，每次处理完当前的 $ dp $ 就把当前的丢到对应的单调双端队列里，这时我们会按照双端队列直接把队尾不优于当前的直接丢掉而不是保留下来等待不交时更新不交的最大值，这个的原因我想了很久，感性地证明了一下，如下：

如果你仔细想一下就会发现这个算法有一点问题，首先我们在最初的找单调双端队列里面的队头不合法的值的时候，我们时按照 $ val $ 的大小，也就是 $ dp(j, j - \xi) - r_j $ 的大小维护的单调双端队列，但是我们更新不交最大值的时候需要的是与其不交区间里的最大值（废话），难道就不会存在一种情况，即队头的区间 $ val $ 更大，但是区间靠右，然而队头之后某个区间 $ val $ 较小却区间靠左，也就是存在一种情况单调优先队列的后面已经存在了不交的区间但是却被队头的相交区间阻挡了，这样的话我们难道不会少更新一些值吗？还有就是在把当前的 $ dp $ 压入单调双端队列的时候，我们会把队尾不优于当前值的直接踢掉，这个时候却没有考虑到在后面更新时这些区间可能会从相交变成不交，从而可能性地去更新不交的最大值，但是现在这被我们丢掉了，难道不会使答案更劣吗？

这几个问题困扰了我很久，完全没有头绪，直到发现了一个性质我才大概能感性理解这个贪心的正确性。

显然当我们转移的时候，如果转移的这个 $ j $ 是与 $ i $ 交的，那么最优的 $ j $ 一定是 $ l_j $ 最小的 $ j $，当然经过我们的处理之后同时也是 $ r_j $ 最小的。这个不难理解，因为我们处理过包含的区间，所以 $ i, j $ 相交那么最终这两段组成的区间一定是 $ [l_j, r_i) $，那么 $ l_j $ 尽量小一定更优，所以 $ j + 1, j + 2, \cdots, i - 1 $ 的区间都是没必要选的，选了也不会有任何贡献。

此时我们再回到刚才的考虑，我们的单调优先队列维护的是最大值，而最大值一定是 $ l $ 和 $ r $ 最小的，那么我们实际上也可以感性地认为更左的区间在单调双端队列里也更靠前，如果这个成立那么我们刚才的所有问题也就很显然是不需要考虑得了，这样的话我们弹出的队头一定是最先变得不交的，被丢掉的区间也一定是更劣的。

于是这个贪心（应该）是正确的。

当然上面这一大段证明都完全是我口糊的，不保证正确性，也不够理性和严谨，期待一个更严谨的证明。

Code

#define _USE_MATH_DEFINES
#include <bits/extc++.h>

#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}

using namespace std;
using namespace __gnu_pbds;

mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

template< typename T = int >
inline T read(void);

struct Line{
    int l, r;
    friend const bool operator < (const Line &a, const Line &b){if(a.l == b.l)return a.r < b.r; return a.l < b.l;}
}line[110000];
list < Line > _line;
int N, K;
int cnt(0);
struct Status{int idx; int val;};
deque < Status > bst[110000];
int mx[110000];
int dp[110000][110];

int main(){
    N = read(), K = read();
    for(int i = 1; i <= N; ++i){
        int l = read(), r = read();
        _line.emplace_back(Line{l, r});
    }_line.sort();
    for(auto it = next(_line.begin()); it != _line.end();)
        if(it->r <= prev(it)->r)it = _line.erase(it), --K; else ++it;
    for(auto ln : _line)line[++cnt] = ln;
    N = cnt; K = max(0, K);
    for(int i = 1; i <= N; ++i){
        for(int k = 0; k <= min(i - 1, K); ++k){
            int xi = i - k - 1;
            while(!bst[xi].empty() && line[bst[xi].front().idx].r < line[i].l){
                auto tp = bst[xi].front(); bst[xi].pop_front();
                mx[xi] = max(mx[xi], tp.val + line[tp.idx].r);
            }
            dp[i][k] = max({
                dp[i][k],
                mx[xi] + line[i].r - line[i].l,
                bst[xi].empty() ? -1 : bst[xi].front().val + line[i].r
            });
            int val = dp[i][k] - line[i].r;
            int pos = i - k;
            while(!bst[pos].empty() && bst[pos].back().val < val)bst[pos].pop_back();
            bst[pos].push_back(Status{i, val});
        }
    }int ans(-1);
    for(int i = N - K; i <= N; ++i)ans = max(ans, dp[i][K - (N - i)]);
    printf("%d\n", ans);
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    short flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

LG-P4181 [USACO18JAN]Rental Service S

题面

sssmzy 有 $ n $ 包彩虹犇，彩虹犇可以产生 zpair 最爱的彩虹糖。在一天中，$ n $ 只彩虹犇有 $ c_i $ 表示其当天可以产生 $ c_i $ 包彩虹糖。有 $ m $ 只 zpair 想要买彩虹糖，每只 zpair 有 $ q_i $ 和 $ p_i $，表示第 $ i $ 只 zpair 当天最多可以按 $ p_i $ 元每包购买 $ q_i $ 包彩虹糖（可以分裂开卖，也就是可以卖 $ \lt q_i $ 包，价格不变）。还存在 $ r $ 只 zpar，每只 zpar 有 $ r_i $，表示其会以 $ r_i $ 元的价格租用一天任意一只彩虹犇，请你帮 sssmzy 最大化得到的钱数并输出钱数。

$ 1 \le n, m, r \le 10^5, 1 \le c_i, p_i, q_i, r_i \le 10^6 $。

$ n, m, r $

$ c_1 $

$ c_2 $

$ \cdots $

$ q_1, p_1 $

$ q_2, p_2 $

$ \cdots $

$ r_1 $

$ r_2 $

$ \cdots $

Examples

Input_1

5 3 4
6
2
4
7
1
10 25
2 10
15 15
250
80
100
40

Output_1

725

Solution

大水题，贪心 + 模拟，且贪心也很显然，只是写起来比较恶心，有语法题那味了，开始以为是我实现太差了，翻了一下题解区也都挺长。

显然几个贪心策略就是：

1. 如果要卖彩虹犇，一定优先卖给 $ r_i $ 最高的 zpar。
2. 如果要卖彩虹糖，一定优先卖给 $ p_i $ 最高的 zpair。（卖的过程可能类似 ODT 的 split？）
3. 如果要保留彩虹犇，一定优先保留日产彩虹糖更多的犇。

然后就没啥可说的了，精细实现就可以了，有很多需要判断的地方比如 $ r $ 和 $ n $ 取 $ \min $ 之类的，很简单，写起来需要用点脑子而已。

复杂度 $ O(n) $，记得开 long long。

Code

#define _USE_MATH_DEFINES
#include <bits/extc++.h>

#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}

using namespace std;
using namespace __gnu_pbds;

mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

#define int ll

template< typename T = int >
inline T read(void);

int N, M, R;
int c[110000];
struct Milk{
    int pri, siz;
    friend const bool operator < (const Milk &a, const Milk &b){
        if(a.pri == b.pri)return a.siz > b.siz;
        return a.pri > b.pri;
    }
}mlk[110000];
int buy[110000];
int cur(0);

signed main(){
    N = read(), M = read(), R = read();
    for(int i = 1; i <= N; ++i)c[i] = read();
    for(int i = 1; i <= M; ++i)mlk[i].siz = read(), mlk[i].pri = read();
    for(int i = 1; i <= R; ++i)buy[i] = read();
    sort(c + 1, c + N + 1, greater < int >());
    sort(mlk + 1, mlk + M + 1);
    sort(buy + 1, buy + R + 1, greater < int >());
    int unsel(0), sel(N);
    int curus(0);
    int curs(N);
    int lftmlk(0);
    int curmlkn(0);
    int mx(-1);
    for(int i = 1; i <= min(N, R); ++i)cur += buy[i];
    do{
        while(curus < unsel)lftmlk += c[++curus];
        while(lftmlk && curmlkn < M){
            ++curmlkn;
            if(lftmlk >= mlk[curmlkn].siz)
                cur += mlk[curmlkn].siz * mlk[curmlkn].pri,
                lftmlk -= mlk[curmlkn].siz;
            else
                cur += lftmlk * mlk[curmlkn].pri,
                mlk[curmlkn].siz -= lftmlk,
                lftmlk = 0,
                --curmlkn;
        }
        while(curs > sel){
            if(curs <= R)cur -= buy[curs];
            --curs;
        }
        mx = max(mx, cur);
        // printf("sel:%lld, unsel:%lld, cur=%lld\n", sel, unsel, cur);
        --sel, ++unsel;
    }while(unsel <= N || sel >= 0);
    printf("%lld\n", mx);
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    short flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

LG-P6111 [USACO18JAN]MooTube S

题面

给定 $ n $ 个点的树形结构，有边权，$ q $ 次询问每次给定 $ k_i, v_i $，求 $ v_i $ 节点到其它所有节点中路径上边权最小值不小于 $ k_i $ 的点的数量。

我知道你很急，但是你别急，我知道你有更优的方法，但是你别优，看看数据范围，想点普及难度的做法。

$ 1 \le n, q \le 5 \times 10^3 $，其它数据均在 $ 10^9 $ 以内，$ 2s $ 时限。

Examples

Input_1

4 3
1 2 3
2 3 2
2 4 4
1 2
4 1
3 1

Output_1

3
0
2

Solution

来个最无脑的做法，每个点开个 vector dfs 一遍维护到其它 $ n - 1 $ 个点路径边权最小值，然后排个序的话就可以 $ O(\log n) $ 查询，不排序就是 $ O(n) $ 查询，最终复杂度 $ O(n^2 \log n + q \log n) $ 或 $ O(n(n + q)) $，两秒时限随便过。

Code

#define _USE_MATH_DEFINES
#include <bits/extc++.h>

#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}

using namespace std;
using namespace __gnu_pbds;

mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

template< typename T = int >
inline T read(void);

struct Edge{
    Edge* nxt;
    int to;
    int val;
    OPNEW;
}ed[11000];
ROPNEW(ed);
Edge* head[5100];
vector < int > vert[5100];
int N, Q;

void dfs(int rt, int p, int fa = 0, int cur = 0){
    if(cur)vert[rt].emplace_back(cur);
    for(auto i = head[p]; i; i = i->nxt)
        if(SON != fa)dfs(rt, SON, p, cur ? min(cur, i->val) : i->val);
}

int main(){
    N = read(), Q = read();
    for(int i = 1; i <= N - 1; ++i){
        int s = read(), t = read(), val = read();
        head[s] = new Edge{head[s], t, val};
        head[t] = new Edge{head[t], s, val};
    }
    for(int i = 1; i <= N; ++i)dfs(i, i), sort(vert[i].begin(), vert[i].end());
    while(Q--){
        int dis = read(), p = read();
        printf("%d\n", (int)distance(lower_bound(vert[p].begin(), vert[p].end(), dis), vert[p].end()));
    }
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    short flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

LG-P4185 [USACO18JAN]MooTube G

题面

题意与上一题不变，数据范围加大了。

给定 $ n $ 个点的树形结构，有边权，$ q $ 次询问每次给定 $ k_i, v_i $，求 $ v_i $ 节点到其它所有节点中路径上边权最小值不小于 $ k_i $ 的点的数量。

$ 1 \le n, q \le 10^5 $，其它数据均在 $ 10^9 $ 以内，$ 1s $ 时限。

Examples

Input_1

4 3
1 2 3
2 3 2
2 4 4
1 2
4 1
3 1

Output_1

3
0
2

Solution

还是挺人类智慧的，全离线下来就行了。

不难想到对于 $ k $ 比较小的一定可以包含可以抵达的所有比当前 $ k $ 更大的 $ k $，所以考虑把询问离线下来按 $ k $ 降序，然后把每条边也离线下来按边权降序排列，然后对于每个询问的 $ k $，把所有不小于 $ k $ 的边权加进真正的图里，用并查集维护即可，至于查询的答案就是点所在并查集的大小减 $ 1 $。复杂度 $ O(n \log n + q \log q) $。

Code

#define _USE_MATH_DEFINES
#include <bits/extc++.h>

#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}

using namespace std;
using namespace __gnu_pbds;

mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

template< typename T = int >
inline T read(void);

class UnionFind{
private:
    int siz[110000];
    int fa[110000];
public:
    UnionFind(void){for(int i = 1; i <= 101000; ++i)fa[i] = i, siz[i] = 1;}
    int Find(int x){return x == fa[x] ? x : fa[x] = Find(fa[x]);}
    void Union(int origin, int son){
        if(Find(origin) == Find(son))return;
        siz[Find(origin)] += siz[Find(son)];
        fa[Find(son)] = Find(origin);
    }
    int GetSiz(int x){return siz[Find(x)] - 1;}
}uf;
struct Edge{
    int s, t;
    int val;
    friend const bool operator < (const Edge &a, const Edge &b){return a.val < b.val;}
};std::priority_queue < Edge > ed;
int ans[110000];
struct Query{
    int v, k;
    int idx;
    friend const bool operator < (const Query &a, const Query &b){return a.k > b.k;}
}qs[110000];
int N, Q;

int main(){
    N = read(), Q = read();
    for(int i = 1; i <= N - 1; ++i){
        int s = read(), t = read(), val = read();
        ed.push(Edge{s, t, val});
    }
    for(int i = 1; i <= Q; ++i){
        int k = read(), v = read();
        qs[i] = Query{v, k, i};
    }sort(qs + 1, qs + Q + 1);
    for(int i = 1; i <= Q; ++i){
        while(!ed.empty() && ed.top().val >= qs[i].k)
            uf.Union(ed.top().s, ed.top().t), ed.pop();
        ans[qs[i].idx] = uf.GetSiz(qs[i].v);
    }
    for(int i = 1; i <= Q; ++i)printf("%d\n", ans[i]);
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    short flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

LG-P4184 [USACO18JAN]Sprinklers P

题面

$ n \times n $ 的网格图（$ n $个格点，从 $ (0, 0) $ 到 $ (n - 1, n - 1) $），给定 $ n $ 个点的坐标 $ (i, j) $，保证任意两个坐标的横或纵均不相等，每个点会对 $ \forall(x, y), x \in [i, n - 1], y \in [j, n - 1] $ 进行洒水，对 $ \forall(x, y), x \in [0, i], y \in [0, j] $ 进行施肥，要求选出一片矩形，使得其中每个格点都既浇水又施肥，求方案数。

或者也可以描述为，给定 $ n $ 个关键点，要求选一个矩形使得其中左上右下各自至少有一个关键点，求方案数。

$ 1 \le n \le 10^5 $。

Examples

Input_1

5
0 4
1 1
2 2
3 0
4 3

Output_1

21

Solution

一道奇怪的题，最终可以转化为无脑推柿子。

首先借一个题解区的图：

不难发现一个妙妙性质，即在第 $ i $ 行里，我们假设可行的矩形的左右端点为 $ [l_i, r_i] $，那么 $ l_i $ 即为在其不在其下面的所有关键点横坐标的最小值，$ r_i $ 为不在其上面的最大值，按照这个规律我们也可以处理出来对于每一列纵坐标可行的最小值 $ up_i $，然后可以写一个 $ O(n^4) $ 的类似二位数点矩形的东西，然后化简。令 $ (i, j) $ 为右下端点，$ (x, y) $ 为左上端点，有答案为：

\[\begin{aligned} \sum_{i = 1}^{n} \sum_{j = l_i}^{r_i} \sum_{y = l_i}^{j - 1} \sum_{x = up_y}^{i - 1} 1 &= \sum_{i = 1}^{n} \sum_{j = l_i}^{r_i} \sum_{y = l_i}^{j - 1}(i - up_y) \\ &= \sum_{i = 1}^{n}\left( \sum_{j = l_i}^{r_i}(j - l_i)i - \sum_{j = l_i}^{r_i} \sum_{y = l_i}^{j - 1}up_y \right) \\ &= \sum_{i = 1}^{n}\left( i\left( \dfrac{1}{2}(l_i + r_i)(r_i - l_i + 1) - (r_i - l_i + 1)l_i \right) - \sum_{j = l_i}^{r_i} \sum_{y = l_i}^{j - 1}up_y \right) \\ &= \sum_{i = 1}^{n}\left( i\left( \dfrac{1}{2}(r_i - l_i)(r_i - l_i + 1) \right) - \sum_{j = l_i}^{r_i} \sum_{y = l_i}^{j - 1}up_y \right) \end{aligned} \]

然后我们令 $ sum1_n = \sum_{i = 1}^{n}up_i $，再令 $ sum2_n = \sum_{i = 1}^{n}sum1_i $，有：

\[\begin{aligned} &\sum_{i = 1}^{n}\left( i\left( \dfrac{1}{2}(r_i - l_i)(r_i - l_i + 1) \right) - \sum_{j = l_i}^{r_i} \sum_{y = l_i}^{j - 1}up_y \right) \\ =& \sum_{i = 1}^{n}\left( i\left( \dfrac{1}{2}(r_i - l_i)(r_i - l_i + 1) \right) - \sum_{j = l_i}^{r_i}(sum1_{j - 1} - sum1_{l_i - 1}) \right) \\ =& \sum_{i = 1}^{n}\left( i\left( \dfrac{1}{2}(r_i - l_i)(r_i - l_i + 1) \right) - \sum_{j = l_i}^{r_i}sum1_{j - 1} + (r_i - l_i + 1)sum1_{l_i - 1} \right) \\ =& \sum_{i = 1}^{n}\left( i\left( \dfrac{1}{2}(r_i - l_i)(r_i - l_i + 1) \right) - \sum_{j = l_i - 1}^{r_i - 1}sum1_{j} + (r_i - l_i + 1)sum1_{l_i - 1} \right) \\ =& \sum_{i = 1}^{n}\left( i\left( \dfrac{1}{2}(r_i - l_i)(r_i - l_i + 1) \right) - sum2_{r_i - 1} + sum2_{l_i - 2} + (r_i - l_i + 1)sum1_{l_i - 1} \right) \end{aligned} \]

然后就成功从 $ O(n^4) $ 推到 $ O(n) $ 了。

Code

#define _USE_MATH_DEFINES
#include <bits/extc++.h>

#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}

using namespace std;
using namespace __gnu_pbds;

mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

#define MOD (ll)(1e9 + 7)
#define GetSum1(x) ((x) > 0 ? sum1[x] : 0)
#define GetSum2(x) ((x) > 0 ? sum2[x] : 0)

template< typename T = int >
inline T read(void);

int N;
int y[110000];
int l[110000], r[110000], up[110000];
ll sum1[110000];
ll sum2[110000];

int main(){
    N = read();
    for(int i = 1; i <= N; ++i){
        int rx = read() + 1, ry = read() + 1;
        y[rx] = ry;
    }l[0] = INT_MAX; r[N + 1] = -1;
    for(int i = 1; i <= N; ++i)l[i] = min(l[i - 1], y[i]);
    for(int i = N; i >= 1; --i)r[i] = max(r[i + 1], y[i]);
    int cur = r[1];
    for(int i = 1; i <= N; ++i)while(cur && cur >= l[i])up[cur] = i, --cur;
    for(int i = 1; i <= N; ++i)sum1[i] = (sum1[i - 1] + up[i]) % MOD;
    for(int i = 1; i <= N; ++i)sum2[i] = (sum2[i - 1] + sum1[i]) % MOD;
    ll ans(0);
    for(int i = 1; i <= N; ++i){
        ans = (ans + ((ll)r[i] - l[i]) * (r[i] - l[i] + 1) / 2ll % MOD * i % MOD) % MOD;
        ans = (ans - GetSum2(r[i] - 1) + GetSum2(l[i] - 2) + MOD) % MOD;
        ans = (ans + ((ll)r[i] - l[i] + 1) * GetSum1(l[i] - 1) % MOD) % MOD;
    }printf("%lld\n", ans);
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    short flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

LG-P4187 [USACO18JAN]Stamp Painting G

题面

给定 $ m $ 种颜色的长度为 $ k $ 的图章，涂一个长度为 $ n $ 的画布，每次可以涂一段长为 $ k $ 的区间，把这一段全变成对应的颜色，最后必须要涂满画布，求有多少种最终状态。

$ 1 \le n, m, k \le 10^6 $。

Examples

Input_1

3 2 2

Output_1

6

Solution

我们发现这样涂的最终状态一定为至少有一段长度为 $ k $ 的颜色相同的区间，然后其它位置可以是任何状态。发现直接求很难，考虑正难则反，令 $ dp(i) $ 表示考虑前 $ i $ 的长度有多少种没有连续 $ k $ 颜色相同区间的状态，显然有转移若 $ i \lt k \(，\) dp(i) = dp(i - 1) \times m $。若 $ i \ge k \(，\) dp(i) = \sum_{j = i - k + 1}^{i - 1}dp(j) \times (m - 1) $，后面这个柿子拿前缀和优化一下就行了，最终把总方案 $ m^n $ 减去 $ dp(n) $ 即为答案，复杂度 $ O(n) $。

这真的是紫色的题吗。。

Code

#define _USE_MATH_DEFINES
#include <bits/extc++.h>

#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}

using namespace std;
using namespace __gnu_pbds;

mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

#define MOD (ll)(1e9 + 7)

template< typename T = int >
inline T read(void);

int N, M, K;
ll dp[1100000];
ll sum[1100000];
ll qpow(ll a, ll b){
    ll ret(1), mul(a);
    while(b){
        if(b & 1)ret = ret * mul % MOD;
        b >>= 1;
        mul = mul * mul % MOD;
    }return ret;
}

int main(){
    N = read(), M = read(), K = read();
    dp[0] = sum[0] = 1;
    for(int i = 1; i <= N; ++i)
        dp[i] = i < K ? dp[i - 1] * M % MOD : (sum[i - 1] - sum[i - K] + MOD) % MOD * (M - 1) % MOD,
        sum[i] = (sum[i - 1] + dp[i]) % MOD;
    printf("%lld\n", (qpow(M, N) - dp[N] + MOD) % MOD);
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    short flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

LG-P4186 [USACO18JAN]Cow at Large G

题面

给定 $ n $ 个节点的树，zpair 初始在 $ S $ 节点上，对于树上每个度数为 $ 1 $ 的节点我们认为其为出口，zpair 如果到达出口即为成功逃脱，你可以在任意一些出口处各放置一只 sssmzy，每次 zpair 走到一个相邻节点，每只 sssmzy 也一样。如果 zpair 和 sssmzy 在某一时刻处于同一个节点或边上我们认为 zpair 被抓住了。求最少放几只 sssmzy 可以让 zpair 一定无法逃脱。

$ 2 \le n \le 10^5 $。

Examples

Input_1

7 1
1 2
1 3
3 4
3 5
4 6
5 7

Output_1

3

Solution

考虑当 zpair 走到某个节点时，若有至少一只 sssmzy 距离该店的路程不大于 zpair，那么 zpair 走到此处时一定可以被截住并无法往下走，所以我们考虑尽可能早地堵死 zpair 的所有可能路径。

考虑 DFS 预处理每个点深度 $ dep_i $，每个点所在子树中叶子节点最小深度 $ mn_i $，然后再次 DFS 对于每个节点如果 $ dep_i - 1 \ge mn_i - dep_i $ 那么在这里面子树里深度最浅的叶子节点放一个 sssmzy 一定可以在当前点堵死 zpair，此时 $ ans \leftarrow ans + 1 $，然后不再搜下去，这样即可统计出最终答案。

Code

#define _USE_MATH_DEFINES
#include <bits/extc++.h>

#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}

using namespace std;
using namespace __gnu_pbds;

mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

template< typename T = int >
inline T read(void);

int N, S;
int ans(0);
struct Edge{
    Edge* nxt;
    int to;
    OPNEW;
}ed[210000];
ROPNEW(ed);
Edge* head[110000];

int mn[110000];
int dep[110000];
int dfs_pre(int p = S, int fa = 0){
    dep[p] = dep[fa] + 1;
    if(!head[p]->nxt)mn[p] = dep[p];
    for(auto i = head[p]; i; i = i->nxt)
        if(SON != fa)
            mn[p] = min(mn[p], dfs_pre(SON, p));
    return mn[p];
}
void dfs(int p = S, int fa = 0){
    if(dep[p] > mn[p] - dep[p])return ++ans, void();
    for(auto i = head[p]; i; i = i->nxt)if(SON != fa)dfs(SON, p);
}
int main(){
    memset(mn, 0x3f, sizeof mn);
    N = read(), S = read();
    for(int i = 1; i <= N - 1; ++i){
        int s = read(), t = read();
        head[s] = new Edge{head[s], t};
        head[t] = new Edge{head[t], s};
    }if(!head[S]->nxt)printf("1\n"), exit(0);
    dfs_pre();
    dfs();
    printf("%d\n", ans);
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    short flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

LG-P4183 [USACO18JAN]Cow at Large P

题面

加强版又来咯

给定 $ n $ 个节点的树，zpair 初始在某个节点上，对于树上每个度数为 $ 1 $ 的节点我们认为其为出口，zpair 如果到达出口即为成功逃脱，你可以在任意一些出口处各放置一只 sssmzy，每次 zpair 走到一个相邻节点，每只 sssmzy 也一样。如果 zpair 和 sssmzy 在某一时刻处于同一个节点或边上我们认为 zpair 被抓住了。求在 zpair 在 $ 1 $ 到 $ n $ 节点上时，最少放几只 sssmzy 可以让 zpair 一定无法逃脱。

$ 1 \le n \le 7 \times 10^4 $。

Examples

Input_1

7
1 2
1 3
3 4
3 5
4 6
5 7

Output_1

3
1
3
3
3
1
1

Solution

好题，淀粉质。

首先延续一下上一题的结论，对于一个能堵住 sssmzy 的节点应该是符合 $ dis_{(u, root)} \ge dis_{(u, mn_u)} $，然后我们不难发现这东西对于一个深度最浅的满足条件的点，其子树内节点也满足，但是我们不想要考虑他们。在上一题我们是通过从根节点搜一下遇到第一个被标记的点就不继续搜下去了，但是我们这个时候这么搞肯定会寄，所以简单考虑一下不难发现要找到的点即为满足 $ dis_{(u, root)} \ge dis_{(u, mn_u)}, dis_{(fa, root)} \lt dis_{(fa, mn_u)} $，也就是父亲不满足此条件，对于每个 $ u $，找到所有满足此条件的点统计一下数量即为 $ u $ 的答案。

以上这些还都是比较好想的，后面就要开始人类智慧了。以上这个东西我们不可以想到，如果让符合条件的 $ u $ 的子树权值和为 $ 1 $，可能会更好统计一些，所以可能需要让很多点权之间互相抵消。这个时候会有一个很人类智慧的想法，使每个点节点权值为 $ 1 - \texttt{儿子数量} $，或者说 $ 2 - deg_u $。

比如这个图，我们显然这个 $ u $ 即为我们要计算的唯一的 $ u $，而其所有的子树也都满足条件，此时把所有权值求和刚好为 $ 1 $，这样的话我们就不需要判断是否为当前分支深度最低的满足的点，直接无脑加和即可。所以现在我们求的答案就是对于每个根节点 $ u $ 的：

\[\sum_{u \mid dis_{(u, root)} \ge dis_{(u, mn_u)}} 2 - deg_u \]

然后我们发现这个 $ dis $ 在以某个点为根的时候就是其 $ dep $，所以转化一下就是 $ dep_{root} \ge dep_{mn_u} - dep_u $，此时的 $ \sum_u 2 - deg_u $ 也就是 $ root $ 的答案了，这个时候就已经完全是点分治的形状了，分别维护左右两边的，按照值排序，然后对于每一个 $ dep_{root} $ 显然 $ dep_{mn_u} - dep_u $ 是一个前缀，随便维护一下即可，剩下的都是完全的点分治模板，你们肯定都会。

Code

#define _USE_MATH_DEFINES
#include <bits/extc++.h>

#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}

using namespace std;
using namespace __gnu_pbds;

mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

template< typename T = int >
inline T read(void);

int N;
struct Edge{
    Edge* nxt;
    int to;
    OPNEW;
}ed[210000];
ROPNEW(ed);
Edge* head[110000];

int ans[110000];
bool vis[110000];
int deg[110000], dep[110000], dleaf[110000];

void dfs_pre(int p = 1, int fa = 0){
    if(deg[p] == 1)dleaf[p] = 0;
    for(auto i = head[p]; i; i = i->nxt){
        if(SON == fa)continue;
        dfs_pre(SON, p);
        dleaf[p] = min(dleaf[p], dleaf[SON] + 1);
    }
}
void dfs_pre_from_root(int p = 1, int fa = 0){
    for(auto i = head[p]; i; i = i->nxt){
        if(SON == fa)continue;
        dleaf[SON] = min(dleaf[SON], dleaf[p] + 1);
        dfs_pre_from_root(SON, p);
    }
}

int mx[110000];
int siz[110000];
int rt(0);
void ResetRoot(void){rt = 0, mx[rt] = N;}
void dfs_rt(int p = 1, int fa = 0, int Siz = N){
    siz[p] = 1; mx[p] = 0;
    for(auto i = head[p]; i; i = i->nxt){
        if(SON == fa || vis[SON])continue;
        dfs_rt(SON, p, Siz);
        siz[p] += siz[SON];
        mx[p] = max(mx[p], siz[SON]);
    }mx[p] = max(mx[p], Siz - siz[p]);
    if(mx[p] < mx[rt])rt = p;
}

struct Status{
    int dep, val;
    friend const bool operator < (const Status &a, const Status &b){return a.dep < b.dep;}
}idx[110000], nod[110000];
int cnt(0);
void dfs_dep(int p, int fa, int cur = 0){
    dep[p] = cur;
    for(auto i = head[p]; i; i = i->nxt){
        if(SON == fa || vis[SON])continue;
        dfs_dep(SON, p, cur + 1);
    }
}
void dfs_upd(int p, int fa){
    idx[++cnt] = Status{dep[p], p},
    nod[cnt] = Status{dleaf[p] - dep[p], 2 - deg[p]};
    for(auto i = head[p]; i; i = i->nxt)if(SON != fa && !vis[SON])dfs_upd(SON, p);
}

void Cal(int p, int fa, int flag){
    cnt = 0;
    dfs_upd(p, fa);
    sort(idx + 1, idx + cnt + 1), sort(nod + 1, nod + cnt + 1);
    int sum(0), sp(0);
    for(int i = 1; i <= cnt; ++i){
        while(sp <= cnt - 1 && nod[sp + 1].dep <= idx[i].dep)sum += nod[++sp].val;
        ans[idx[i].val] += flag * sum;
    }
}
void Make(int p){
    vis[p] = true;
    dfs_dep(p, 0);
    Cal(p, 0, 1);
    for(auto i = head[p]; i; i = i->nxt){
        if(vis[SON])continue;
        Cal(SON, p, -1);
        ResetRoot();
        dfs_rt(SON, p, siz[SON]);
        Make(rt);
    }
}

int main(){
	// freopen("P4183_3.in", "r", stdin);
    N = read();
    for(int i = 1; i <= N - 1; ++i){
        int s = read(), t = read();
        head[s] = new Edge{head[s], t};
        head[t] = new Edge{head[t], s};
        ++deg[s], ++deg[t];
    }memset(dleaf, 0x3f, sizeof(dleaf));
    dfs_pre(); dfs_pre_from_root();
    ResetRoot(); dfs_rt(); /*dfs_rt(rt);*/ Make(rt);
    for(int i = 1; i <= N; ++i)printf("%d\n", deg[i] == 1 ? 1 : ans[i]);
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    short flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

UPD

update-2022_11_07 初稿

标签：return,int,题解,void,ret,SON,Jan,2018,define
From： https://www.cnblogs.com/tsawke/p/16945849.html