首页 > 其他分享 >楼房重建线段树

楼房重建线段树

时间:2024-02-07 10:55:42浏览次数:31  
标签:val int 楼房 线段 tr lim define 最大值 重建

维护前缀最大值个数。

pushup 操作进行修改。

定义 solve(x, lim) 为前面这个区间的最大值为 lim,\(x\) 支配的区间产生的贡献。

如果 \(x\) 的最大值已经小于 \(lim\),显然没有贡献。

考虑 \(x\) 的左儿子,如果左儿子的最大值大于 \(lim\) 直接递归左二子查询,此时右儿子的答案不受影响。

如果左儿子最大值小于 \(lim\) 的话,贡献显然为0,递归右儿子查询。

\(solve\) 每次只会递归一个儿子,一共 \(O(\log n)\) 层,复杂度 \(O(\log n)\)。

总复杂度 \(O(n\log ^ 2 n)\)。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 5, INF = 0x3f3f3f3f;
const LL mod = 998244353;

int n, m;

struct Segment_Tree {
	struct Node {
		int l, r, val;
		double maxv;
		#define l(x) tr[x].l
		#define r(x) tr[x].r
		#define val(x) tr[x].val
		#define mx(x) tr[x].maxv
	} tr[N << 2];

	void build(int l, int r, int x) {
		tr[x] = {l, r};
		if (l == r) return;
		int mid = (l + r) / 2;
		build(l, mid, x * 2), build(mid + 1, r, x * 2 + 1);
	}

	int solve(int x, double lim) {
		if (mx(x) <= lim) return 0;
		if (l(x) == r(x)) return 1;
		if (mx(x * 2) <= lim) return solve(x * 2 + 1, lim);
		else return solve(x * 2, lim) + val(x) - val(x * 2);
	}

	void pushup(int x) {
		mx(x) = max(mx(x * 2), mx(x * 2 + 1));
		val(x) = val(x * 2) + solve(x * 2 + 1, mx(x * 2));
	}

	void update(int p, int x, double v) {
		if (l(x) == r(x)) {
			mx(x) = v;
			val(x) = 1;
			return;
		}
		int mid = (l(x) + r(x)) / 2;
		if (p <= mid) update(p, x * 2, v);
		else update(p, x * 2 + 1, v);
		pushup(x);
	}

} SegT;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m;
    SegT.build(1, n, 1);

    for (int i = 1; i <= m; i ++) {
    	int x, y;
    	cin >> x >> y;
    	SegT.update(x, 1, (double)y / x);
    	cout << SegT.val(1) << '\n';
    }

    return 0;
}

标签:val,int,楼房,线段,tr,lim,define,最大值,重建
From: https://www.cnblogs.com/Svemit/p/18010738

相关文章

  • P6025 线段树 题解
    解题思路暴力做法从\(l\)到\(r\)枚举每一个数,然后建线段树,记录最大下标,然后计算答案。代码略。时间\(O(n^2)\),期望得分:\(10\)分。优化暴力我们考虑每次枚举不遍历整棵线段树。显然,贪心的,最深的最右边的节点编号最大。那么我们可以发现,如果两颗子树大小相同,那么最大节......
  • P10145 [WC/CTS2024] 线段树 题解
    Link纪念一下场切题。题意:给定一棵(分点不一定为中点)的线段树,给定若干个询问区间,问有多少个线段树上结点的集合,知道了这些结点对应的区间和就可以知道任何一个询问区间的和。从询问区间开始考虑。会发现可以把所有\(a_i\)分成若干个集合,只要知道每个集合的和就可以知道所有询......
  • 洛谷 P10145 [WC/CTS2024] 线段树 题解--zhengjun
    提供一种考场做法,在思路上和官方题解的差异蛮大的,虽然结果差不多。首先需要发现\([l,r)\)区间可以算出来的充要条件是:如果对于每个选中的节点\(u\),连无向边\((L_u,R_u)\),则当且仅当\(l\)和\(r\)连通时区间\([l,r)\)可以算出来。证明的话,用前缀和理解这些东西,分别考虑......
  • 线段树二分——nc2.4多校_G.新春漫步
    目录问题概述思路分析参考代码做题反思问题概述原题参考G.新春漫步坐标轴上有n个点,初始时每个位置上都有一个坚固程度为a1的障碍物,接下来有m次操作1.将位置p上的障碍物的坚固程度减去x,若减去x后坚固程度小于等于0,则该障碍物消失2.询问一个人从p的位置向右走,最多能走到什么位......
  • CF522D Closest Equals 离线扫描 + 线段树
    CF522DClosestEquals题意:m个询问,求[l,r]内相同元素的最小距离。离线询问,按右端点排序。对于每一个a[i],如果last[a[i]]存在,将线段树last[a[i]]的位置改为i-last[a[i]]。查询区间最小值。当然这题也可以回滚莫队。注:本题一路从黑题堕落到绿题#include<bits/stdc......
  • 2022CCPC女生赛-L.彩色的树(线段树合并)
     链接Problem-L-Codeforces以前迷迷糊糊用dsuontree写的题目但是其实没搞明白现在换一种写(太菜了还是没搞明白dsuontree)题意:给你一棵树,询问给定询问的节点上,子树内距离小于等于k的节点不同颜色的种类有多少个。k是固定的值。解法:本题做法为比较板子的线段树合并,......
  • 【模板】 与等差数列结合的线段树
    题面代码点击查看代码#include<bits/stdc++.h>usingnamespacestd;#defineIOSios::sync_with_stdio(0);cin.tie(0);cout.tie(0);#definerep(i,a,n)for(inti=a;i<=n;i++)#defineper(i,a,n)for(inti=n;i>=a;i--)#definefifirst#definesesecond#defin......
  • [算法学习笔记01]线段树
    #[算法学习笔记01]线段树###每日蒟蒻小故事(1/1)蒟蒻刚刚升到S组,发现S组正在学习线段树Ⅲ.蒟蒻并不知道什么是线段树.蒟蒻十分害怕,向大佬询问什么是线段树.大佬邪魅一笑,并未解释.于是可怜的蒟蒻什么也听不懂,只得在洛谷和OIWIKI上自学线段树.“所以什么是线段树?”###什么......
  • 线段树合集
    线段树合集线段树:https://oi-wiki.org/ds/seg/扫描线:https://oi-wiki.org/geometry/scanning/orhttps://zhuanlan.zhihu.com/p/103616664orhttps://www.cnblogs.com/Rakan-LoveJ/p/11401851.html标记永久化:https://www.cnblogs.com/wozaixuexi/p/9462461.html李超线段树:ht......
  • 代码随想录 day35 柠檬水找零 根据身高重建队列 用最少数量的箭引爆气球
    柠檬水找零就根据几种条件列出来找零情况就行生活经验可知找零当然先给大面额的利于后面的找零根据身高重建队列这题感觉就是先做过队列给糖也难以有思路这里是先按身高先排好队一样身高就k小的排在前面然后再按他前面有几个人直接就给他插到第几个位置就行用最少......