首页 > 其他分享 >P9571 Horizon Blue 题解

P9571 Horizon Blue 题解

时间:2023-08-19 20:22:04浏览次数:37  
标签:Blue ch int 题解 P9571 操作

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;
}

标签:Blue,ch,int,题解,P9571,操作
From: https://www.cnblogs.com/frostwood/p/17643029.html

相关文章

  • P9572 Colorful Days♪ 题解
    原题链接题目大意:有两个数组\(S\),\(T\),你可以把\(S\)进行复制并接到其后面形成\(S^k\),如\(S\)=123,则\(S^2\)=123123,\(S^3\)=123123123。让你求出\(S^k\)与\(T\)的最长公共子序列以及在最长公共子序列最长时\(k\)的最小值。首先思考如果无视\(k\)最小的要求,最......
  • P4197 Peaks 题解
    P4197Peaks题解题目描述在Bytemountains有\(n\)座山峰,每座山峰有他的高度\(h_i\)。有些山峰之间有双向道路相连,共\(m\)条路径,每条路径有一个困难值,这个值越大表示越难走。现在有\(q\)组询问,每组询问询问从点\(v\)开始只经过困难值小于等于\(x\)的路径所能到达的......
  • P9571 Horizon Blue 题解
    原题链接题目大意:\(有三个操作,分别为\)\(操作1加入一条直线\)\(操作2查询与一条直线相交但不重合的直线条数\)\(操作3删除所有与一条直线相交或重合的直线\)\(注意:后面两个操作的直线并不需要加入\)\(显然,两条直线相交不重合,当且仅当其k值不同\)\(所以可以把所有直线按k......
  • 寻宝 题解
    寻宝题目大意存在\(n\)个点和两种有向边:一类边分\(m\)组,每组的边权相同,从\([s_l,s_r]\)中的所有点连向\([t_l,t_r]\)中的所有点。二类边存在于任意两点\(i,j\)间,从\(i\)连向\(j\)的二类边的边权为\(|i-j|\timesa_i\)。求从点\(1\)到\(n\)的最短路......
  • P9425 [蓝桥杯 2023 国 B] AB 路线 题解
    ~~应该能过官方数据吧~~---回归正题。我开始想过更简单的深搜,但是我怕无法记忆化,所以选择了广搜。和普通的广搜不同,此题的队列要存$3$个维度,分别是$x$,$y$,$z$,分别表示横坐标、纵坐标、目前的步数模$2k$的值。此时我们可以把每$2k$步进行分组,前$k$步走在```A```的格子......
  • 洛谷P5410 【模板】扩展 KMP(Z 函数)题解
    题目链接P5410【模板】扩展KMP(Z函数)-洛谷|计算机科学教育新生态(luogu.com.cn) 分析先考虑z数组设nx[i]为字符串b与b以b[i]开头的后缀最长公共前缀设i为当前需要求的位置当前i+nx[i]-1的最大值所对应的i为q p为i对应的位置当i大于q+nx[q......
  • arc139,arc140,arc141题解
    ARC139A-DATrailingZeros憨的。BMakeN感觉没有那么naive。首先用\(1\)去更新一下后面两个决策的价值。然后有一个较为显然的东西是说\(\text{lcm}\)为周期,周期内应该贪心取最大的。周期外由于范围很小,可以直接枚举一种决策的次数,取最小值即可。复杂度是正确的。CO......
  • Luogu P9510 『STA - R3』高维立方体 题解
    题目传送门没见过这玩意,写个题解记下。题目大意周知斐波那契数列定义为:\[\operatorname{fib}(n)=\left\{\begin{aligned}1&&n\le2\\\operatorname{fib}(n-1)+\operatorname{fib}(n-2)&&n>2\end{aligned}\right.\]然后定义(\(n\le0\)函数值为\(0\))\[f(n)......
  • CF-1860C Game on Permutation题解
    题意:在一条数轴上,Alice可以跳到在你所在点前面且值比当前所在点小的点。每回合可以向任意符合要求的点跳一次。当轮到Alice的回合同时不存在符合要求的点,Alice就赢了。Alice可以选择一个点作为起始点,然后作为后手(赛时这里把我坑了)。问有多少个点是必胜的点。\(n\leq3\times10^5......
  • P6429 [COCI2008-2009#1] JEZ 题解
    题目传送门:Click。某蒟蒻看见这道题,想了足足一个晚上,过后茅塞顿开,故作此篇。感谢神犇的题解。看题目数据范围:\(1\leqr,c\leq10^6,1\leqk\leq10^{12}\),显然打暴力\(\mathcal{O}(rc)\)的时间复杂度是行不通的。必须做到近似于\(mathcal{O}(r)\)的时间复杂度。观察题......