题解 P1533 【可怜的狗狗】

Rbu_nas

2019-08-14 16:06:40

Solution

这题我本来以为只是一道清新的小水题,然而却调了我一上午 TAT 看到区间第 k 小立刻联想到平衡树,但是问题在于这是有区间范围的嗷,每次都重新把区间里的点都加进来肯定 gg,所以就可以离线然后[莫队](https://blog.sengxian.com/algorithms/mo-s-algorithm)求解 这道题要注意先插入再删除,就是说我们默认我们的左右端点 $l$,$r$ 是在询问范围 $[ql,\ qr]$ 前的,这样子添加点肯定没有影响。但如果不这样的话,若询问给出 $[2,\ 3]$ 这样的区间,而我们的左右端点一开始是 $l = 1, r = 0$ 的,树里面也没有点,开始移动时会先删除 $l = 1$ 呀,然后 $l+1\ \to \ l=2$,但我们删除 $l = 1$ 就会挂啊,因为树没有节点,然后程序就会奇奇怪怪的把第一只狗的颜值弄进树了emm 另外就是很多平衡树题目题解里都会先插入 $inf$ 与 $-inf$,我认为**部分**题目其实不需要啊,因为不存在什么查找会越界吧。如果是我理解错误麻烦大佬能指出orz 这里给出 fhqTreap 与 vector 的代码实现。 ```cpp #include <cstdio> #include <cmath> #include <cstdlib> #include <iostream> #include <algorithm> using namespace std; const int inf = 2100000000; const int N = 300007; template < class T > inline void read(T &x) { x = 0; bool f = 1; register char ch = getchar(); for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = 0; for(; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48); x = f ? x : -x; } int n, m; int a[N], Ans[N]; int root, cnt; struct fhqTreap { int l, r; int val, key; int size; }; fhqTreap tr[N << 1]; inline void pushUp(int p) { tr[p].size = tr[tr[p].l].size + tr[tr[p].r].size + 1; } inline int newnode(int val) { ++cnt; tr[cnt].l = tr[cnt].r = 0; tr[cnt].val = val, tr[cnt].key = rand(); tr[cnt].size = 1; return cnt; } void split(int p, int val, int &x, int &y) { if(!p) { x = y = 0; return ; } if(tr[p].val <= val) { x = p; split(tr[p].r, val, tr[p].r, y); } else { y = p; split(tr[p].l, val, x, tr[p].l); } pushUp(p); } int merge(int x, int y) { if(!x || !y) return x | y; if(tr[x].key > tr[y].key) { tr[x].r = merge(tr[x].r, y); pushUp(x); return x; } else { tr[y].l = merge(x, tr[y].l); pushUp(y); return y; } } int kthNum(int p, int k) { if(k <= tr[tr[p].l].size) return kthNum(tr[p].l, k); else if(k == tr[tr[p].l].size + 1) return p; else { k -= (tr[tr[p].l].size + 1); return kthNum(tr[p].r, k); } } //以上为 fhq-treap 板子 struct captainMo { int l, r, k, id, block; }; captainMo q[N]; inline bool cmp(captainMo a, captainMo b) { return (a.block ^ b.block) ? a.block < b.block : (a.block & 1) ? a.r < b.r : a.r > b.r; } //使用奇偶性排序加速,这里不细讲。 inline void del(int t) { int val = a[t], x, y, z; split(root, val, x, y); split(x, val - 1, x, z); z = merge(tr[z].l, tr[z].r); root = merge(merge(x, z), y); } //树中删除下标为 t 的狗的颜值 inline void add(int t) { int val = a[t], x, y; split(root, val, x, y); root = merge( merge(x, newnode(val)), y ); } //添加下标为 t 的狗的颜值 signed main() { srand(1******7); read(n); read(m); //块的大小设为 n/√(m*2/3) 玄学加速 register int S = n / sqrt((m << 1) / 3); for(register int i = 1; i <= n; ++i) read(a[i]); for(register int i = 1; i <= m; ++i) { read(q[i].l), read(q[i].r), read(q[i].k); q[i].id = i, q[i].block = q[i].l / S; } sort(q + 1, q + m + 1, cmp); //莫队操作 register int l = 1, r = 0; for(register int i = 1; i <= m; ++i) { while(l > q[i].l) add(--l); while(r < q[i].r) add(++r); while(l < q[i].l) del(l++); while(r > q[i].r) del(r--); Ans[q[i].id] = tr[kthNum(root, q[i].k)].val; //记录此询问的位置的答案 } for(register int i = 1; i <= m; ++i) printf("%d\n", Ans[i]); return 0; } ``` ```cpp #pr\ agma GCC optimize(3) #include <bits/stdc++.h> using namespace std; const int inf = (1 << 30); const int N = 300007; template < class T > inline void read(T &x) { x = 0; bool f = 1; register char ch = getchar(); for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = 0; for(; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48); x = f ? x : -x; } int n, m; int a[N], Ans[N]; vector < int > v; struct captainMo { int l, r, k, id, block; }; captainMo q[N]; inline bool cmp(captainMo a, captainMo b) { return (a.block ^ b.block) ? a.block < b.block : (a.block & 1) ? a.r < b.r : a.r > b.r; } inline void del(int t) { v.erase(lower_bound(v.begin(), v.end(), a[t])); } inline void add(int t) { v.insert(lower_bound(v.begin(), v.end(), a[t]), a[t]); } signed main() { read(n); read(m); v.push_back(inf); v.push_back(-inf); //这里是为了不 lower_bound 出界 RE register int S = n / sqrt((m << 1) / 3); for(register int i = 1; i <= n; ++i) read(a[i]); for(register int i = 1; i <= m; ++i) { read(q[i].l), read(q[i].r), read(q[i].k); q[i].id = i, q[i].block = q[i].l / S; } sort(q + 1, q + m + 1, cmp); register int l = 1, r = 0; for(register int i = 1; i <= m; ++i) { while(l > q[i].l) add(--l); while(r < q[i].r) add(++r); while(l < q[i].l) del(l++); while(r > q[i].r) del(r--); Ans[q[i].id] = v.at(q[i].k + 1); //插入了-inf且不会被删除,所以排名+1 } for(register int i = 1; i <= m; ++i) printf("%d\n", Ans[i]); return 0; } ```