首页 模拟赛

平衡树（线段树 / 树状数组二分），AC 自动机 + zkw 线段树，状压 dp

# A. 工作

考场上怒调 3h 平衡树 + 启发式合并，然后脑子短路了，硬是没想到正解。

事实上你只需要维护一棵平衡树，支持查询前 kk 大数的和，区间 -1，快速维护区间 -1 之后树的形态。

前两个操作就不多说了，下面来看一下第三个操作。

我们是对最大的 kk 个数进行的区间 -1，由于只减去了1，所以可以分两种情况讨论：

  • 第 kk 大的数大于第 k+1k + 1 大的数，那么 -1 之后依然满足平衡树的性质，无需进行额外操作。

  • 第 kk 大数等于第 k+1k + 1 大的数。这种情况下有可能有好多数都相同。假设第 kk 大数权值为 xx，且第 l∼kl \sim k 大的数以及第 k+1∼rk + 1 \sim r 大的数均为 xx。

    此时我们有两棵树（前 1∼k1 \sim k 和 k+1∼nk + 1 \sim n），当把 l∼kl \sim k 大的数减 1 之后，它们会小于原本排在 k+1∼rk + 1 \sim r 的数，所以我们把这两棵树拆成四棵树，即数的排名为1∼l−1,  l∼k,  k+1∼r,  r+1∼n1 \sim l - 1,\ \ l \sim k,\ \ k + 1 \sim r,\ \ r + 1 \sim n 的四棵树，设四棵树的根分别为 a,b,c,da, b, c, d。

    这时 l∼kl \sim k 已经小于 k+1∼rk + 1 \sim r 了，所以把 aa 和 cc 合并，再把 bb 和 dd 合并，最后再合并到一起即可。

然后这题就变成板子了。

但是这题比较卡常，朴素写法得跑 2s 多，考虑优化建树过程。

不难发现，插数顺序并不影响我们的树，所以直接对输入的 aia_i 排个序，然后直接 merge\text{merge} 即可，也就是对于每个数省掉了一次 split\text{split}，然后就可以卡过了。

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
#include <bits/stdc++.h>
#define ls(x) ch[x][0]
#define rs(x) ch[x][1]
#define ll long long

using namespace std;

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

    template <typename T> inline void write(T x){
        if(x < 0) putchar('-'), x = -x;
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 5e5 + 10;
int n, m, root, tot;
int v[N];
ll sum[N];
int siz[N], val[N], ch[N][2], wei[N], tag[N];

inline void pushup(int x){
    sum[x] = sum[ls(x)] + sum[rs(x)] + val[x];
    siz[x] = siz[ls(x)] + siz[rs(x)] + 1;
}

inline void pushtag(int x, int k){
    tag[x] += k, val[x] -= k, sum[x] -= 1ll * siz[x] * k;
}

inline void pushdown(int x){
    if(tag[x]){
        if(ls(x)) pushtag(ls(x), tag[x]);
        if(rs(x)) pushtag(rs(x), tag[x]);
        tag[x] = 0;
    }
}

inline void split_siz(int x, int k, int &a, int &b){
    if(!x) return a = b = 0, void();
    pushdown(x);
    if(siz[ls(x)] + 1 <= k) a = x, split_siz(rs(x), k - siz[ls(x)] - 1, rs(x), b);
    else b = x, split_siz(ls(x), k, a, ls(x));
    pushup(x);
}

inline void split_val(int x, int k, int &a, int &b){
    if(!x) return a = b = 0, void();
    pushdown(x);
    if(val[x] <= k) a = x, split_val(rs(x), k, rs(x), b);
    else b = x, split_val(ls(x), k, a, ls(x));
    pushup(x);
}

inline int merge(int x, int y){
    if(!x || !y) return x | y;
    if(wei[x] <= wei[y]){
        rs(x) = merge(rs(x), y);
        return pushup(x), x;
    }else{
        ls(y) = merge(x, ls(y));
        return pushup(y), y;
    }
}

inline int newnode(int k){
    siz[++tot] = 1, val[tot] = k, wei[tot] = rand(), sum[tot] = k;
    return tot;
}

inline void Union(int x, int y){
    int a, b, c, d;
    split_siz(y, 1, a, b);
    int tmp = val[a];
    y = merge(a, b);
    split_val(y, tmp, a, b);
    split_val(x, tmp - 1, c, d);
    root = merge(merge(c, a), merge(d, b));
}

ll ans = 0;

inline void solve(int k){
    int a = 0, b = 0;
    split_siz(root, n - k, a, b);
    ans += sum[b], tag[b]++, val[b]--, sum[b] -= siz[b];
    Union(a, b);
}

signed main(){
    // freopen("A.in", "r", stdin);
    // freopen("A.out", "w", stdout);
    n = read();
    for(int i = 1; i <= n; ++i) v[i] = read();
    sort(v + 1, v + 1 + n);
    for(int i = 1; i <= n; ++i) root = merge(root, newnode(v[i]));
    // cout << "insert" << endl;
    m = read();
    for(int i = 1; i <= m; ++i) solve(read());
    write(ans), puts("");
    return 0;
}
// X.K.

然后再简单说说 zzzzzz 神仙的思路，还是查询前 kk 大的数的和，然后区间减 1，同样是上面的讨论。假设 l∼r (l<k<r)l \sim r\ (l < k < r) 的数都相同，l∼kl \sim k 的数减 1 之后不再是前 kk 大。

这时候我们考虑不去减这些数，而是去减排名为r−(k−l)+1∼rr - (k - l) + 1 \sim r 的数。

容易证明，这样效果是一样的，而且不会破坏现有的递增的关系，可以继续进行接下来的操作。

# B. 大水题

思路过于神仙，代码也不会写，咕咕咕。

# C. 榜滚(ranklist)

是 21 年联合省选「滚榜」的不知道加强版还是弱化版，暴力全排列的话还是可以取得 45pts 的好成绩。

思路其实是差不多的，但是状态跟那道题略有不同。

设 dps,i,jdp_{s, i, j} 表示状态为 ss 的人，当前这个人比上一个人多过了 ii 道题，总共消耗了 jj 道题。

这道题由于给出了一个 luck\text{luck} 值，所以不 luck\text{luck} 的那些人题数必须严格多余之前的。

然后赋初值，转移即可，刷表法可能要好写一些。

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>
#define uint unsigned int

using namespace std;

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

    template <typename T> inline void write(T x){
        if(x < 0) putchar('-'), x = -x;
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 14;
int n, m, K, mx;
int a[N], luck[N];
int dp[1 << N][N][511];

signed main(){
    n = read(), m = read(), K = read();
    for(int i = 0; i < n; ++i) mx = max(mx, a[i] = read());
    for(int i = 1; i <= K; ++i) luck[read() - 1] = 1;
    for(int i = 0; i < n; ++i){
        int t = ((mx == a[i]) || (!luck[i]));
        int b = mx - a[i] + t;
        if(b <= m) dp[1 << i][t][b] = 1;
    }
    for(int s = 0; s < (1 << n); ++s)
        for(int i = 0; i <= n; ++i)
            for(int j = 1; j <= m; ++j)
                if(dp[s][i][j])
                    for(int k = 0; k < n; ++k)
                        if(!((s >> k) & 1)){
                            int t = i + ((mx + i == a[k]) || (!luck[k]));
                            int b = mx - a[k] + t;
                            if(j + b <= m) dp[s | (1 << k)][t][j + b] += dp[s][i][j];
                        }
    uint ans = 0;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j) ans += dp[(1 << n) - 1][i][j];
    write(ans), puts("");
    return 0;
}
// X.K.

阅读次数 次