USACO 2018 Jan Solution

更好的阅读体验戳此进入

题面 Luogu 链接

LG-P4188 [USACO18JAN]Lifeguards S

题面

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

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

Input_1

xxxxxxxxxx
4
1
3
2
5 9
3
1 4
4
3 7

Output_1

xxxxxxxxxx
1
1
7

Solution

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

Code

xxxxxxxxxx
72
1
#define _USE_MATH_DEFINES
2
#include <bits/extc++.h>
3

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

11
using namespace std;
12
using namespace __gnu_pbds;
13

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

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

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

26
struct Line{
27
    int l, r;
28
    friend const bool operator < (const Line &a, const Line &b){return a.l < b.l;}
29
}a[110000];
30
vector < int > pos;
31
int N;
32
int d[210000];
33
int sum[210000];
34

35
int main(){
36
    N = read();
37
    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);
38
    sort(pos.begin(), pos.end());
39
    auto endpos = unique(pos.begin(), pos.end());
40
    int siz = distance(pos.begin(), endpos);
41
    for(int i = 1; i <= N; ++i)
42
        a[i].l = distance(pos.begin(), upper_bound(pos.begin(), endpos, a[i].l)),
43
        a[i].r = distance(pos.begin(), upper_bound(pos.begin(), endpos, a[i].r));
44
    for(int i = 1; i <= N; ++i)d[a[i].l]++, d[a[i].r]--;
45
    int tot(0);
46
    for(int i = 1; i < siz; ++i){
47
        d[i] += d[i - 1];
48
        if(d[i])tot += pos.at(i + 1 - 1) - pos.at(i - 1);
49
        if(d[i] == 1)sum[i] += pos.at(i + 1 - 1) - pos.at(i - 1);
50
        sum[i] += sum[i - 1];
51
    }int mx(-1);
52
    for(int i = 1; i <= N; ++i)mx = max(mx, tot - (sum[a[i].r - 1] - sum[a[i].l - 1]));
53
    printf("%d\n", mx);
54
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
55
    return 0;
56
}
57

58
template < typename T >
59
inline T read(void){
60
    T ret(0);
61
    short flag(1);
62
    char c = getchar();
63
    while(c != '-' && !isdigit(c))c = getchar();
64
    if(c == '-')flag = -1, c = getchar();
65
    while(isdigit(c)){
66
        ret *= 10;
67
        ret += int(c - '0');
68
        c = getchar();
69
    }
70
    ret *= flag;
71
    return ret;
72
}

LG-P4182 [USACO18JAN]Lifeguards P

题面

加强版来咯

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

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

Examples

Input_1

xxxxxxxxxx
4
1
3 2
2
1 8
3
7 15
4
2 14

Output_1

xxxxxxxxxx
1
1
12

Solution

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

然后 DP 显然，也很好想到一个状态 $dp(i,k)$$dp(i, k)$ 表示考虑前 $i$$i$ 个区间，删去其中的 $k$$k$ 个的最优值，然后发现这玩意没有固定具体怎么删没法转移，然后就想到在原来的状态基础上钦定必须选择第 $i$$i$ 个区间，然后需要把区间优先按左端点，再按右端点排序，这样我们就会发现最开始去掉那些区间的作用了，去掉之后现在我们剩下的区间排序后一定满足对于 $l$$l$ 的升序一定也满足 $r$$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]$$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(n{k}^2)$$O(nk^2)$ 的，显然不正确。

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

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

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

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

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

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

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

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

Code

xxxxxxxxxx
86
1
#define _USE_MATH_DEFINES
2
#include <bits/extc++.h>
3

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

11
using namespace std;
12
using namespace __gnu_pbds;
13

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

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

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

26
struct Line{
27
    int l, r;
28
    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;}
29
}line[110000];
30
list < Line > _line;
31
int N, K;
32
int cnt(0);
33
struct Status{int idx; int val;};
34
deque < Status > bst[110000];
35
int mx[110000];
36
int dp[110000][110];
37

38
int main(){
39
    N = read(), K = read();
40
    for(int i = 1; i <= N; ++i){
41
        int l = read(), r = read();
42
        _line.emplace_back(Line{l, r});
43
    }_line.sort();
44
    for(auto it = next(_line.begin()); it != _line.end();)
45
        if(it->r <= prev(it)->r)it = _line.erase(it), --K; else ++it;
46
    for(auto ln : _line)line[++cnt] = ln;
47
    N = cnt; K = max(0, K);
48
    for(int i = 1; i <= N; ++i){
49
        for(int k = 0; k <= min(i - 1, K); ++k){
50
            int xi = i - k - 1;
51
            while(!bst[xi].empty() && line[bst[xi].front().idx].r < line[i].l){
52
                auto tp = bst[xi].front(); bst[xi].pop_front();
53
                mx[xi] = max(mx[xi], tp.val + line[tp.idx].r);
54
            }
55
            dp[i][k] = max({
56
                dp[i][k],
57
                mx[xi] + line[i].r - line[i].l,
58
                bst[xi].empty() ? -1 : bst[xi].front().val + line[i].r
59
            });
60
            int val = dp[i][k] - line[i].r;
61
            int pos = i - k;
62
            while(!bst[pos].empty() && bst[pos].back().val < val)bst[pos].pop_back();
63
            bst[pos].push_back(Status{i, val});
64
        }
65
    }int ans(-1);
66
    for(int i = N - K; i <= N; ++i)ans = max(ans, dp[i][K - (N - i)]);
67
    printf("%d\n", ans);
68
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
69
    return 0;
70
}
71

72
template < typename T >
73
inline T read(void){
74
    T ret(0);
75
    short flag(1);
76
    char c = getchar();
77
    while(c != '-' && !isdigit(c))c = getchar();
78
    if(c == '-')flag = -1, c = getchar();
79
    while(isdigit(c)){
80
        ret *= 10;
81
        ret += int(c - '0');
82
        c = getchar();
83
    }
84
    ret *= flag;
85
    return ret;
86
}

LG-P4181 [USACO18JAN]Rental Service S

题面

sssmzy 有 $n$$n$ 包彩虹犇，彩虹犇可以产生 zpair 最爱的彩虹糖。在一天中，$n$$n$ 只彩虹犇有 $c_i$$c_i$ 表示其当天可以产生 $c_i$$c_i$ 包彩虹糖。有 $m$$m$ 只 zpair 想要买彩虹糖，每只 zpair 有 $q_i$$q_i$ 和 $p_i$$p_i$，表示第 $i$$i$ 只 zpair 当天最多可以按 $p_i$$p_i$ 元每包购买 $q_i$$q_i$ 包彩虹糖（可以分裂开卖，也就是可以卖 $<q_i$$\lt q_i$ 包，价格不变）。还存在 $r$$r$ 只 zpar，每只 zpar 有 $r_i$$r_i$，表示其会以 $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$$1 \le n, m, r \le 10^5, 1 \le c_i, p_i, q_i, r_i \le 10^6$。

$n,m,r$$n, m, r$

$c_1$$c_1$

$c_2$$c_2$

$\cdots$$\cdots$

$q_1,p_1$$q_1, p_1$

$q_2,p_2$$q_2, p_2$

$\cdots$$\cdots$

$r_1$$r_1$

$r_2$$r_2$

$\cdots$$\cdots$

Examples

Input_1

xxxxxxxxxx
13
1
5 3 4
2
6
3
2
4
4
5
7
6
1
7
10 25
8
2 10
9
15 15
10
250
11
80
12
100
13
40

Output_1

xxxxxxxxxx
1
1
725

Solution

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

显然几个贪心策略就是：

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

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

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

Code

xxxxxxxxxx
95
1
#define _USE_MATH_DEFINES
2
#include <bits/extc++.h>
3

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

11
using namespace std;
12
using namespace __gnu_pbds;
13

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

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
#define int ll
24

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

28
int N, M, R;
29
int c[110000];
30
struct Milk{
31
    int pri, siz;
32
    friend const bool operator < (const Milk &a, const Milk &b){
33
        if(a.pri == b.pri)return a.siz > b.siz;
34
        return a.pri > b.pri;
35
    }
36
}mlk[110000];
37
int buy[110000];
38
int cur(0);
39

40
signed main(){
41
    N = read(), M = read(), R = read();
42
    for(int i = 1; i <= N; ++i)c[i] = read();
43
    for(int i = 1; i <= M; ++i)mlk[i].siz = read(), mlk[i].pri = read();
44
    for(int i = 1; i <= R; ++i)buy[i] = read();
45
    sort(c + 1, c + N + 1, greater < int >());
46
    sort(mlk + 1, mlk + M + 1);
47
    sort(buy + 1, buy + R + 1, greater < int >());
48
    int unsel(0), sel(N);
49
    int curus(0);
50
    int curs(N);
51
    int lftmlk(0);
52
    int curmlkn(0);
53
    int mx(-1);
54
    for(int i = 1; i <= min(N, R); ++i)cur += buy[i];
55
    do{
56
        while(curus < unsel)lftmlk += c[++curus];
57
        while(lftmlk && curmlkn < M){
58
            ++curmlkn;
59
            if(lftmlk >= mlk[curmlkn].siz)
60
                cur += mlk[curmlkn].siz * mlk[curmlkn].pri,
61
                lftmlk -= mlk[curmlkn].siz;
62
            else
63
                cur += lftmlk * mlk[curmlkn].pri,
64
                mlk[curmlkn].siz -= lftmlk,
65
                lftmlk = 0,
66
                --curmlkn;
67
        }
68
        while(curs > sel){
69
            if(curs <= R)cur -= buy[curs];
70
            --curs;
71
        }
72
        mx = max(mx, cur);
73
        // printf("sel:%lld, unsel:%lld, cur=%lld\n", sel, unsel, cur);
74
        --sel, ++unsel;
75
    }while(unsel <= N || sel >= 0);
76
    printf("%lld\n", mx);
77
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
78
    return 0;
79
}
80

81
template < typename T >
82
inline T read(void){
83
    T ret(0);
84
    short flag(1);
85
    char c = getchar();
86
    while(c != '-' && !isdigit(c))c = getchar();
87
    if(c == '-')flag = -1, c = getchar();
88
    while(isdigit(c)){
89
        ret *= 10;
90
        ret += int(c - '0');
91
        c = getchar();
92
    }
93
    ret *= flag;
94
    return ret;
95
}

LG-P6111 [USACO18JAN]MooTube S

题面

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

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

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

Examples

Input_1

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

Output_1

xxxxxxxxxx
3
1
3
2
0
3
2

Solution

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

Code

xxxxxxxxxx
73
1
#define _USE_MATH_DEFINES
2
#include <bits/extc++.h>
3

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

11
using namespace std;
12
using namespace __gnu_pbds;
13

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

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

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

26
struct Edge{
27
    Edge* nxt;
28
    int to;
29
    int val;
30
    OPNEW;
31
}ed[11000];
32
ROPNEW(ed);
33
Edge* head[5100];
34
vector < int > vert[5100];
35
int N, Q;
36

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

43
int main(){
44
    N = read(), Q = read();
45
    for(int i = 1; i <= N - 1; ++i){
46
        int s = read(), t = read(), val = read();
47
        head[s] = new Edge{head[s], t, val};
48
        head[t] = new Edge{head[t], s, val};
49
    }
50
    for(int i = 1; i <= N; ++i)dfs(i, i), sort(vert[i].begin(), vert[i].end());
51
    while(Q--){
52
        int dis = read(), p = read();
53
        printf("%d\n", (int)distance(lower_bound(vert[p].begin(), vert[p].end(), dis), vert[p].end()));
54
    }
55
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
56
    return 0;
57
}
58

59
template < typename T >
60
inline T read(void){
61
    T ret(0);
62
    short flag(1);
63
    char c = getchar();
64
    while(c != '-' && !isdigit(c))c = getchar();
65
    if(c == '-')flag = -1, c = getchar();
66
    while(isdigit(c)){
67
        ret *= 10;
68
        ret += int(c - '0');
69
        c = getchar();
70
    }
71
    ret *= flag;
72
    return ret;
73
}

LG-P4185 [USACO18JAN]MooTube G

题面

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

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

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

Examples

Input_1

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

Output_1

xxxxxxxxxx
3
1
3
2
0
3
2

Solution

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

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

Code

xxxxxxxxxx
87
1
#define _USE_MATH_DEFINES
2
#include <bits/extc++.h>
3

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

11
using namespace std;
12
using namespace __gnu_pbds;
13

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

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

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

26
class UnionFind{
27
private:
28
    int siz[110000];
29
    int fa[110000];
30
public:
31
    UnionFind(void){for(int i = 1; i <= 101000; ++i)fa[i] = i, siz[i] = 1;}
32
    int Find(int x){return x == fa[x] ? x : fa[x] = Find(fa[x]);}
33
    void Union(int origin, int son){
34
        if(Find(origin) == Find(son))return;
35
        siz[Find(origin)] += siz[Find(son)];
36
        fa[Find(son)] = Find(origin);
37
    }
38
    int GetSiz(int x){return siz[Find(x)] - 1;}
39
}uf;
40
struct Edge{
41
    int s, t;
42
    int val;
43
    friend const bool operator < (const Edge &a, const Edge &b){return a.val < b.val;}
44
};std::priority_queue < Edge > ed;
45
int ans[110000];
46
struct Query{
47
    int v, k;
48
    int idx;
49
    friend const bool operator < (const Query &a, const Query &b){return a.k > b.k;}
50
}qs[110000];
51
int N, Q;
52

53
int main(){
54
    N = read(), Q = read();
55
    for(int i = 1; i <= N - 1; ++i){
56
        int s = read(), t = read(), val = read();
57
        ed.push(Edge{s, t, val});
58
    }
59
    for(int i = 1; i <= Q; ++i){
60
        int k = read(), v = read();
61
        qs[i] = Query{v, k, i};
62
    }sort(qs + 1, qs + Q + 1);
63
    for(int i = 1; i <= Q; ++i){
64
        while(!ed.empty() && ed.top().val >= qs[i].k)
65
            uf.Union(ed.top().s, ed.top().t), ed.pop();
66
        ans[qs[i].idx] = uf.GetSiz(qs[i].v);
67
    }
68
    for(int i = 1; i <= Q; ++i)printf("%d\n", ans[i]);
69
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
70
    return 0;
71
}
72

73
template < typename T >
74
inline T read(void){
75
    T ret(0);
76
    short flag(1);
77
    char c = getchar();
78
    while(c != '-' && !isdigit(c))c = getchar();
79
    if(c == '-')flag = -1, c = getchar();
80
    while(isdigit(c)){
81
        ret *= 10;
82
        ret += int(c - '0');
83
        c = getchar();
84
    }
85
    ret *= flag;
86
    return ret;
87
}

LG-P4184 [USACO18JAN]Sprinklers P

题面

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

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

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

Examples

Input_1

xxxxxxxxxx
6
1
5
2
0 4
3
1 1
4
2 2
5
3 0
6
4 3

Output_1

xxxxxxxxxx
1
1
21

Solution

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

首先借一个题解区的图：

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

然后我们令 $sum{1}_n=\sum _{i=1}^{n}u{p}_i$$sum1_n = \sum_{i = 1}^{n}up_i$，再令 $sum{2}_n=\sum _{i=1}^{n}sum{1}_i$$sum2_n = \sum_{i = 1}^{n}sum1_i$，有：

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

Code

xxxxxxxxxx
72
1
#define _USE_MATH_DEFINES
2
#include <bits/extc++.h>
3

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

11
using namespace std;
12
using namespace __gnu_pbds;
13

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

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

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

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

30
int N;
31
int y[110000];
32
int l[110000], r[110000], up[110000];
33
ll sum1[110000];
34
ll sum2[110000];
35

36
int main(){
37
    N = read();
38
    for(int i = 1; i <= N; ++i){
39
        int rx = read() + 1, ry = read() + 1;
40
        y[rx] = ry;
41
    }l[0] = INT_MAX; r[N + 1] = -1;
42
    for(int i = 1; i <= N; ++i)l[i] = min(l[i - 1], y[i]);
43
    for(int i = N; i >= 1; --i)r[i] = max(r[i + 1], y[i]);
44
    int cur = r[1];
45
    for(int i = 1; i <= N; ++i)while(cur && cur >= l[i])up[cur] = i, --cur;
46
    for(int i = 1; i <= N; ++i)sum1[i] = (sum1[i - 1] + up[i]) % MOD;
47
    for(int i = 1; i <= N; ++i)sum2[i] = (sum2[i - 1] + sum1[i]) % MOD;
48
    ll ans(0);
49
    for(int i = 1; i <= N; ++i){
50
        ans = (ans + ((ll)r[i] - l[i]) * (r[i] - l[i] + 1) / 2ll % MOD * i % MOD) % MOD;
51
        ans = (ans - GetSum2(r[i] - 1) + GetSum2(l[i] - 2) + MOD) % MOD;
52
        ans = (ans + ((ll)r[i] - l[i] + 1) * GetSum1(l[i] - 1) % MOD) % MOD;
53
    }printf("%lld\n", ans);
54
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
55
    return 0;
56
}
57

58
template < typename T >
59
inline T read(void){
60
    T ret(0);
61
    short flag(1);
62
    char c = getchar();
63
    while(c != '-' && !isdigit(c))c = getchar();
64
    if(c == '-')flag = -1, c = getchar();
65
    while(isdigit(c)){
66
        ret *= 10;
67
        ret += int(c - '0');
68
        c = getchar();
69
    }
70
    ret *= flag;
71
    return ret;
72
}

LG-P4187 [USACO18JAN]Stamp Painting G

题面

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

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

Examples

Input_1

xxxxxxxxxx
1
1
3 2 2