线段树简单应用:https://codeforces.com/problemset/problem/1070/C

65 阅读 0 评论 43 点赞

我是靠谱客的博主优美电脑，最近开发中收集的这篇文章主要介绍线段树简单应用:https://codeforces.com/problemset/problem/1070/C，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

嗯~

自己的能力算是有一点提高了吧，之前的自己就连G[start].push({xxx,1});G[end+1].push({xxx,-1})这种东西都不会

写这个博客算是记录下自己学到的两个东西，

1.动态地求数量

妈耶，m(1~2e5)个可选的计划，我难道要把每个计划都刷一遍，然后用它来[start,end]中的每一个点？不存在的，

这种时候应该维护好一个数据结构，到了start或者end+1的地方，对这个数据结构进行修改。

边修改边查询。这种动态的方法很有效，通过动态的边修改边查询，可以方便的计算

$sum_{i=1}^{n} ( sum_{j=1}^{i-1} f(i,j))$ 这种区间的计数问题，具体一点的可以看这道题和我的这发提交

2.线段树的简单应用

线段树有三好:~~轻声体柔易推倒~~

咳咳，不对，我先谈谈不用线段树为什么不能过

在这题中，我开始想的简单了，以为数据结构用个set,插入logn，查询n(从低价到高价找到k个服务器)就行，但是当可选的服务器提供商非常多,每个提供的服务器数量少，而且我又要很多服务器怎么办？如果这样做，就会一个提供商要一个，总共就是On,那以共要m次，结果就是O(mn)，所以就无情地T了

于是要优化，怎么优化，看一下数据范围，修改m(1~2e5)次，查询m(1~2e5)次，修改次数和查询次数差不多，数据范围额额，看拿什么当数据吧

但总而言之修改和查询地复杂度应该都在100,考虑到2e5,因该也就是log(2e5 or 1e6)左右吧，不然会T，那用线段树怎么回事呢

设数据结构内的数据为P,那么我们的修改操作是:P内增加cnt(1e6)个price(1e6);查询操作:P内最小的k(1e6)个数的和是多少

用线段树，数据范围=maxn=1e6，修改和查询都是20的复杂度，可以接受，

于是:我需要单点修改(cnt个price),我需要区间查询(最小的k个数的和)，查询次数和修改次数差不多的，那肯定就要选择线段树了

线段树适用: 单点/区间修改，区间查询

扯个题外话，把计划的开始和结束都安排在时间轴上，线段树在计算i的相关东西时，只能计算在i之前发生的事对i产生的影响(先前的计划开始，先前的计划结束),不能计划未来的(我怎么知道接下来会有哪些东西要发生)。

如果要考虑到未来的东西，就要用到主席树？？(查询[le,ri]区间以获取[le,ri]区间内事件的影响)

划重点了！！这次线段树简单应用的核心代码:

//[e[o].l,e[o].r]的[l,r] 中找到前num个的和
ll query(ll o, ll l, ll r, ll num)//不保证e[o].sum>=num e[o].l=l 
{
	if (e[o].sum == num)return e[o].c;
	if (e[o].l == e[o].r)return 1ll * e[o].l * min(e[o].sum, 1ll * num);//没有，省一点
	PushDown(o);
	PushUp(o);
	ll mid = (e[o].l + e[o].r) >> 1;
	if (e[ls].sum >= num)
		return query(ls, l, mid, num);
	else
		return e[ls].c + query(rs, mid + 1, r, num - e[ls].sum);
}