Blog of RuSun

\begin {array}{c} \mathfrak {One Problem Is Difficult} \\\\ \mathfrak {Because You Don't Know} \\\\ \mathfrak {Why It Is Diffucult} \end {array}

NOI Online 2022 提高级

发表于 分类于
本文字数： 9.1k 阅读时长 ≈ 8 分钟
标签：                

被单调队列的一场。

T1 P8251 [NOI Online 2022 提高组] 丹钓战

单调栈模拟题意过程，得到一个元素下面的元素编号 $p _ i$ ，该元素贡献答案当且仅当下面的元素不在 $l - r$ 内，于是题意转化为 $l - r$ 内小于 $l$ 的个数，用主席树维护即可。

查看代码 
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
#include <cstdio>
using namespace std;
template <class Type>
void read(Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type>
void write(Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar(x % 10 + '0');
}
const int N = 5e5 + 10, M = 1e7 + 10;
struct Data
{
    int a, b;
} w[N];
int top, stk[N];
int n, q, idx, p[N], rt[N];
struct Node
{
    int l, r, s;
} tr[M];
void pushup (int x)
{
    tr[x].s = tr[tr[x].l].s + tr[tr[x].r].s;
}
void modify(int &x, int t, int l = 0, int r = n - 1)
{
    tr[++idx] = tr[x];
    x = idx;
    if (l == r)
        return tr[x].s++, void();
    int mid = l + r >> 1;
    t <= mid ? modify(tr[x].l, t, l, mid) : modify(tr[x].r, t, mid + 1, r);
    pushup(x);
}
int query (int x, int y, int k, int l = 0, int r = n - 1)
{
    if (l > k)
        return 0;
    if (r <= k)
        return tr[y].s - tr[x].s;
    int mid = l + r >> 1;
    return query(tr[x].l, tr[y].l, k, l, mid) + query(tr[x].r, tr[y].r, k, mid + 1, r);
}
int main ()
{
    read(n), read(q);
    for (int i = 1; i <= n; i++)
        read(w[i].a);
    for (int i = 1; i <= n; i++)
        read(w[i].b);
    for (int i = 1; i <= n; i++)
    {
        while (top && (w[stk[top]].a == w[i].a || w[stk[top]].b <= w[i].b))
            top--;
        p[i] = stk[top];
        stk[++top] = i;
    }
    for (int i = 1; i <= n; i++)
        modify(rt[i] = rt[i - 1], p[i]);
    for (int l, r; q; q--)
    {
        read(l), read(r);
        write(query(rt[l - 1], rt[r], l - 1)), puts("");
    }
    return 0;
}

T2 P8252 [NOI Online 2022 提高组] 讨论

在没有找到答案之前，对于所有的集合，一定是相互独立或者其中一个在另一个内部。对于其中一些集合在一个集合内部的情况，也是不相交的。考虑如图维护这样的关系。一旦新的集合跨越了两个及以上的颜色，则有答案。

维护一个 $v _ i$ 表示会 $i$ 题的一个人，即图中的颜色。

将所有的人按会的题目的数量从大到小排序，这样保证了后面的一定不包含前面的，对于新加入的颜色，如果完全在一个颜色内，那么将这个集合内全部设为新的颜色。否则，它可以构成答案。

注意，选择答案的时候，要选择其中集合大小最小的，否则可能出现被包含的情况。

查看代码 
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 <cstdio>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
template <class Type>
void read(Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type>
void write(Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar(x % 10 + '0');
}
const int N = 1e6 + 10;
struct Node
{
    int id;
    Node(int x)
    {
        id = x;
    }
    set<int> v;
    bool operator<(const Node &_) const
    {
        return v.size() > _.v.size();
    }
};
vector<Node> w;
int n, v[N];
bool cmp(int x, int y)
{
    if (w[x].v.size() ^ w[y].v.size())
        return w[x].v.size() < w[y].v.size();
    return x < y;
}
void solve()
{
    read(n);
    w.clear();
    for (int i = 1; i <= n; i++)
        v[i] = -1;
    for (int i = 1, k; i <= n; i++)
    {
        Node t(i);
        read(k);
        for (int a; k; k--)
        {
            read(a);
            t.v.insert(a);
        }
        w.push_back(t);
    }
    sort(w.begin(), w.end());
    for (int i = 0; i < n; i++)
    {
        vector<int> t;
        bool flag = false;
        for (int j : w[i].v)
            ~v[j] ? (t.push_back(v[j]), 0) : flag = true;
        sort(t.begin(), t.end(), cmp);
        if (t.erase(unique(t.begin(), t.end()), t.end()) - t.begin() > 1 || (flag && !t.empty()))
            return printf("YES\n%d %d\n", w[i].id, w[t[0]].id), void();
        for (int j : w[i].v)
            v[j] = i;
    }
    puts("NO");
}
int main()
{
    int T;
    read(T);
    while (T--)
        solve();
    return 0;
}

T3 P8253 [NOI Online 2022 提高组] 如何正确地排序

注意到 $m$ 较小，按每一行考虑，对于最大值，对于一行的两个数 $a _ i, a _ j$ 有贡献，不考虑相等，当且仅当对于其他行每一行有：
$$
a _ i + a _ j > b _ i + b _ j
$$
即
$$
(a _ i - b _ i) > -(a _ j - b _ j)
$$
相等的时候只能算一次，

即可以写作：
$$
(a _ i - b _ i) \ge -(a _ j - b _ j) + [j < i]
$$
于是转化为三维偏序问题。将所有值分为两类，将等式右边的值在树状数组上修改，贡献到左侧的值上。

对于最小值，将所有数变为相反数，再做一次，答案取相反数。

注意到问题为 $\displaystyle \sum _ {i = 1} ^ n \sum _ {j = 1} ^ n f(i, j)$ ，即 $f(i, j)$ 和 $f(j, i)$ 都贡献答案，所以答案需要乘二。

查看代码 
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
#include <cstdio>
#include <algorithm>
#include <cassert>
using namespace std;
typedef long long LL;
template <class Type>
void read(Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type>
void write(Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar(x % 10 + '0');
}
const int N = 2e5 + 10, inf = 2e5;
int v[4][N];
struct Node
{
    int v[3], op, res;
    friend bool operator<(const Node &x, const Node &y)
    {
        for (int i = 0; i < 3; i++)
            if (x.v[i] ^ y.v[i])
                return x.v[i] < y.v[i];
        return x.op < y.op;
    }
};
namespace CDQ
{
    int tr[inf << 1];
    void modify(int x, int k)
    {
        for (x += inf; x < inf << 1; x += x & -x)
            tr[x] += k;
    }
    int query(int x)
    {
        int res = 0;
        for (x += inf; x; x -= x & -x)
            res += tr[x];
        return res;
    }
    void cdq(int l, int r, Node *w)
    {
        if (l == r)
            return;
        int mid = l + r >> 1;
        cdq(l, mid, w), cdq(mid + 1, r, w);
        int t = 0;
        static Node tmp[N << 1];
        for (int i = l, j = mid + 1; i <= mid || j <= r;)
            if (i <= mid && (j > r || w[i].v[1] <= w[j].v[1]))
            {
                w[i].op == -1 && (modify(w[i].v[2], 1), 0);
                tmp[t++] = w[i++];
            }
            else if (j <= r && (i > mid || w[i].v[1] > w[j].v[1]))
            {
                ~w[j].op && (w[j].res += query(w[j].v[2]));
                tmp[t++] = w[j++];
            }
        for (int i = l; i <= mid; i++)
            w[i].op == -1 && (modify(w[i].v[2], -1), 0);
        for (int i = l; i <= r; i++)
            w[i] = tmp[i - l];
    }
    LL main(int n, int k, Node *w)
    {
        sort(w, w + n);
        cdq(0, n - 1, w);
        LL res = 0;
        for (int i = 0; i < n; i++)
        {
            ~w[i].op && (res += (LL)v[k][w[i].op] * w[i].res);
            w[i].res = 0;
        }
        return res;
    }
}
int m, n;
LL solve()
{
    LL res = 0;
    static Node w[N << 1];
    for (int i = 0; i < m; i++)
    {
        int t = 0;
        for (int k = 0; k < n; k++)
        {
            w[t++].op = -1;
            for (int j = 0, p = 0; j < m; j++)
            {
                if (j == i)
                    continue;
                w[t].v[p] = v[i][k] - v[j][k];
                w[t ^ 1].v[p] = v[j][k] - v[i][k] + (j < i);
                p++;
            }
            w[t++].op = k;
        }
        res += CDQ::main(t, i, w);
    }
    return res;
}
int main()
{
    read(m), read(n);
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            read(v[i][j]);
    LL res = solve();
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            v[i][j] *= -1;
    printf("%lld", res - solve() << 1);
    return 0;
}
相关文章