P9571 Horizon Blue 题解
这个题拿平衡树写是不是小题大做了
咳咳咳进入正题。
首先转化一下题意。第一个操作是加入直线，第二个操作就是求所有斜率不等于 \(k\) 的直线的数量，第三个操作就是删掉所有斜率不等于 \(k\) 的和所有与该直线重合的直线。
感觉这题完全就是 FHQ_Treap 的板子题嘛，重载一下小于号，按 \(k\) 为第一关键字，\(b\) 为第二关键字来排序，这样，第一个操作直接插入；第二个操作按 \(k\) 裂成三部分，所求就是左右两部分的 \(siz\) 和；第三个操作的话，首先按照第二个操作分裂一次，扔掉两边；然后再将中间 \(k\) 与 \(b\) 恰好相同的分裂出来，扔掉，合并剩下的左右两部分。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+100;
const int INF = 0x3f3f3f3f;
inline int read(){
int x = 0, f = 1; char ch = getchar();
while(ch<'0' || ch>'9') {if(ch == '-') f = -1; ch = getchar();}
while(ch>='0'&&ch<='9') x = x*10+ch-48, ch = getchar();
return x * f;
}
struct Line{
int k, b;
bool operator < (const Line &y) const{
if(k == y.k){
return b < y.b;
}
return k < y.k;
}
};
mt19937 getrand(time(0));
struct node{
int ls, rs, siz;
int rnd;
Line val;
};
int root ;
struct FHQ_Treap{
node tree[N];
int idx;
int New(Line tmp){
++idx;
tree[idx] = {0, 0, 1, getrand(), tmp};
return idx;
}
void push_up(int x){
tree[x].siz = tree[tree[x].ls].siz+tree[tree[x].rs].siz+1;
}
void split(int pos, int &l, int &r, Line k){
if(!pos) return l = r = 0, void();
if(tree[pos].val < k){
l = pos;
split(tree[l].rs, tree[l].rs, r, k);
push_up(l);
} else{
r = pos;
split(tree[r].ls, l, tree[r].ls, k);
push_up(r);
}
}
int merge(int l, int r){
if(!l || !r) return l | r;
if(tree[l].rnd < tree[r].rnd){
tree[l].rs = merge(tree[l].rs, r);
push_up(l);
return l;
} else{
tree[r].ls = merge(l, tree[r].ls);
push_up(r);
return r;
}
}
void insert(Line tmp){
int dl, dr;
split(root, dl, dr, tmp);
root = merge(dl, merge(New(tmp), dr));
}
int query(Line tmp){
int dl, dr, md;
split(root, dl, dr, (Line){tmp.k, -INF});//把 b 设为负无穷，以保证 k 相等的只会在右子树。
split(dr, md, dr, (Line){tmp.k+1, -INF});//和上面类似。
int ret = tree[dl].siz+tree[dr].siz;
root = merge(dl, merge(md, dr));
return ret;
}
void erase(Line tmp){
int dl, dr, md;
split(root, dl, dr, (Line){tmp.k, -INF});
split(dr, md, dr, (Line){tmp.k+1, -INF});
split(md, dl, dr, tmp);//两次分裂，之前分离的两边的子树因为要删去，所以变量可以直接拿来重新使用。
split(dr, md, dr, (Line){tmp.k, tmp.b+1});
root = merge(dl, dr);
}
}s;
int n;
int main(){
n = read();
while(n--){
int op = read(), k = read(), b = read();
if(op == 1){
s.insert((Line){k, b});
} else if(op == 2){
printf("%d\n",s.query((Line){k, b}));
} else{
s.erase((Line){k, b});
}
}
return 0;
}