2021-10-03权值线段树（二）

入门篇权值线段树（一）

关于权值线段树又看了一些题目，更加确信这个东西只是在建模方面进行了思维加深，由于其常与二维偏序问题结合才被单独赋予概念。

本篇主讲三道题

权值线段树的常见操作（平衡树？）

1. 第K大值
   写一个线段树，维护可重集合中的第K大值
   思路是不难想的，每个区间的信息是当前区间内的数字个数，这样一来，对于当前节点，就可以根据左区间的数字个数来确定第K大值是在左区间还是又区间了，最后到叶子节点时就OK了。
   代码就不搞了。
   还是感觉这玩意和平衡树好像，，，

偏序类问题

2. CF1311F Moving Points
   题目大意：在一个一维坐标轴上给定$n$个点的初始坐标$x1,x2,x3,x4\dots \dots xn$，每个点有一个初速度$v1,v2,v3,v4\dots \dots vn$，所有点同时开始向右移动，问所有点两两之间的最短距离和是多少。

首先什么是偏序问题
其实上一篇中的逆序对问题就是偏序问题了，在数学中，可以认为偏序是全序的子集，事实上初学者暂时无需关心什么是偏序，只需知道应用场合即可。
最好理解的地方就是坐标系。

我们看到，在坐标系上散落着许多点，每个点有坐标$(X,Y)$现在我们要求计算每个点左下方的点数（当然也可以左上方），有同学可能会说二维前缀和就OK了，确实，但有没有更快的方法呢？
这里我们将所有点按照$X$排序，这样一来，就做到了从左到右遍历，然后遍历地同时在线地将每个点$Y$值存入线段树（或树状数组），这样一来，当来到$Xi$点时，就变成了求$1\to Yi$共有多少个点了，这一过程利用数据结构维护做到$nlon$，而这就是偏序思想，我们将逆序对问题的位置看成x轴，数值看成y轴，是不是一样呢？
这种两个维度的数据，将其中一维排序后维护另一维并用数据结构计数的思维便是所谓的二维偏序，所以并不是新算法，主要还是在于建模，对应的还有其他模型，常见的就是（时间+数值），（位置+数值），（位置+位置）等。

回到这道题，这题还是颇具CF风格的，首先有个结论：对于$i$和$j$两点，如果$xi<xj$且$vi>vj$，那么早晚会相遇，最短距离为0；否则，距离要么不变（速度相同），要么越拉越大，所以一开始的距离就是最短距离。
这样一来，我们将$x$看成$x轴$，$v$看成$y$轴，不是变成了按照x排序，求左下方所有点与当前点最短距离和，显然，需要两个信息，第一是左下方的点数，第二是距离和，所以需要两个数据结构，具体可以借助前缀和思想进行计数，维护$[1,vi]$间所有点到0点的距离和$M$，再开一个线段树维护$[1,vi]$间所有点的数量$n$，则当前点能提供的贡献为$n\ast xi-M$。代码时间关系以后补上：

补充一点偏序的概念，偏序的科学描述虽然很复杂，但感性理解其实很简单，我们知道对于一维数据的集合如{3，6，2，5，4}，任何两个数字都能比较大小关系，这叫全序，但是在二维情况下{(3,2),(4,6),(2,5),(3,8)}，我们可以规定当$xi<xj$且$yi<yj$时，点$i<$点$j$，但是仍有其他情况是无法比较大小的，这叫偏序，偏序的一些问题在非线性结构中有所体现，有时也会结合一些拓扑的思维，往上也能扩展到三位偏序，但在信息学中主要还是侧重于问题建模。

权值线段树与动态开点的结合
3. 回转寿司
题意：给定一个整数序列，与$L$，$R$，求满足总和在$[L,R]$之间的连续子序列的个数。
$N\le 10^5$
$|a_i|\le 10^5$
$0\le L,R\le 10^9$

首先整理二维偏序模型，关键信息是区间和，所以考虑前缀和，对于$sumi$，需存在$sumj$满足$L<=sumi-sumj<=R$，所以如果维护一下前缀和就变成区间查询问题了。
我们按照从左到右遍历$sumi$，一边遍历一边查找到目前为止满足的$sumj$有多少个，为了看得清楚，我们将公式变形一下：$sumi-L>=sumj>=sumi-R$，即查询$[sumi-R,sumi-L]$之间有多少个$sumj$符合条件。
但是一看数据，达到$10^9$，还没算上前缀和的累加，直接开线段树必炸，闲着无聊试了一发有40分，，，
考虑到线段树上很多点虽然建在那里，但其实无论修改还是查询却都用不到，可线段树的常规写法必须依靠左儿子=当前*2，右儿子=当前*2+1这类线性关系，所以导致了空间必须事先开够，那有没有办法像链表一样需要的时候再去建点，把好钢用在刀刃上呢，那就是动态开点。
其实跟链表的思维是一样的，就是事先要一批链表节点，然后一边跑修改，一边按需分配（不过在写的时候通常会用"&"符号进行传值引用方便操作，这里不细讲，不过虽然不用这样写也可以，但是确实会带来很大的方便，并且在如平衡树等动态建点的数据结构中都有用到，还是建议好好摸透原理）。

#include<cstdio>
#define maxn 100039
using namespace std;
typedef long long ll;
int N, L, R;
int a[maxn];
ll sum[maxn];
struct FLY{
	int v, nexl, nexr;
	ll l, r; 
}node[3000039];
int K = 1;
//void up(int u){node[u].v = (node[u].nexl!=0?node[node[u].nexl].v:0)+(node[u].nexr!=0?node[node[u].nexr].v:0);}
void up(int u){node[u].v = node[node[u].nexl].v+node[node[u].nexr].v;}
int update(int &u, ll L, ll l, ll r){
	if(!u){
		u = ++K;
		node[u].l = l, node[u].r = r;
	}
	if(l>=r)return node[u].v++, 0;
	ll m = l+(r-l)/2;
	if(L<=m)update(node[u].nexl, L, l, m);
	else update(node[u].nexr, L, m+1, r);
	up(u);
	return 0;
}
int quary(int u, ll L, ll R){
	if(!u)return 0;
	if(L<=node[u].l&&R>=node[u].r)return node[u].v;
	ll m = node[u].l+(node[u].r-node[u].l)/2;
	int sum = 0;
	if(L<=m)sum += quary(node[u].nexl, L, R);
	if(R>m)sum += quary(node[u].nexr, L, R);
	return sum;
}
ll ans;
int main(){
	freopen("test.in", "r", stdin);
	freopen("test.out", "w", stdout);
	scanf("%d%d%d", &N, &L, &R);
	node[1].l = -1e10, node[1].r = 1e10;
	int f = 1;
	update(f, 0, node[1].l, node[1].r);
	for(int i = 1; i < N+1; i++){
		scanf("%d", a+i);
		sum[i] = sum[i-1] + a[i];
		ans += quary(1, sum[i]-R, sum[i]-L);
		update(f, sum[i], node[1].l, node[1].r);
	}
	printf("%lld", ans);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52