noip2021 训练1

发表于 更新于 分类于 阅读次数： 本文字数： 7.4k 阅读时长 ≈ 15 分钟

Link

CF402E Strictly Positive Matrix

Description

给出一个矩阵 AA，问是否存在一个正整数 kk 使得 AkA^k 的所有元素都是正数。

2≤n≤2000,0≤ai,j≤50,∑i=1nai,i>02\le n \le 2000,0\le a_{i,j}\le 50,\sum_{i=1}^{n}a_{i,i}>0

Solution

将矩阵看作邻接矩阵，都是正数就相当于联通。

把不为 00 的连边，tarjantarjan 缩点，判断图是否联通。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>

using namespace std;

const int N = 2005;
int n;
vector <int> g[N];
int dfn[N], low[N], tim;
int stk[N], top, cnt;
bool vis[N];

void tarjan(int u)
{
    dfn[u] = low[u] = ++tim;
    stk[++top] = u;
    vis[u] = 1;
    for(auto v : g[u])
    {
        if(!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]);
        else if(vis[v]) low[u] = min(low[u], dfn[v]);
    }
    if(low[u] == dfn[u])
    {
        int x; cnt++;
        do
        {
            x = stk[top--];
            vis[x] = 0;
        } while (x != u);
    }
    return;
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
        {
            int a;
            scanf("%d", &a);
            if(a) g[i].push_back(j);
        }
    for(int i = 1; i <= n; i++)
        if(!dfn[i]) tarjan(i);
    printf(cnt == 1 ? "YES" : "NO");
    return 0;
}

CF427C Checkposts

Description

给定一张 nn 个点 mm 条边的有向图。

在第 ii 个点建造哨站的花费是 aia_i，每个哨站可以覆盖所有从该点出发能够到达的点。

试求出使每个点都被覆盖的最小花费及在最小花费下的方案数。

1≤n≤1051\leq n\leq 10^5，0≤m≤3×1050\leq m\leq 3\times 10^5，0≤ai≤1090\leq a_i\leq 10^9。方案数对 109+710^9+7 取模。

Solution

不难发现一个环里不论取哪个点都能覆盖整个环，因此先缩点。

对于每个强连通分量，记录下最小花费 以及 最小花费的方案数。

答案即为每个强连通分量的最小花费的和 以及 方案数的积。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int N = 1e5 + 5;
const int p = 1e9 + 7;
int n, m, cnt;
ll a[N], val[N], num[N];
vector <int> g[N];
int dfn[N], low[N], tim;
int stk[N], top;
bool vis[N];

void tarjan(int u)
{
    dfn[u] = low[u] = ++tim;
    stk[++top] = u;
    vis[u] = 1;
    for(auto v : g[u])
    {
        if(!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]);
        else if(vis[v]) low[u] = min(low[u], dfn[v]);
    }
    if(dfn[u] == low[u])
    {
        int x; cnt++;
        do {
            x = stk[top--];
            vis[x] = 0;
            if(a[x] < val[cnt]) val[cnt] = a[x], num[cnt] = 1;
            else if(a[x] == val[cnt]) num[cnt]++;
        } while(x != u);
    }
    return;
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    scanf("%d", &m);
    for(int i = 1, u, v; i <= m; i++)
    {
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
    }
    memset(val, 0x3f, sizeof(val));
    for(int i = 1; i <= n; i++)
        if(!dfn[i]) tarjan(i);
    ll ans = 0, sum = 1;
    for(int i = 1; i <= cnt; i++)
        ans += val[i], sum = sum * num[i] % p;
    printf("%lld %lld\n", ans, sum % p);
    return 0;
}

CF981D Bookshelves

Description

给定一个长度为 nn 的序列，将这个序列分为 kk 段，最大化每一段内和 的 按位与。

1≤k≤n≤50,0<ai<2501\le k \le n \le 50,0<a_i<2^{50}

Solution

二进制的一个性质：高位填 11 一定是最优的（比较显然）

因此可以从高位到低位枚举，判断是否能填 11。

对于当前枚举到的答案 ansans，怎么判断是否合法呢？

设 fi,jf_{i,j} 表示将前 ii 个数分成了 jj 段能否表示出 ansans。

因为是按位与，所以要保证每一段都要包含 ansans，然后就可以转移了。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int N = 55;
int n, m;
ll a[N], f[N][N], ans;

bool chk(ll x)
{
    memset(f, 0, sizeof(f));
    f[0][0] = 1;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            for(int k = 0; k < i; k++)
                f[i][j] |= (f[k][j - 1] & (((a[i] - a[k]) & x) == x));
    return f[n][m];
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
        scanf("%lld", &a[i]), a[i] += a[i - 1];
    for(int i = 62; i >= 0; i--)
        if(chk(ans | (1ll << i))) ans |= (1ll << i);
    printf("%lld\n", ans);
    return 0;
}

CF617E XOR and Favorite Number

Description

给定一个长度为 nn 的序列 aa，然后再给一个数字 kk，再给出 mm 组询问，每组询问给出一个区间，求这个区间里面有多少个子区间的异或值为 kk。

1≤n,m≤105,0≤k,ai≤106,1≤li≤ri≤n1\le n,m \le 10^5,0\le k,a_i \le 10^6,1\le l_i \le r_i \le n

Solution

区间异或，不难想到要算前缀异或。

考虑莫队，因为若 x⊕y=kx \oplus y = k，则 y=x⊕ky = x \oplus k

用 cnticnt_i 记一下 ii 出现过几次，然后在插入、删除时就可以直接修改答案了。

注意因为是前缀异或，所以询问的左端点要 −1-1

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int N = 1e5 + 5;
const int MAXN = 2e6 + 5;
int n, m, k, a[N], B;
struct query
{
    int l, r, id;
    friend bool operator < (query x, query y)
    {
        return x.l / B == y.l / B ? x.r < y.r : x.l / B < y.l / B;
    }
}q[N];
ll ans[N], sum, cnt[MAXN];

void add(int x)
{
    sum += cnt[x ^ k];
    cnt[x]++;
}

void del(int x)
{
    cnt[x]--;
    sum -= cnt[x ^ k];
}

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]), a[i] ^= a[i - 1];
    for(int i = 1; i <= m; i++)
        scanf("%d%d", &q[i].l, &q[i].r), q[i].l--, q[i].id = i;
    B = sqrt(n);
    sort(q + 1, q + 1 + m);
    int l = 1, r = 0;   //[l,r]
    for(int i = 1; i <= m; i++)
    {
        while(l > q[i].l) add(a[--l]);
        while(l < q[i].l) del(a[l++]);
        while(r < q[i].r) add(a[++r]);
        while(r > q[i].r) del(a[r--]);
        ans[q[i].id] = sum;
    }
    for(int i = 1; i <= m; i++)
        printf("%lld\n", ans[i]);
    return 0;
}

CF161D Distance in Tree

Description

输入点数为 NN 一棵树

求树上长度恰好为 KK 的路径个数

Solution

点分治板子题，但是这里用树形dp

fu,if_{u,i} 表示在以 uu 为根的子树中，有多少个点到 uu 的距离为 ii

gug_{u} 表示在以 uu 为根的子树中有多少条长度为 kk 的链，并且链经过 uu

答案为 ∑i=1ngi\sum_{i = 1}^n g_i

先跑一遍 dfsdfs 算出 ff，然后再跑一遍 dfsdfs，求 gg。

在算 gg 的时候，将 uu 的子树合并到前面的子树里，就枚举这个子树中链的长度 jj，然后乘以前面的子树中链的长度为 k−jk - j 的个数，求个和。

因为只有子树里的计算，所以可以用 dsu on treedsu\ on\ tree，但是我懒得写了qwq

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int N = 5e4 + 5;
int n, m;
vector <int> G[N];
ll f[N][505];

void dfs1(int u, int fa)
{
    f[u][0] = 1;
    for(auto v : G[u])
    {
        if(v == fa) continue;
        dfs1(v, u);
        for(int i = 1; i <= m; i++)
            f[u][i] += f[v][i - 1];
    }
    return;
}

ll pre[505], g[N], ans;
void dfs2(int u, int fa)
{
    memset(pre, 0, sizeof(pre));
    pre[1] = 1;
    for(auto v : G[u])
    {
        if(v == fa) continue;
        for(int i = 0; i <= m; i++)
            g[u] += pre[i] * f[v][m - i];
        for(int i = 2; i <= m; i++)
            pre[i] += f[v][i - 2];
    }
    for(auto v : G[u])
        if(v != fa) dfs2(v, u);
    return;
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1, u, v; i < n; i++)
    {
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs1(1, 0);
    dfs2(1, 0);
    for(int i = 1; i <= n; i++) ans += g[i];
    printf("%lld\n", ans);
    return 0;
}

CF464E The Classic Problem

Description

给定一张 nn个点，mm 条边的无向图，每条边的边权为 2xi2^{x_i}，求 ss 到 tt 的最短路，结果对 109+710^9+7 取模。

1≤n≤105,0≤m≤105,0≤xi≤1051\le n \le 10^5,0\le m \le 10^5,0\le x_i\le 10^5

Solution

最短路板子，边权巨大，需要开高精度，但是复杂度太大，会 TT。

考虑优化，观察到边权都是 22 的次幂，可以将长度以二进制形式存储，然后用主席树维护一下 disdis，因为需要用到历史版本。

接下来考虑需要支持什么操作：

  1. 在跑最短路时，更新最短路，第 xix_i 位 +1+1，需要单点修改。
  2. 单点 +1+1 可能会导致进位，要将一段 11 改为 00，需要区间修改。
  3. 单点 +1+1 的位置需要主席树上二分找到第一个为 00 的位置。
  4. 比较大小，也是二分找第一位不同的位置。

维护一下区间 11 的个数和转成十进制后的值。

因为主席树不支持动态修改，所以可以新建一颗全 00 的树，然后在进位时将空树贴进去就行了。

注意左子树是低位，右子树是高位，在二分时要先递归右子树，再递归左子树，比大小也是。

然后就可以愉快地跑 dijkstradijkstra 了。

一开始 disdis 的正无穷，可以建一棵全 11 的树，就已经是最大了。

一些细节：

  1. 更新最短路时不能直接在原树上改，要新建节点，因为原树在后面可能会用到。
  2. 更新最短路时需要记一下原来的节点个数，如果没有更新成功，后面的点都是没用的，可以去掉。
  3. 动态开点记得把数组开大点。
Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
#include <bits/stdc++.h>
#define ll long long

using namespace std;

template <typename T>
void read(T &x)
{
    x = 0; char c = getchar();
    while(!isdigit(c)) c = getchar();
    while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
    return;
}

template <typename T>
void write(T x)
{
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

const int N = 2e5 + 5;
const int modd = 1e9 + 7;
int n, m, s, t, inf;
ll mi[N];
int ans[N], len;
struct edge
{
    int v, w, nxt;
}e[N << 1];
int head[N], tot;

void add(int u, int v, int w)
{
    e[++tot] = (edge) {v, w, head[u]};
    head[u] = tot;
}

int rt[N], cnt;
struct Tree
{
    int ls[N << 5], rs[N << 5], num[N << 5];
    ll sum[N << 5];

    void Copy(int x, int y)
    {
        ls[x] = ls[y], rs[x] = rs[y];
        num[x] = num[y], sum[x] = sum[y];
    }

    bool equal(int x, int y)
    {
        return num[x] == num[y] && sum[x] == sum[y];
    }

    void pushup(int p)
    {
        num[p] = num[ls[p]] + num[rs[p]];
        sum[p] = (sum[ls[p]] + sum[rs[p]]) % modd;
    }

    int build(int l, int r, int val)
    {
        int p = ++cnt;
        if(l == r)
        {
            num[p] = val;
            sum[p] = mi[l] * val;
            return p;
        }
        int mid = (l + r) >> 1;
        ls[p] = build(l, mid, val);
        rs[p] = build(mid + 1, r, val);
        pushup(p);
        return p;
    }

    int update(int pre, int l, int r, int pos)
    {
        int p = ++cnt;
        Copy(p, pre);
        if(l == r)
        {
            num[p] = 1;
            sum[p] = mi[l];
            return p;
        }
        int mid = (l + r) >> 1;
        if(pos <= mid) ls[p] = update(ls[pre], l, mid, pos);
        else rs[p] = update(rs[pre], mid + 1, r, pos);
        pushup(p);
        return p;
    }

    int query(int p, int l, int r, int L, int R)
    {
        if(l > R || r < L) return 0;
        if(L <= l && r <= R) return num[p];
        int mid = (l + r) >> 1;
        return query(ls[p], l, mid, L, R) + query(rs[p], mid + 1, r, L, R);
    }

    void Clear(int &p, int x, int l, int r, int L, int R)
    {
        if(l > R || r < L) return;
        if(L <= l && r <= R)
        {
            p = x;
            return;
        }
        int mid = (l + r) >> 1, y = ++cnt;
        Copy(y, p);
        Clear(ls[y], ls[x], l, mid, L, R);
        Clear(rs[y], rs[x], mid + 1, r, L, R);
        pushup(p = y);
        return;
    }

    int Search(int p, int l, int r, int pos)
    {
        if(l == r) return l;
        int mid = (l + r) >> 1;
        if(pos > mid) return Search(rs[p], mid + 1, r, pos);
        if(query(ls[p], l, mid, pos, mid) == mid - pos + 1) return Search(rs[p], mid + 1, r, mid + 1);
        else return Search(ls[p], l, mid, pos);
    }

    bool cmp(int x, int y, int l, int r)
    {
        if(l == r) return num[x] < num[y];
        int mid = (l + r) >> 1;
        if(equal(rs[x], rs[y])) return cmp(ls[x], ls[y], l, mid);
        else return cmp(rs[x], rs[y], mid + 1, r);
    }
}T;

struct Que
{
    int id, rt;

    Que() {}

    Que(int _id, int _rt)
    {
        id = _id, rt = _rt;
    }

    friend bool operator < (Que x, Que y)
    {
        return T.cmp(y.rt, x.rt, 0, N - 1);
    }
};

priority_queue <Que> que;
bool vis[N];
int pre[N];

void dijkstra()
{
    for(int i = 1; i <= n; i++)
        rt[i] = inf;
    rt[s] = rt[0];
    que.push(Que(s, rt[s]));
    while(!que.empty())
    {
        int x = que.top().id;
        que.pop();
        if(vis[x]) continue;
        vis[x] = 1;
        for(int i = head[x]; i; i = e[i].nxt)
        {
            int y = e[i].v, lst = cnt;
            int pos = T.Search(rt[x], 0, N - 1, e[i].w);
            int rty = T.update(rt[x], 0, N - 1, pos);
            if(pos > e[i].w) T.Clear(rty, rt[0], 0, N - 1, e[i].w, pos - 1);
            if(T.cmp(rty, rt[y], 0, N - 1)) pre[y] = x, que.push(Que(y, rt[y] = rty));
            else cnt = lst;
        }
    }
}

int main()
{
    read(n), read(m);
    for(int i = 1, u, v, w; i <= m; i++)
    {
        read(u), read(v), read(w);
        add(u, v, w), add(v, u, w);
    }
    read(s), read(t);

    mi[0] = 1;
    for(int i = 1; i < N; i++)
        mi[i] = mi[i - 1] * 2 % modd;
    
    rt[0] = T.build(0, N - 1, 0);
    inf = T.build(0, N - 1, 1);
    
    dijkstra();
    
    if(T.equal(rt[t], inf))
    {
        printf("-1\n");
        return 0;
    }

    for(int i = t; i != s; i = pre[i])
        ans[++len] = i;
    ans[++len] = s;
    write(T.sum[rt[t]]), putchar('\n');
    write(len), putchar('\n');
    for(int i = len; i >= 1; i--)
        write(ans[i]), putchar(' ');
    return 0;
}

CF980E The Number Games

Description

在一颗 nn 个点的树中删 kk 个点，使得剩下的点联通并且权值和最大。

第 ii 个点的权值为 2i2^i。

1≤k<n≤1061 \le k < n \leq 10^6

Solution

一开始想的是经典错误思路：在叶子节点中从小到大删。

考虑一条链

1
2-4-1-3

显然应该删 3,13,1 而不是 2,32,3

正解：

从大到小保留，因为如果最大的点能选，后面的点加起来都不会大于这个点的权值。

以 nn 为根建树，从大到小枚举，判断能不能保留从 ii 到根还未保留的点。

怎么维护呢？

可以用树剖，一开始都是 11，如果确定保留了，就改为 00，从 ii 到根还未保留的点就是链上的和。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;
int n, k;
vector <int> g[N];

int f[N], dep[N], siz[N], son[N];

void dfs1(int u, int fa)
{
    f[u] = fa;
    dep[u] = dep[fa] + 1;
    siz[u] = 1;
    for(auto v : g[u])
    {
        if(v == fa) continue;
        dfs1(v, u);
        siz[u] += siz[v];
        if(siz[v] > siz[son[u]]) son[u] = v;
    }
    return;
}

int top[N], id[N], cnt;

void dfs2(int u, int tp)
{
    top[u] = tp;
    id[u] = ++cnt;
    if(son[u]) dfs2(son[u], tp);
    for(auto v : g[u])
    {
        if(v == f[u] || v == son[u]) continue;
        dfs2(v, v);
    }
    return;
}

#define ls (rt << 1)
#define rs (rt << 1 | 1)
#define swap(a, b) a ^= b ^= a ^= b

int sum[N << 2], tag[N << 2];

void pushup(int rt)
{
    sum[rt] = sum[ls] + sum[rs];
}

void build(int l, int r, int rt)
{
    tag[rt] = -1;
    if(l == r)
    {
        sum[rt] = 1;
        return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, ls);
    build(mid + 1, r, rs);
    pushup(rt);
    return;
}

void pushdown(int rt)
{
    if(tag[rt] != -1)
    {
        sum[ls] = tag[ls] = tag[rt];
        sum[rs] = tag[rs] = tag[rt];
        tag[rt] = -1;
    }
}

void upd(int L, int R, int l, int r, int rt)
{
    if(l > R || r < L) return;
    if(L <= l && r <= R)
    {
        sum[rt] = tag[rt] = 0;
        return;
    }
    pushdown(rt);
    int mid = (l + r) >> 1;
    upd(L, R, l, mid, ls);
    upd(L, R, mid + 1, r, rs);
    pushup(rt);
    return;
}

int qry(int L, int R, int l, int r, int rt)
{
    if(l > R || r < L) return 0;
    if(L <= l && r <= R) return sum[rt];
    pushdown(rt);
    int mid = (l + r) >> 1;
    return qry(L, R, l, mid, ls) + qry(L, R, mid + 1, r, rs);
}

void update(int x, int y)
{
    while(top[x] != top[y])
    {
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        upd(id[top[x]], id[x], 1, n, 1);
        x = f[top[x]];
    }
    if(dep[x] > dep[y]) swap(x, y);
    upd(id[x], id[y], 1, n, 1);
    return;
}

int query(int x, int y)
{
    int res = 0;
    while(top[x] != top[y])
    {
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        res += qry(id[top[x]], id[x], 1, n, 1);
        x = f[top[x]];
    }
    if(dep[x] > dep[y]) swap(x, y);
    res += qry(id[x], id[y], 1, n, 1);
    return res;
}

int main()
{
    scanf("%d%d", &n, &k);
    for(int i = 1, u, v; i < n; i++)
    {
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs1(n, 0), dfs2(n, n);
    build(1, n, 1);
    k = n - k;
    for(int i = n; i >= 1; i--)
    {
        int tot = query(n, i);
        if(k < tot) continue;
        update(n, i);
        k -= tot;
    }
    for(int i = 1; i <= n; i++)
        if(qry(id[i], id[i], 1, n, 1))
            printf("%d ", i);
    return 0;
}

CF1101F Trucks and Cities

Description

有 nn 个城市坐落在一条数轴上，第 ii 个城市位于位置 aia_i。

城市之间有 mm 辆卡车穿行．每辆卡车有四个参数：sis_i 为起点编号，fif_i 为终点编号，cic_i 表示每行驶 11 个单位长度需要消耗的油量，rir_i 表示可以在路途中加油的次数。

当卡车到达一个城市的时候可以将油加满（当然也可以不加），在路中无法加油，但是路途中总加油次数不能超过 rir_i。

所有卡车的油箱都是一样大的，我们称它的容积为 VV。试求一个最小的 VV，使得对于所有的卡车都存在一种方案，在路途中任意时刻油箱内的油量大于等于 00 且路途中总加油次数小于等于 rir_i 的情况下从起点城市到达终点城市。

Solution

一个比较暴力的做法，对于每辆卡车，算出油箱的最小容积，然后取个 maxmax。

在算每辆卡车时可以二分答案。

但是这样是过不去的，考虑优化

  1. 因为答案是每辆车的最大值，所以在计算每辆车时，可以先用当前的 ansans 判断一下，如果可以就不用再算了。

  2. 在判断每辆车二分出来的容积是否合法时，也可以二分贪心地往后跳。

复杂度大概是一个 mm 带两个 log⁡\log。

根据第一条优化，可以 random_shufflerandom\_shuffle 一下，这样效果更佳（雾

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int N = 405;
const int M = 3e5 + 5;
int n, m;
int a[N], mx[N][N];
ll ans;
struct truck
{
    int s, t, c, p;
}car[M];

bool chk(int s, int t, int c, int p, ll x)
{
    if((ll)mx[s][t] * c > x) return false;
    int pos = s, cnt = 0;
    while(pos < t && cnt <= p)
    {
        if((ll)(a[t] - a[pos]) * c <= x) return true;
        int l = pos, r = t, nxt = pos;
        while(l <= r)
        {
            int mid = (l + r) >> 1;
            if((ll)(a[mid] - a[pos]) * c <= x) l = mid + 1, nxt = mid;
            else r = mid - 1;
        }
        cnt++;
        pos = nxt;
    }
    return cnt <= p;
}

template <typename T>
void read(T &x)
{
    x = 0; char c = getchar();
    while(!isdigit(c)) c = getchar();
    while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
    return;
}

int main()
{
    srand(19260817);

    read(n), read(m);
    for(int i = 1; i <= n; i++) read(a[i]);
    for(int i = 1; i <= m; i++)
        read(car[i].s), read(car[i].t), read(car[i].c), read(car[i].p);

    for(int i = 1; i <= n; i++)
        for(int j = i + 1; j <= n; j++)
            mx[i][j] = max(mx[i][j - 1], a[j] - a[j - 1]);
    
    random_shuffle(car + 1, car + 1 + m);

    for(int i = 1; i <= m; i++)
    {
        if(chk(car[i].s, car[i].t, car[i].c, car[i].p, ans)) continue;
        ll l = max((ll)mx[car[i].s][car[i].t] * car[i].c, ans + 1), r = (ll)(a[car[i].t] - a[car[i].s]) * car[i].c;
        ll mn = r;
        while(l <= r)
        {
            ll mid = (l + r) >> 1;
            if(chk(car[i].s, car[i].t, car[i].c, car[i].p, mid)) r = mid - 1, mn = mid;
            else l = mid + 1;
        }
        ans = max(ans, mn);
    }

    printf("%lld\n", ans);
    return 0;
}

CF340D Bubble Sort Graph

Description

题目可以理解为给出一个长度为 nn 的序列，每个逆序对连一条无向边，求得到的无向图（可能不连通）的最大独立集。

2≤n≤105,1≤ai≤n2\le n \le 10^5,1\le a_i \le n

Solution

经过思考，题意可以转化为求最长上升子序列。

然后就是一个板子了，这里用的树状数组。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;
int n, ans;
int c[N];

void add(int x, int y)
{
    for(; x <= n; x += x & -x)
        c[x] = max(c[x], y);
}

int qry(int x)
{
    int res = 0;
    for(; x; x -= x & -x)
        res = max(res, c[x]);
    return res;
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {
        int a;
        scanf("%d", &a);
        int len = qry(a) + 1;
        add(a, len);
        ans = max(ans, len);
    }
    printf("%d\n", ans);
    return 0;
}

CF274E Mirror Room

Description

有一个 n∗mn*m 的格子图，其中有一些是黑色的，另一些为白色。

从某个白色格子的中心点向左上（NW），左下（SW），右上（NE），右下（SE）四个方向中的一个发出一束光线，若光线碰到黑色格子或者墙壁（即边界）会反射。反射情况如图所示：

我们不难发现，光线能穿过的格子总数是可以算出的。假如光线经过了某个格子的中心，则称光线经过了这个格子。求光线经过的格子总数。

1≤n,m≤105,0≤k≤1051\le n,m \le 10 ^ 5,0\le k \le 10^5

Solution

大模拟。

模拟光线的移动，对于每条对角线线，用 setset 记录下障碍物的位置，然后就可以直接二分找到走到哪反射。

二分时，如果是向左上或右上，要取前一个格子，因为 lowerbound()lower_bound() 会找到下一个。

在反射时要注意，我们二分找到的是这条对角线上的下一个格，还需要根据题中给出的三种情况进行分类讨论。可以用 mapmap 记录每个格子为黑色或白色，然后判一下相邻的两个格子。

如果是原路返回，就原路返回去，最后答案除以二即可。

有一个小技巧，先从起点找到下一个障碍物，然后以这个障碍物为起点进行模拟，这样当再次回到这个障碍物时就已经走了一圈了。

这里用了很多异或来简化代码，就不细说了，可以手动模拟一下（

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
#define ll long long

using namespace std;

typedef pair<int, int> P;
const int N = 1e5 + 5;
int n, m, k;
map <int, int> mp[N << 1];
set <P> s[2][N << 1];
int x, y, d;
string str;
int dx[] = {1, 1, -1, -1};
int dy[] = {1, -1, -1, 1};
ll ans;
int flag = 1;

int getid(int op, int x, int y)
{
    return !op ? x - y + m + 1 : x + y;
}

void ins(int x, int y)
{
    s[0][getid(0, x, y)].insert(P(x, y));
    s[1][getid(1, x, y)].insert(P(x, y));
    mp[x][y] = 1;
}

void work()
{
    auto it = s[d & 1][getid(d & 1, x, y)].lower_bound(P(x, y));
    if(d < 2) it--; //左上右上
    int sx = (*it).first, sy = (*it).second;
    ans += abs(x - sx);
    x = sx + dx[d];
    y = sy + dy[d];
    bool f1 = mp[sx].count(y), f2 = mp[x].count(sy);
    if(!(f1 ^ f2)) flag = 2, d = (d + 2) % 4;
    else if(f1) y = sy, d ^= 3;
    else x = sx, d ^= 1;
    return;
}

int main()
{
    ios :: sync_with_stdio(false);
    cin >> n >> m >> k;
    for(int i = 1, x, y; i <= k; i++)
    {
        cin >> x >> y;
        ins(x, y);
    }
    cin >> x >> y >> str;
    for(int i = 0; i <= n + 1; i++) ins(i, 0), ins(i, m + 1);
    for(int i = 0; i <= m + 1; i++) ins(0, i), ins(n + 1, i);
    if(str == "NW") d = 0;  //左上
    if(str == "NE") d = 1;  //右上
    if(str == "SE") d = 2;  //右下
    if(str == "SW") d = 3;  //左下
    work();
    int tx = x, ty = y, td = d;
    ans = 0, work();
    while(x != tx || y != ty || d != td) work();
    printf("%lld\n", ans / flag);
    return 0;
}

USACO11JAN Roads and Planes G

Description

给定 nn 个点，rr 条道路，pp 条航线，起点 ss。

道路是双向的，边权为正数。

航线是单向的，边权可能为负数，并且对于航线 aia_i 到 bib_i 保证不存在路径从 bib_i 到 aia_i。

求 ss 到其他每个点的最短路。

1≤n≤25000,1≤r≤50000,1≤p≤500001\le n \le 25000,1\le r \le 50000,1\le p \le 50000

Solution

直接 spfa+SLF优化spfa+SLF优化 跑过去。

用双端队列 dequedeque ，在入队的时候与队头比较一下，如果 disdis 小于队头，则入到队头，否则入队尾。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define INF 0x3f3f3f3f

using namespace std;

const int N=100010;
const int M=150010;

int n,m,k,s;
struct edge
{
	int v,w,nxt;
}e[M];
int head[N],tot;

void add(int u,int v,int w)
{
	e[++tot]=(edge){v,w,head[u]};
	head[u]=tot;
}

deque<int>que;
int dis[N],vis[N];

void spfa(int s)
{
	memset(dis,0x3f,sizeof(dis));
	dis[s]=0;
	que.push_back(s);
	vis[s]=1;
	while(!que.empty())
	{
		int u=que.front();
		que.pop_front();
		vis[u]=0;
		for(int i=head[u];i;i=e[i].nxt)
		{
			int v=e[i].v,w=e[i].w;
			if(dis[u]+w<dis[v])
			{
				dis[v]=dis[u]+w;
				if(!vis[v])
				{
					if(!que.empty()&&dis[v]>=dis[que.front()]) que.push_back(v);
					else que.push_front(v);
					vis[v]=1;
				}
			}
		}
	}
}

int main()
{
	scanf("%d%d%d%d",&n,&m,&k,&s);
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
		add(v,u,w);
	}
	for(int i=1;i<=k;i++)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
	}
	spfa(s);
	for(int i=1;i<=n;i++)
		if(dis[i]==INF) puts("NO PATH");
		else printf("%d\n",dis[i]);
	return 0;
}

USACO15JAN Grass Cownoisseur G

Description

给定一个 nn 个点 mm 条边的有向图，从 11 号点出发，最后走回 11 号点，最多能经过几个点。

在行走过程中可以逆向走一条边。

1≤n,m≤1051\le n,m \le 10^5

Solution

在一个点，该点强连通分量内的点肯定都走一遍，容易想到 tarjantarjan 缩点，然后得到一个 DAGDAG。

因为可以逆行一次，所以要正着处理一遍，求出从 11 到每个点最多能经过几个点，然后再建反图跑一遍，相当于求出了每个点到 11 最多能经过几个点。

这里不能简单的拓扑排序，而是要跑一遍最长路。

最后枚举每个点，将两次算出来的个数加起来取 maxmax，但是这里还要减去 11 号点所在强连通分量的点的个数，因为会算重。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;
int n, m;
vector <int> g[N];
vector <int> G[N];
int dfn[N], low[N], tim;
int stk[N], top, cnt, num[N], id[N];
bool vis[N];

void tarjan(int u)
{
    dfn[u] = low[u] = ++tim;
    stk[++top] = u;
    vis[u] = 1;
    for(auto v : g[u])
    {
        if(!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]);
        else if(vis[v]) low[u] = min(low[u], dfn[v]);
    }
    if(low[u] == dfn[u])
    {
        int x; cnt++;
        do
        {
            x = stk[top--];
            vis[x] = 0;
            num[cnt]++;
            id[x] = cnt;
        } while (x != u);
    }
    return;
}

int dis1[N], dis2[N];
queue <int> que;
bool inq[N];
void spfa(int dis[])
{
    que.push(id[1]);
    dis[id[1]] = num[id[1]];
    inq[id[1]] = 1;
    while(!que.empty())
    {
        int u = que.front();
        que.pop();
        inq[u] = 0;
        for(auto v : G[u])
        {
            if(dis[v] < dis[u] + num[v])
            {
                dis[v] = dis[u] + num[v];
                if(!inq[v]) que.push(v), inq[v] = 1;
            }
        }
    }
    return;
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1, u, v; i <= m; i++)
    {
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
    }

    for(int i = 1; i <= n; i++)
        if(!dfn[i]) tarjan(i);

    for(int i = 1; i <= n; i++)
        for(auto j : g[i]) if(id[i] != id[j])
                G[id[i]].push_back(id[j]);
    spfa(dis1);

    for(int i = 1; i <= cnt; i++) G[i].clear();
    memset(inq, 0, sizeof(inq));
    
    for(int i = 1; i <= n; i++)
        for(auto j : g[i]) if(id[i] != id[j])
            G[id[j]].push_back(id[i]);
    spfa(dis2);

    int ans = num[id[1]];
    for(int i = 1; i <= cnt; i++)
        for(auto j : G[i])
            if(dis1[i] > 0 && dis2[j] > 0)
                ans = max(ans, dis1[i] + dis2[j] - num[id[1]]);
    printf("%d\n", ans);
    return 0;
}

USACO18OPEN Talent Show G

Description

给定 nn 头奶牛，每头奶牛有一个重量 wiw_i 和才艺 viv_i，请选出若干头奶牛，使得总重量 ≥m\ge m，并最大化 ∑vi∑wi\dfrac{\sum v_i}{\sum w_i}。

输出 ∑vi∑wi\dfrac{\sum v_i}{\sum w_i} 的最大值。

1≤n≤250,1≤m≤103,1≤wi≤106,1≤vi≤1031\le n \le 250,1\le m \le 10^3,1\le w_i \le 10^6,1 \le v_i \le 10^3

Solution

有点类似于 Luogu P3874 [TJOI2010]砍树

因为求的是 ∑vi∑wi\dfrac{\sum v_i}{\sum w_i} ，并不能简单地通过前面的最大值推到后面的最大值。

对于这种题，比较套路的思想，进行01分数规划。

首先二分答案 xx，若存在 ∑vi∑wi≥x\dfrac{\sum v_i}{\sum w_i}\ge x，说明答案可以更大。

将上面的式子转化一下

∑vi≥∑wi×x\sum v_i \ge \sum w_i \times x

∑(vi−wi×x)≥0\sum(v_i-w_i\times x) \ge 0

这样，每头奶牛的贡献就变成了 vi−wi×xv_i-w_i\times x。

然后要保证 ∑wi≥m\sum w_i \ge m，还需要01背包，可以将 ≥m\ge m 的部分全都放到 fmf_m 上，最后判一下 fmf_m 是否 ≥0\ge 0 即可。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int N = 255;
const int MAXN = 1010;
int n, m;
int w[N], v[N];
ll f[MAXN];

bool chk(int x)
{
    memset(f, 128, sizeof(f));
    f[0] = 0;
    for(int i = 1; i <= n; i++)
        for(int j = m; j >= 0; j--)
        {
            int k = min(m, j + w[i]);
            f[k] = max(f[k], f[j] + v[i] - 1ll * w[i] * x);
        }
    return f[m] >= 0;
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d%d", &w[i], &v[i]);
        v[i] *= 1000;
    }
    
    int l = 0, r = 1e9, ans;
    while(l <= r)
    {
        int mid = (l + r) >> 1;
        if(chk(mid)) l = mid + 1, ans = mid;
        else r = mid - 1;
    }
    printf("%d\n", ans);
    return 0;
}

USACO18OPEN Out of Sorts S

Description

对长度为 nn 的数组进行冒泡排序

过程如下

1
2
3
4
5
6
7
8
sorted = false
while (not sorted):
   sorted = true
   moo
   for i = 0 to N-2:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
         sorted = false

其中 moo 的作用是输出 moo，求出代码会输出多少次 moo。

1≤n≤105,0≤ai≤1091\le n \le 10^5,0\le a_i \le 10^9 保证 aia_i 各不相同

Solution

每进行一次冒泡排序，对于第 ii 个数，会把前面一个大于 aia_i 的数排到 ii 后面。

因此只需要算一下每个数前面有多少个比它大的，取个 maxmax，最后要 +1+1，但并不进行排序。

离散化一下，用树状数组维护即可。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;
int n, a[N], b[N], c[N], ans;

void add(int x, int y)
{
    for(; x <= n; x += x & -x)
        c[x] += y;
}

int qry(int x)
{
    int res = 0;
    for(; x; x -= x & -x)
        res += c[x];
    return res;
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]), b[i] = a[i];
    sort(b + 1, b + 1 + n);
    for(int i = 1; i <= n; i++)
        a[i] = lower_bound(b + 1, b + 1 + n, a[i]) - b;
    for(int i = 1; i <= n; i++)
    {
        add(a[i], 1);
        ans = max(ans, i - qry(a[i]));
    }
    printf("%d\n", ans + 1);
    return 0;
}

USACO18OPEN Out of Sorts G

Description

对长度为 nn 的数组进行冒泡排序

过程如下

1
2
3
4
5
6
7
8
9
10
11
12
13
sorted = false
while (not sorted):
   sorted = true
   moo
   for i = 0 to N-2:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
   for i = N-2 downto 0:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
   for i = 0 to N-2:
      if A[i+1] < A[i]:
         sorted = false

其中 moo 的作用是输出 moo，求出代码会输出多少次 moo。

1≤n≤105,0≤ai≤1091\le n \le 10^5,0\le a_i \le 10^9 保证 aia_i 各不相同

Solution

对于每个位置 ii，将 ii 排到对应的位置需要的步数是 ii 前面比 ii 大的数的个数。

因为每次冒泡都会把一个大于 ii 的数放到后面，把一个小于 ii 的数放到前面。

最后取 maxmax。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;
struct node
{
    int val, id;
    friend bool operator < (node x, node y)
    {
        return x.val == y.val ? x.id < y.id : x.val < y.val;
    }
}p[N];
int n, a[N], b[N];
int c[N];

void add(int x, int y)
{
    for(; x <= n; x += x & -x)
        c[x] += y;
}

int qry(int x)
{
    int res = 0;
    for(; x; x -= x & -x)
        res += c[x];
    return res;
}

bool cmp(node x, node y)
{
    return x.id < y.id;
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d", &p[i].val), p[i].id = i;
    sort(p + 1, p + 1 + n);
    for(int i = 1; i <= n; i++)
        p[i].val = i;
    sort(p + 1, p + 1 + n, cmp);
    int ans = 1;
    for(int i = 1; i <= n; i++)
    {
        add(p[i].val, 1);
        ans = max(ans, i - qry(p[i].id));
    }
    printf("%d\n", ans);
    return 0;
}

USACO17JAN Promotion Counting P

Description

给定一颗 nn 个点的树，每个点有一个权值 pp，对于每个点 ii，求它的子树中有多少个点 jj，满足 pi>pjp_i>p_j。

1≤n≤105,1≤pi≤1091\le n \le 10^5,1\le p_i \le 10^9

Solution

把权值离散化一下，然后用权值树状数组维护子树信息，每个点的答案即为一个前缀和。

子树内可以递归，考虑如何处理并列的子树，肯定不能每次清空或新建树状数组。

对于子树 ii，ansi=ans_i= 加了 ii 的子树后大于 pip_i 的 减去 原来就大于 pip_i 的。

这样就可以适用于每个子树了。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;
int n, a[N], b[N], fa[N], tot;
vector <int> g[N];
struct BIT
{
    int c[N];
    BIT()
    {
        memset(c, 0, sizeof(c));
    }
    void add(int x, int y)
    {
        for(; x <= tot; x += x & -x)
            c[x] += y;
    }
    int qry(int x)
    {
        int res = 0;
        for(; x; x -= x & -x)
            res += c[x];
        return res;
    }
}t;
int ans[N];

void dfs(int u)
{
    ans[u] = -(t.qry(tot) - t.qry(a[u]));
    for(auto v : g[u]) dfs(v);
    ans[u] += t.qry(tot) - t.qry(a[u]);
    t.add(a[u], 1);
    return;
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]), b[i] = a[i];
    for(int i = 2; i <= n; i++)
    {
        scanf("%d", &fa[i]);
        g[fa[i]].push_back(i);
    }
    sort(b + 1, b + 1 + n);
    tot = unique(b + 1, b + 1 + n) - b - 1;
    for(int i = 1; i <= n; i++)
        a[i] = lower_bound(b + 1, b + 1 + n, a[i]) - b;
    dfs(1);
    for(int i = 1; i <= n; i++)
        printf("%d\n", ans[i]);
    return 0;
}

USACO11NOV Above the Median G

Description

给出 nn 个数字 hih_i，问中位数大于等于 xx 的连续子串有几个。（这里如果有偶数个数，定义为偏大的那一个而非中间取平均）。

1≤n≤105,1≤hi≤109,1≤x≤1091\le n \le 10^5,1\le h_i \le 10^9,1\le x\le 10^9

Solution

对于中位数比较套路的思路，将 ≥x\ge x 的数改为 11，将 <x<x 的数改为 −1-1，这样如果一个区间的 ≥0\ge 0 说明这个区间的中位数 ≥x\ge x。

然后就可以用树状数组维护前缀和了，对于 ii 的前缀和 sumsum，我们要求出以 ii 为右端点的区间中位数 ≥x\ge x 的个数，需要要求出前 ii 个前缀和中 ≤x\le x 的个数，也就是顺序对的个数。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int N = 1e5 + 5;
int n, m;
int c[N << 1];

void add(int x, int y)
{
    for(; x <= n + n + 1; x += x & -x)
        c[x] += y;
}

int qry(int x)
{
    int res = 0;
    for(; x; x -= x & -x)
        res += c[x];
    return res;
}

int main()
{
    scanf("%d%d", &n, &m);
    int sum = 0;
    ll ans = 0;
    add(n + 1, 1);
    for(int i = 1; i <= n; i++)
    {
        int a;
        scanf("%d", &a);
        sum += a >= m ? 1 : -1;
        ans += qry(n + 1 + sum);
        add(sum + n + 1, 1);
    }
    printf("%lld\n", ans);
    return 0;
}

USACO18FEB Snow Boots G

Description

给定 nn 块地砖和 mm 双靴子，每块地砖的雪的深度 fif_i，每双靴子可以走的最大积雪深度 sis_i 和最大步长 did_i。

求哪些靴子可以从 11 走到 nn。

1≤n,m≤105,1≤fi≤109(f1=fn=0),1≤si≤109,1≤di≤n−11\le n,m\le 10^5,1\le f_i\le 10^9(f_1=f_n=0),1\le s_i \le 10^9,1\le d_i\le n-1

Solution

考虑什么情况下，第 ii 双靴子不合法，因为步长为 did_i 所以只有在存在一段连续 >di>d_i 个地砖并且积雪深度都 >si>s_i 的时候不合法。

将第 ii 双靴子能走的设为 00，不能走的设为 11，这样只需要维护区间最长的连续的 11。

可以用线段树维护，一开始全为 11。

将地砖和靴子放在一起按升序排序，这样可以保证后面的一定大于前面的，然后依次枚举

  • 如果是地砖，就单点修改，把 11 改为 00。
  • 如果是靴子，就查询最长的连续 11 的个数。
Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;
int n, m;
struct node
{
    int dep, s, id;
    friend bool operator < (node x, node y)
    {
        return x.dep == y.dep ? x.id < y.id : x.dep < y.dep;
    }
}a[N << 1];
int ans[N];

#define ls (rt << 1)
#define rs (rt << 1 | 1)
struct segtree
{
    int l, r, mx, lmx, rmx;
}t[N << 2];

void pushup(int rt)
{
    t[rt].lmx = t[ls].lmx;
    t[rt].rmx = t[rs].rmx;

    if(t[ls].mx == t[ls].r - t[ls].l + 1) t[rt].lmx += t[rs].lmx;
    if(t[rs].mx == t[rs].r - t[rs].l + 1) t[rt].rmx += t[ls].rmx;
    
    t[rt].mx = max(t[ls].mx, t[rs].mx);
    t[rt].mx = max(max(t[rt].mx, t[ls].rmx + t[rs].lmx), max(t[rt].lmx, t[rt].rmx));
}

void build(int l, int r, int rt)
{
    t[rt].l = l, t[rt].r = r;
    if(l == r)
    {
        t[rt].mx = t[rt].lmx = t[rt].rmx = 1;
        return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, ls);
    build(mid + 1, r, rs);
    pushup(rt);
}

void upd(int pos, int rt)
{
    if(t[rt].l == t[rt].r)
    {
        t[rt].mx = t[rt].lmx = t[rt].rmx = 0;
        return;
    }
    int mid = (t[rt].l + t[rt].r) >> 1;
    if(pos <= mid) upd(pos, ls);
    else upd(pos, rs);
    pushup(rt);
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i].dep);
        a[i].id = i;
    }
    for(int i = n + 1; i <= n + m; i++)
    {
        scanf("%d%d", &a[i].dep, &a[i].s);
        a[i].id = i;
    }
    sort(a + 1, a + 1 + n + m);
    build(1, n, 1);
    for(int i = 1; i <= n + m; i++)
    {
        if(a[i].id <= n) upd(a[i].id, 1);
        else ans[a[i].id - n] = t[1].mx < a[i].s;
    }
    for(int i = 1; i <= m; i++)
        printf("%d\n", ans[i]);
    return 0;
}