题解 P1533 【可怜的狗狗】
Rbu_nas
2019-08-14 16:06:40
这题我本来以为只是一道清新的小水题,然而却调了我一上午 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;
}
```