题目传送门 唯一的传送站 题目大意 一共有$n$个学生，以及$q$天需要安排任务。第$i$有$m_{i}$个任务，第$j$个任务必须由恰好$k_{i, j}$名学生去完成。第$i$名学生愿意参与一项需要人数恰
题目传送门
唯一的传送站
题目大意
一共有$n$个学生，以及$q$天需要安排任务。第$i$有$m_{i}$个任务，第$j$个任务必须由恰好$k_{i, j}$名学生去完成。第$i$名学生愿意参与一项需要人数恰好为$k$的任务当且仅当$A_i \leqslant k \leqslant B_i$。每个学生一天至多参与一项任务，也可以不参与任何任务。问每天是否存在分配方案。
真想吐槽为什么有人把IOI的题出进省选模拟赛。（显然我是看了题解的）
好像网上这道题没啥题解，稍微写良心一点。（noi官网上有题解，只是应该默认看IOI题解的人都是佬，所以写得很精炼，嗯，应该没用错词。）
先来说说34分做法。
考虑将$k$从小到大排序，对于每个任务能选择的学生中，肯定希望先选择右端点较小的。因为如果它不选这个学生，那么后面的任务更难选择它了。
然后就先对学生排一遍序，然后拿个堆就完事了。于是我们得到了34分的高分。
怎么优化这个算法呢？
考虑把学生看作二维平面内的点$(A, B)$，那么对于一个任务可以选择的学生是下图的阴影区域内的（包含边界）：
因为它要满足$A\leqslant k \wedge B\geqslant k$，将可行解画在二维平面上就是上面那样。
根据上面的贪心策略就是先选择下面的点。注意到点的横坐标的多少在影响是否可选之后没有意义了。
那么我们寻找一种比较舒服的取点的方式。假如我们在之前的取点过程中，不断将最后取的点的纵坐标为当前这个区域的上界。我们使得这些上界不断递减，例如：
其中蓝色的部分是已经取走点的部分。然后如何实现这样的一个东西？
考虑一级一级地向上取点，如果足够就把这一级的点全取走，合并上界。否则在主席树上求$k$大，找到新的上界加入栈。大概就是：
其中红色部分是尝试取走的部分，黄色部分是在主席树上二分得到的东西。（其实这里省掉了一次尝试取走的过程）
感觉思路还是挺简单的。我就说说我那丑陋的实现遇到的一大堆问题。
- 当上一次的上界比当前的$k$小时直接弹掉。
- 栈里不应有高度相同的上界。
- 上界中可能有多个点，可能包含未取的。
于是便成功造就了我的码题1小时，调试3小时（果然我是个菜菜的NOIP选手）。
另外说一下关于这道题的对拍。全随机很容易通过。
钦定$B$的值可以得到一些不错的数据。
然后我想了想，为什么转化到二维平面上就能实现优化。我觉得嘛，这东西有点像是二维偏序，在一维数组中自然不好处理，没有一种好的排序方式能够较好地处理。
最后orz杜瑜皓题解上的dp做法。想到Hall定理，也想不到这种神奇的dp。
Code
1 /** 2 * uoj 3 * Problem#231 4 * Accepted 5 * Time: 12591ms 6 * Memory: 304020k 7 */ 8 #include <bits/stdc++.h> 9 #include "teams.h" 10 using namespace std; 11 typedef bool boolean; 12 13 const int N = 5e5 + 5; 14 15 typedef class SegTreeNode { 16 public: 17 int s, id; 18 SegTreeNode *l, *r; 19 20 SegTreeNode():s(0), l(NULL), r(NULL) { } 21 SegTreeNode(int id, SegTreeNode* nul):s(0), id(id), l(nul), r(nul) { } 22 23 inline void pushUp() { 24 s = l->s + r->s; 25 } 26 }SegTreeNode; 27 28 #define Limit 4000000 29 30 SegTreeNode pool[Limit]; 31 SegTreeNode *top = pool; 32 SegTreeNode null(-1, &null); 33 34 SegTreeNode* newnode(int id) { 35 if (top - pool >= Limit) 36 return new SegTreeNode(id, &null); 37 top->id = id; 38 return top++; 39 } 40 41 typedef class ChairTree { 42 public: 43 int n; 44 SegTreeNode** rts; 45 46 ChairTree() { } 47 ChairTree(int n):n(n) { 48 rts = new SegTreeNode*[(n + 1)]; 49 for (int i = 0; i <= n; i++) 50 rts[i] = &null; 51 } 52 53 void update(SegTreeNode*& op, SegTreeNode*& p, int l, int r, int idx, int id) { 54 if (!p || p->id != id) 55 p = newnode(id), p->s = op->s, p->l = op->l, p->r = op->r; 56 if (l == r) { 57 p->s++; 58 return; 59 } 60 int mid = (l + r) >> 1; 61 if (idx <= mid) 62 update(op->l, p->l, l, mid, idx, id); 63 else 64 update(op->r, p->r, mid + 1, r, idx, id); 65 p->pushUp(); 66 } 67 68 int query(SegTreeNode*& p, int l, int r, int ql, int qr) { 69 if (l == ql && r == qr) 70 return p->s; 71 int mid = (l + r) >> 1; 72 if (qr <= mid) 73 return query(p->l, l, mid, ql, qr); 74 if (ql > mid) 75 return query(p->r, mid + 1, r, ql, qr); 76 return query(p->l, l, mid, ql, mid) + query(p->r, mid + 1, r, mid + 1, qr); 77 } 78 79 int query(SegTreeNode*& ap, SegTreeNode*& rp, int l, int r, int k) { 80 if (k > ap->s - rp->s) 81 return -1; 82 if (l == r) 83 return l; 84 int ls = ap->l->s - rp->l->s, mid = (l + r) >> 1; 85 if (ls >= k) 86 return query(ap->l, rp->l, l, mid, k); 87 return query(ap->r, rp->r, mid + 1, r, k - ls); 88 } 89 90 void update(int nv, int idx) { 91 update(rts[nv - 1], rts[nv], 1, n, idx, nv); 92 } 93 94 int query(int vl, int vr, int l, int r) { 95 if (l > r) return 0; 96 return query(rts[vr], 1, n, l, r) - query(rts[vl], 1, n, l, r); 97 } 98 99 int query(int vl, int vr, int k) { 100 return query(rts[vr], rts[vl], 1, n, k); 101 } 102 }ChairTree; 103 104 int n; 105 vector<int> *g; 106 ChairTree ct; 107 108 void init(int n, int* A, int* B) { 109 ::n = n; 110 g = new vector<int>[(n + 1)]; 111 ct = ChairTree(n); 112 for (int i = 0; i < n; i++) 113 g[A[i]].push_back(B[i]); 114 for (int i = 1; i <= n; i++) { 115 for (int j = 0; j < (signed) g[i].size(); j++) 116 ct.update(i, g[i][j]); 117 if (!g[i].size()) 118 ct.rts[i] = ct.rts[i - 1]; 119 } 120 } 121 122 typedef class Data { 123 public: 124 int p, h, r; 125 126 Data(int p = 0, int h = 0, int r = 0):p(p), h(h), r(r) { } 127 }Data; 128 129 Data st[N]; 130 131 int can(int m, int* K) { 132 int tp = -1; 133 sort(K, K + m); 134 st[++tp] = Data(0, n, 0); 135 for (int i = 0; i < m; i++) { 136 while (tp && st[tp].h < K[i]) 137 tp--; 138 int finded = ct.query(st[tp].p, K[i], K[i], K[i]), used = 0; 139 while (tp && st[tp].h == K[i]) 140 finded += ct.query(st[tp - 1].p, st[tp].p, K[i], K[i]) - st[tp].r, used += st[tp].r, tp--; 141 if (finded >= K[i]) { 142 st[++tp] = Data(K[i], K[i], K[i] + used); 143 continue; 144 } 145 int nf = finded, h = K[i]; 146 // cerr << i << " Init " << nf << " " << h << " " << tp << endl; 147 while (nf < K[i]) { 148 nf = nf + ct.query(st[tp].p, K[i], h + 1, st[tp].h); 149 if (nf >= K[i]) { 150 int k = K[i] - finded + ct.query(st[tp].p, K[i], 1, h); 151 // cerr << k << endl; 152 h = ct.query(st[tp].p, K[i], k); 153 int r = k - ct.query(st[tp].p, K[i], 1, h - 1); 154 // cerr << r << endl; 155 while (st[tp].h == h) 156 r += st[tp].r, tp--; 157 st[++tp] = Data(K[i], h, r); 158 // cerr << "New data added " << K[i] << " " << h << " " << r << endl; 159 assert(st[tp].h <= n); 160 break; 161 } 162 h = st[tp].h, finded = nf; 163 // cerr << i << " Rect " << nf << " " << h << " " << tp << endl; 164 nf = nf + ct.query(st[tp - 1].p, st[tp].p, h, h) - st[tp].r; 165 tp--; 166 if (nf >= K[i]) { 167 int r = K[i] - finded + ct.query(st[tp + 1].p, K[i], h, h) + st[tp + 1].r; 168 while (st[tp].h == h) 169 r += st[tp].r, tp--; 170 st[++tp] = Data(K[i], h, r); 171 // cerr << "New data added " << K[i] << " " << h << " " << r << endl; 172 assert(st[tp].h <= n); 173 } else if (tp == -1 && nf < K[i]) 174 return 0; 175 finded = nf; 176 // cerr << i << " Rest " << nf << " " << h << " " << tp << endl; 177 } 178 } 179 return 1; 180 }