[IOI2015]teams分组 - 题目 - 黑暗爆炸OJ

考虑对于一个点 $i$ 的区间 $[l_i, r_i]$ 不妨假设按照 $l_i$ 从小到大排列，如果一个点 $i$ 是可以取到的情况，我们可以发现对于所有可以取到的肯定是选 $r_i$ 最小的进行取走。

我们考虑对于每个询问从小到大来做，考虑将每个 $[l_i, r_i]$ 对应到二维平面的 $(x, y)$ 上，对于每个询问记录在这次询问之后没有被取走的 $y$ 的最小值，设其为 $h_i$。

那么对于一个 $k_x$ 如果 $h_i < k_x$ 显然是可以直接取的，如果出现 $h_i > k_x$ 我们需要考虑其剩下没有取的元素，这个东西可以通过单调栈来维护。

之后对于平面上二维数点，直接使用可持久化线段树即可。

考虑加入一个元素的情况，直接在线段树二分位置即可。

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
#include <bits/stdc++.h>
using namespace std;
namespace Legendgod {
	namespace Read {
//		#define Fread
		#ifdef Fread
		const int Siz = (1 << 21) + 5;
		char *iS, *iT, buf[Siz];
		#define gc() ( iS == iT ? (iT = (iS = buf) + fread(buf, 1, Siz, stdin), iS == iT ? EOF : *iS ++) : *iS ++ )
		#define getchar gc
		#endif
		template <typename T>
		void r1(T &x) {
		    x = 0;
			char c(getchar());
			int f(1);
			for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
			for(; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
			x *= f;
		}
		template <typename T, typename...Args>
		void r1(T &x, Args&...arg) {
			r1(x), r1(arg...);
		}
		#undef getchar
	}

using namespace Read;

const int maxn = 1e7 + 5;
int n, m, N, tot(0);
int t[maxn], lson[maxn], rson[maxn];
struct Seg {
    #define ls lson[p]
    #define rs rson[p]
    #define mid ((l + r) >> 1)
    void Insert(int& p,int pre,int l,int r,int pos) {
        p = ++ tot;
        t[p] = t[pre] + 1;
        ls = lson[pre], rs = rson[pre];
        if(l == r) return ;
        if(pos <= mid) Insert(ls, lson[pre], l, mid, pos);
        else Insert(rs, rson[pre], mid + 1, r, pos);
    }
    int Querypos(int p,int pre,int l,int r,int K) {
        if(l == r) return l;
        int tmp = t[rs] - t[rson[pre]];
        if(tmp >= K) return Querypos(rs, rson[pre], mid + 1, r, K);
        else return Querypos(ls, lson[pre], l, mid, K - tmp);
    }
    int Query(int p,int pre,int l,int r,int ps) {
        if(!p) return 0;
        if(l == r) return t[p] - t[pre];
        if(ps <= mid) return Query(ls, lson[pre], l, mid, ps) + t[rs] - t[rson[pre]];
        else return Query(rs, rson[pre], mid + 1, r, ps);
    }

    #undef ls
    #undef rs
    #undef mid
}T;

struct Node{
    int l, r;
    int operator < (const Node &z) const {
        return l < z.l;
    }
}a[maxn];

int st[maxn], hater[maxn], k[maxn], sp[maxn];
int rt[maxn];

signed main() {
    freopen("teams.in", "r", stdin);
    freopen("teams.out", "w", stdout);
	int i, j;
    r1(n);
    N = n + 1;
    for(i = 1; i <= n; ++ i) r1(a[i].l, a[i].r);
    sort(a + 1, a + n + 1);
    int ed = 1;
    for(i = 1; i <= N; ++ i) {
        rt[i] = rt[i - 1];
        while(ed <= n && a[ed].l == i) T.Insert(rt[i], rt[i], 1, N, a[ed].r), ++ ed;
    }
    int Q; r1(Q); while(Q --) {
        r1(m);
        for(i = 1; i <= m; ++ i) r1(k[i]);
        sort(k + 1, k + m + 1);
        int ln(0);
        for(i = 1; i <= m; ++ i) {
            /*
            hater[i]
            the lowest height in ith operation we didn't used
            sp[i]
            the points we left (didn't used)
            Hater !!!!
            */
            while(ln && hater[ln] < k[i]) -- ln;
//            printf("SSS %d : %d\n", k[st[ln]], k[i]);
            int sum = sp[ln];
            sum += T.Query(rt[k[i]], rt[k[st[ln]]], 1, N, k[i]) - k[i];
//        printf("i = %d, sum = %d, ln = %d\n", i, sum, ln);
            if(sum < 0) { puts("0"); break; }
            else if(i == m) { puts("1"); break; }
            int nh = T.Querypos(rt[k[i]], rt[k[st[ln]]], 1, N, sum - sp[ln]);
            while(nh > hater[ln] && ln) {
                -- ln;
                nh = T.Querypos(rt[k[i]], rt[k[st[ln]]], 1, N, sum - sp[ln]);
            }
            st[++ ln] = i, sp[ln] = sum, hater[ln] = nh;
//            printf("hater[1] = %d\n", hater[1]);
        }
    }
	return 0;
}

}


signed main() { return Legendgod::main(), 0; }//