跳转至

NOIOL2022 题解

题面

一年前的这个时候打过这一场，但是我甚至只打了 T1 的最低档暴力分 /xk

然后那个时候也都从来没有改题，态度上都是很敷衍的，也都不怎么用心想。

这次稍微好点了，起码我会 T1 了。

T1ψ(｀∇´)ψ

这个问题还是比较套路。

显然的我们先做一遍全局的观察一下，然后考虑转化为区间。

实在是套路的不能再套路了。

好然后我们发现，假设钦定一个位置为 \(l\)，\(l\) 显然是成功的，然后原本就是成功的元组相对顺序不会改变。

所以我们考虑一下本来不是成功，但是以 \(l\) 开头却是成功应该是什么情况，从不知道哪个样例看就是类似 \(l = 5\)，然后你在 \(6\) 的时候，把 \(5\) 弹掉了，但是全局的情况下还有一个 \(4\) 在底下顶着。

观察手模可以发现，如果 \(l = 5\)，记录 \(i\) 入栈的时候，栈顶为 \(lst(i)\)，那么在 \(4\) 之后如果出现 \(4, 4, 4\) 这样的连续段，显然就是一个一个一个成功的元组。

问题转化为考虑对于 \(lst\)，在给定区间内求有多少个 \(lst < l\)，主席树一下即可，\(\log(n)\)。

也可以差分之后转化成二维数点使用 Fenwick。

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
// author : black_trees

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define endl '\n'

using namespace std;
using i64 = long long;

const int si = 5e5 + 10;

int root[si];
int n, q, a[si], b[si];
class president_tree {
    private:
        struct node {
            int ls, rs;
            int val;
        } t[si * 40];
        int cnt = 0;
        int Node() {
            ++cnt; t[cnt].ls = t[cnt].rs = 0;
            t[cnt].val = 0; return cnt;
        }
        inline void pushup(int p) {
            t[p].val = t[t[p].ls].val + t[t[p].rs].val;
        }
    public: 
        int build(int l, int r) {
            int p = Node();
            if(l == r) return p;
            int mid = (l + r) >> 1;
            t[p].ls = build(l, mid), t[p].rs = build(mid + 1, r);
            pushup(p); return p;
        }
        int insert(int lst, int l, int r, int x) {
            int p = Node();
            if(l == r) { t[p].val = 1; return p; }
            int mid = (l + r) >> 1;
            if(x <= mid) t[p].rs = t[lst].rs, t[p].ls = insert(t[lst].ls, l, mid, x);
            else t[p].ls = t[lst].ls, t[p].rs = insert(t[lst].rs, mid + 1, r, x);
            pushup(p); return p;
        }
        int query(int p, int l, int r, int L, int R) {
            if(L <= l && r <= R) return t[p].val;
            int ret = 0, mid = (l + r) >> 1;
            if(L <= mid) ret += query(t[p].ls, l, mid, L, R);
            if(R > mid)  ret += query(t[p].rs, mid + 1, r, L, R);
            return ret;
        }
} tr;

struct obj {
    int l, i;
    bool operator < (const obj &b) {
        return l < b.l;
    }
} w[si];

int L[si], stk[si];

int main() {

    // freopen("ex_stack1.in", "r", stdin);
    // freopen("ex_stack1.out", "w", stdout);

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    cin >> n >> q;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    for(int i = 1; i <= n; ++i) cin >> b[i];

    int cnt = 0;
    for(int i = 1; i <= n; ++i) {
        while(cnt && (a[stk[cnt]] == a[i] || b[stk[cnt]] <= b[i])) 
            --cnt;
        L[i] = stk[cnt] + 1;
        stk[++cnt] = i;
    }
    for(int i = 1; i <= n; ++i) w[i].i = i,w[i].l = L[i];
    sort(w + 1, w + 1 + n), root[0] = tr.build(1, n);

    int pp = 1;
    for(int i = 1; i <= n; ++i) {
        root[i] = root[i - 1];
        while(pp <= n && w[pp].l == i) 
            root[i] = tr.insert(root[i], 1, n, w[pp].i), ++pp;
    }

    for(int nw = 1; nw <= q; ++nw) {
        int l, r; cin >> l >> r;
        cout << tr.query(root[l], 1, n, l, r) << endl;
    }

    return 0;
}

考场思考的时候问题出在，我一直在考虑上一个 good，然后中间这一段可以怎么搞没想清楚。

还是最后发现了这个连续段才想到的，其实也是，考场思路不清晰，感觉不太能抽象出问题具体在哪里？这个该咋解决啊。

T2ψ(｀∇´)ψ

就，不妨按照从大到小排序。

为什么呢，因为我们想做的是事情是比较方便的处理交集，并且保证没有包含关系。

显然对于一个集合，最优的一定是满足条件里面最小的集合。

于是我们扫一遍每个集合，然后对于每个位置，我们动态记录当前覆盖了这个条件的最小的集合是啥。

这个因为从大到小了所以直接顺序枚举即可，然后 argue 一下可不可行就行。

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
// author : black_trees

#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>

#define endl '\n'
#define int long long

using namespace std;
using i64 = long long;

const int si = 2e6 + 10;

struct obj {
    int siz, id;
    std::vector<int> v;
    void init() { siz = id = 0, v.clear(); }
    bool operator < (const obj &b) const {
        return siz > b.siz;
    }
}p[si];

int n;
int bel[si], rec[si];

signed main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    int T; cin >> T;
    while(T--) {
        cin >> n;
        for(int i = 1; i <= n; ++i) {
            p[i].init(), bel[i] = 0, p[i].id = i;
            cin >> p[i].siz;
            for(int j = 0, x; j < p[i].siz; ++j)
                cin >> x, p[i].v.emplace_back(x);
        }
        sort(p + 1, p + 1 + n);
        int u, v;
        int col = 0;
        for(int i = 1; i <= n; ++i) {
            u = v = 0;
            col = p[i].id, rec[p[i].id] = i;
            for(int j = 0; j < p[i].siz; ++j) {
                int t = p[i].v[j];
                int tmp = bel[t]; bel[t] = col;
                if(!tmp) tmp = col;
                if(!u) u = tmp;
                else if(u != tmp) v = tmp;
                if(u && v) {
                    n = -1;
                    p[i].siz = -1;
                }
            }
        }
        if(n != -1) cout << "NO" << endl;
        else {
            if(u == col || v == col);
            else if(p[rec[u]].siz > p[rec[v]].siz) u = col;
            else v = col;
            cout << "YES" << endl;
            cout << u << " " << v << endl;
        }
    }
    return 0;
}

T3ψ(｀∇´)ψ

以为自己能做出来想了大半天结果一分没有，最后赶紧去补 T1，结果手残打挂了主席树。

可以不用三维偏序，很妙的思路。

你对于这种 \(\sum\sum f(i,j)\) 的式子，处理套路目前来看无非就两种，一种是正攻，直接考虑怎么转化计算贡献的方式，另外一种就是考虑正难则反，我们求出 \(U\) 和答案的补集就行了。

这题就是考虑，假设所有位置都做了贡献，总答案显然是 \(2n\sum a(i,j)\)。

那么我们只需要算有多少个 \(a(i, j)\) 没做出贡献就行。

答案的 \(\min, \max\) 里面是类似的，这里只考虑 \(\min\)：

显然，对于一个 \(a(k, i) + a(k, j)\)，它不会对 \(\min\) 做出贡献，当且仅当存在 \(k^\prime\)，使得 \(a(k^\prime, i) + a(k^\prime, j) \le a(k, i) + a(k, j)\)。于是我们对于一个 \(i\)，数一下有多少个 \(j\) 满足这个条件就行。

然后就套路的移项，把 \(i, j\) 分别放到 \(\le\) 两边，问题转化为二维偏序。

于是树状数组维护即可，对于 \(\max\) 同理。

这里相当于只考虑了有 \(3\) 行被选出来的情况，于是我们枚举 \(m!\) 种可能做一下就行。

注意我们 \(\min, \max\) 同时做的时候可能两边取等，考虑强制钦定大小，随便选一边就行。

复杂度 \(O(n\log n)\)，带一个 \(4!\) 常数。树状数组记得开两倍然后平移一下，因为可能有负数。

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
// author : black_trees

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define endl '\n'
#define int long long

using namespace std;
using i64 = long long;

const int si = 2e5 + 5;
const int V = si << 1;
const int inf = 0x3f3f3f3f3f3f3f3fll;

int n, m;
int a[5][si], ord[] = {1, 2, 3, 4};

class Fenwick {
    private:
        int t[V + 10];
        inline int lowbit(int x) { return x & -x; }
    public:
        void init() { memset(t, 0, sizeof t); }
        void add(int x, int v) { while(x <= V) t[x] += v, x += lowbit(x); }
        int que(int x) { int ret = 0; while(x) ret += t[x], x -= lowbit(x); return ret; }
} tr;
struct Operations {
    int tyq, x, y, v;
    Operations() { tyq = x = y = v = 0; }
    Operations(int a, int b, int c, int d) : tyq(a), x(b), y(c), v(d) {}
    bool operator < (const Operations &t) const {
        if(x != t.x) return x < t.x;
        return tyq < t.tyq;
    }
} b[si << 1];

int solve(int p[]) {
    int e = p[0], f = p[1], g = p[2];
    tr.init(); int ret = 0, cnt = 0; 
    for(int i = 1; i <= n; ++i) {
        b[++cnt] = Operations(1, a[e][i] - a[f][i], a[f][i] - a[g][i], 0);
        b[cnt].x += (e > f), b[cnt].y += (f > g);
        b[++cnt] = Operations(2, a[f][i] - a[e][i], a[g][i] - a[f][i], a[f][i]);
    }
    sort(b + 1, b + 1 + cnt);
    for(int i = 1; i <= cnt; ++i) {
        auto [tyq, x, y, v] = b[i];
        if(tyq == 1) tr.add(y + si, 1);
        if(tyq == 2) ret += v * tr.que(y + si);
    }
    return ret;
}

signed main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    cin >> m >> n;
    for(int i = 1; i <= m; ++i) {
        for(int j = 1; j <= n; ++j) {
            cin >> a[i][j];
        }
    }
    for(int i = m + 1; i <= 4; ++i) {
        for(int j = 1; j <= n; ++j) {
            a[i][j] = a[i - m][j];
        }
    }

    int ans = 0;
    for(int i = 1; i <= 4; ++i) {
        for(int j = 1; j <= n; ++j) {
            ans += (2ll * n * a[i][j]);
        }
    }

    do {
        ans -= solve(ord);
    } while(next_permutation(ord, ord + 4));

    cout << ans << endl;

    return 0;
}
最后更新: May 9, 2023