yaoxi-std 的博客

$\text{开}\mathop{\text{卷}}\limits^{ju\check{a}n}\text{有益}$

0%

P5861 [IOI2015] teams 分组

发表于 分类于

P5861 [IOI2015] teams 分组

挂的最惨的一次模拟赛了没有之一（$200$挂到$13$的那个就是我）

题面

题目链接

解法

这是一个 $O(N \log N + S \log^2 N)$ 的方法，可能需要卡卡常才能过。不需要主席树只需要线段树套 vector 再进行一堆奇怪的操作

容易想到贪心思路：先将 $K[i]$ 从小到大排序，每次取 $B[j]$ 最小的 $K[i]$ 个，这样显然是最优的。

所以可以对于每个学生，在线段树的 $B[i]$ 处插入一个数 $A[i]$。在处理 $K[i]$ 时，在线段树上二分出最小的 $r$ 使得有 $\ge K$ 个 $A[i] \le K \le B[i] \le r$，然后将对应的 $K$ 个学生删除。

思路很简单，下面是实现。因为在询问过程中不需要对学生进行修改，所以就可以在预处理阶段就构建出这个线段树套 vector 并排好序。

考虑如何在线段树上二分，这个很套路，首先由于 $K[i]$ 递增，所以 $B[i] < K$ 的已经没有用了，全部删去。然后就考虑的是一个最小的前缀 $r$ 使有 $\ge K$ 个 $A[i] \le K$ 并且 $B[i] \le R$，直接普通的线段树二分即可。由于还需要在 vector 上再次二分，所以一次操作为 $O(\log^2 N)$。

然后考虑删除，显然对于线段树上每个节点，删除掉的都是 vector 中的一段前缀，于是想到对每个节点维护一个 $pos$ 表示已经删掉了前 $pos$ 个，这样就可以对每个节点快速删除了，只需要在线段树上找到对应的区间并更新 $pos$ 就行。

最后在做完一次询问需要清空。显然清空就是将所有的 $pos$ 赋成 $0$，维护一个是否清空的标记 $cls$ 并 pushdown 即可。

AC代码

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
/**
 * @file:           teams.cpp
 * @author:         yaoxi-std
 * @url:            https://www.luogu.com.cn/problem/P5861
*/
// #pragma GCC optimize ("O2")
// #pragma GCC optimize ("Ofast", "inline", "-ffast-math")
// #pragma GCC target ("avx,sse2,sse3,sse4,mmx")
#include <bits/stdc++.h>
using namespace std;
#define resetIO(x) \
    freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout)
#define debug(fmt, ...) \
    fprintf(stderr, "[%s:%d] " fmt "\n", __FILE__, __LINE__, ##__VA_ARGS__)
namespace fastio {
const int MAXBUF = 1 << 21;
char buf[MAXBUF], *p1 = buf, *p2 = buf;
char pbuf[MAXBUF], *pp = pbuf;
inline char getc() { return (p1 == p2) && (p2 = (p1 = buf) + fread(buf, 1, MAXBUF, stdin)), *p1++; }
inline void putc(char c) { (pp == pbuf + MAXBUF) && (fwrite(pbuf, 1, MAXBUF, stdout), pp = pbuf), *pp++ = c; }
inline void print_final() { fwrite(pbuf, 1, pp - pbuf, stdout), pp = pbuf; }
};  // namespace fastio
using namespace fastio;
template <class _Tp>
inline _Tp& read(_Tp& x) {
    bool sign = false; char ch = getc();
    for (; !isdigit(ch); ch = getc()) sign |= (ch == '-');
    for (x = 0; isdigit(ch); ch = getc()) x = x * 10 + (ch ^ 48);
    return sign ? (x = -x) : x;
}
template <class _Tp>
inline void write(_Tp x) {
    if (x < 0) putc('-'), x = -x;
    if (x > 9) putc(x / 10);
    putc((x % 10) ^ 48);
}
bool m_be;
using ll = long long;
const int MAXN = 5e5 + 10;
const int INF = 0x3f3f3f3f;
struct SegmentTree {
    #define li (i << 1)
    #define ri (i << 1 | 1)
    #define lson li, l, mid
    #define rson ri, mid + 1, r
    int pos[MAXN * 4];           // 已经删掉几个数了
    bool cls[MAXN * 4];          // 是否要清空的标记
    vector<int> vec[MAXN * 4];   // 对应 vector
    // 为了排序
    void build(int i, int l, int r) {
        pos[i] = 0;
        sort(vec[i].begin(), vec[i].end());
        if (l == r) return;
        int mid = (l + r) >> 1;
        build(lson), build(rson);
    }
    // 插入，全部的插入操作结束后需要 build 来排序
    void insert(int i, int l, int r, int q, int v) {
        vec[i].emplace_back(v);
        if (l == r) return;
        int mid = (l + r) >> 1;
        q <= mid ? insert(lson, q, v) : insert(rson, q, v);
    }
    // 节点 i 中未被删除的 <=p 的数字数量
    int count(int i, int p) {
        return upper_bound(vec[i].begin(), vec[i].end(), p) - vec[i].begin() - pos[i];
    }
    // 下传标记
    void pushdown(int i) {
        // 如果需要清空就直接清空
        if (cls[i]) cls[i] = 0, cls[li] = cls[ri] = 1, pos[li] = pos[ri] = 0;
        // 不需要下传
        if (pos[i] == pos[li] + pos[ri]) return;
        // 由于删掉的一定是前 pos[i] 个，所以儿子节点中小于 vec[i][pos[i]-1] 
        // 的一定已经要被删掉，剩下的等于 vec[i][pos[i]-1] 的就优先删除 B[i] 
        // 更小的也就是左儿子中的。
        int x = vec[i][pos[i] - 1];
        pos[li] += count(li, x - 1), pos[ri] += count(ri, x - 1);
        int p = pos[i] - pos[li] - pos[ri], t = count(li, x);
        (p <= t) ? (pos[li] += p) : (pos[li] += t, pos[ri] += p - t);
    }
    // 查询 B[i] 在区间 [ql,qr] 的学生中还有多少个 A[i]<=p 的
    int query(int i, int l, int r, int ql, int qr, int p) {
        if (ql > qr) return 0;
        if (ql <= l && r <= qr) return count(i, p);
        int mid = (l + r) >> 1, ret = 0; pushdown(i);
        if (ql <= mid) ret += query(lson, ql, qr, p);
        if (qr > mid) ret += query(rson, ql, qr, p);
        return ret;
    }
    // 二分出最小的 R 使得有 >=k 个 A[i]<=p 且 B[i]<=R
    // 这里是把 二分 和 删除 放到一个函数里了，应该看得懂吧
    int bound(int i, int l, int r, int p, int k) {
        if (l == r) return pos[i] += k, l;
        int mid = (l + r) >> 1; pushdown(i);
        int tmp = count(li, p), ret;
        if (k <= tmp) ret = bound(lson, p, k);
        else pos[li] += tmp, ret = bound(rson, p, k - tmp);
        return pos[i] = pos[li] + pos[ri], ret;
    }
} sgt;
int n, q, m, a[MAXN], b[MAXN], k[MAXN];
bool m_ed;
signed main() {
    resetIO(teams);
    // debug("Mem %.5lfMB.", fabs(&m_ed - &m_be) / 1048576);
    read(n);
    for (int i = 1; i <= n; ++i) read(a[i]), read(b[i]);
    for (int i = 1; i <= n; ++i)
        sgt.insert(1, 1, n, b[i], a[i]);
    sgt.build(1, 1, n);
    read(q);
    while (q--) {
        bool ans = 1; ll sum = 0; read(m);
        for (int i = 1; i <= m; ++i) read(k[i]), sum += k[i];
        if (sum > n) { putc('0'), putc('\n'); continue; }
        sort(k + 1, k + m + 1);
        sgt.cls[1] = 1, sgt.pos[1] = 0; // 记得打上清空的标记
        for (int i = 1; i <= m; ++i) {
            // B[i] < K[i] 的不再有用，可以直接删掉
            int rem = k[i] + sgt.query(1, 1, n, 1, k[i] - 1, k[i]);
            if (sgt.count(1, k[i]) < rem) { ans = 0; break; }
            sgt.bound(1, 1, n, k[i], rem);
        }
        putc(ans ? '1' : '0'), putc('\n');
    }
    return print_final(), 0;
}