一个可以累死人的数据结构

线段树（仅限于基础的那个）（zx 树这种的以后再说）

线段树是一个神奇的数据结构，他基本上什么区间操作都可以优化

这里讲一些基本的操作：单点修改，区间查询，区间修改（延迟标记）

首先讲……概念…(我的线段树写的有的不一样，有的是用结构体存的左右节点，有的是在函数定义上存的节点)

线段树，顾名思义，一个树形结构，存储的每一个节点都是一个线段

线段树的根节点存储着区间 1-n 的总信息，2 号存 1-（1+n）/2。。。

每一个线段的子节点都是自己线段的两半，直到叶子结点 l==r

单点修改：

我们在进行单点修改的过程中，一般指令都是这个样子：c x y，表示操作 a[x]=y；

我们可以知道，线段树维护的是一条线段，只有叶子结点维护的是点，那么，我们首先应该递归到叶子结点，然后修改值，再向上修改父节点，就以区间和为例：

void change(int p,int l,int r,int x,int y)
{
    if(l==r&&l==x)
    {
        t[p]=y;
        return;
    }
    int mid=l+r>>1;
    if(x<=mid)change(p*2,l,mid,x,y);
    else change(p*2+1,mid+1,r,x,y);
    t[p]=t[p*2]+t[p*2+1];
}

区间查询

我们查询一个区间的时候，绝对不可能只是查询一个节点，基本上每一次都会查询到多个节点，那么我们应该怎么实现呢

操作 1：首先一个区间 l-r，我们可能需要查询的区间为 x1-x2,x2-x3,x3-x4

首先，如果我们递归到了当前的节点，这个节点的线段是被我们查询的这个区间所覆盖住的，我们直接把这个节点统计到答案之中，应为我们可以分成若干个线段树的节点，所以只要我们一直递归，就一定可以地轨道两个节点，l-x5,x6-r，这之间的所有节点都是被我们操作 1 所统计的，所以直接把这个答案返回。

如果不懂可以自己手模一遍

long long ask(int p,int l,int r,int x,int y){
    if(x<=l && y>=r) return t[p];
    spread(p);
    int mid=l+r>>1;
    long long ans=0;
    if(x<=mid) ans+=ask(p*2,x,y);
    if(y>mid) ans+=ask(p*2+1,x,y);
    return ans;
}

区间修改（懒标记 laztag）

这是一大难点啊。。。

首先对于我们上面的区间查询，我们可以感受到，线段树在对我们的区间进行一定的操作时，是可以划分为不同的节点进行操作的，那么，区间修改是否也可以这么做呢？

答案是肯定的

区间修改，在又一次经过操作 1 之后，我们就可以改变已经被覆盖的区间，比如区间和，我们就直接让这个区间增加 x*len(长度)，然后 return

可是这样并不满足我们的需要，因为区间修改的时候这样修改的确会直接将上面的数据进行修改，但是，我们如果多次操作，修改的次数一多，查询有交集的区间就会受影响，因此，我们引入懒标记：

懒标记是标记我们当前的节点需要进行区间修改，还是区间和为例，我们 laz[x]就代表着 x 节点的线段中每一个数都需要增加 laz[x]这么多，只要我们每一次在进行区间统计师，都将我们的父节点的 laztag 传下来，我们就知道，从最开始到现在，我们没、每一个节点总共需要至少增加多少(我说至少是因为当前节点的子节点(或者是子孙节点)可能 laztag 非零)

void spread(int p){
    if(t[p].add){
        t[p*2].pre+=t[p].add*(t[p*2].r-t[p*2].l+1);
        t[p*2+1].pre+=t[p].add*(t[p*2+1].r-t[p*2+1].l+1);
        t[p*2].add+=t[p].add;
        t[p*2+1].add+=t[p].add;
        t[p].add=0;
    }
}
void change(int p,int x,int y,int z){
    if(x<=t[p].l && y>=t[p].r){
        t[p].pre+=(long long)z*(t[p].r-t[p].l+1);
        t[p].add+=z;
        return;
    }
    spread(p);
    int mid=t[p].l+t[p].r>>1;
    if(x<=mid) change(p*2,x,y,z);
    if(y>mid) change(p*2+1,x,y,z);
    t[p].pre=t[p*2].pre+t[p*2+1].pre;
}

例题

这玩意的例题可多可难。。。这几个题我都至少调了有 2hours

P2471 降雨量题目链接

这道题真的不错(难调)

首先这道题需要进行分类讨论：

对于我们查询的区间(l,r)

我们先判断 false： 1.左端点年份确定了，右端点年份不确定，那我们的中间的最大值大于左端点（我们的定义应该是左端点的降雨量比右端点大并且右端点比一整个区间之内别的都大，所以中间最大值大于左端点就不成立） 2.右端点年份确定，左端点不确定，那么中间的最大值大于右端点，同样不成立 3.都确定了，左端点小于右端点

然后是 maybe： 1.年份不连续：右端点减去左端点和左右端点年分之差不相等 2.左端点不确定 3.右端点不确定

（由于我们已经切掉了 false 的情况，所以只剩下了 maybe 和 true，而有任何一个不确定都不可能是 true，所以。。。直接扔掉）

只要不是 FALSE 或者是 maybe 那就是 true

P5490 扫描线（也是 lyd 例题）题目链接

扫描线是一个非常经典的算法，可以用来求面积和，周长并等

以面积和为例：

我们放进坐标系中几个矩形，我们想要求出它们的面积和，第一可以想到用容斥原理，但他很慢。。。

我们考虑这么一件事情，我们假设有一条平行于纵轴的直线，他在随便移动。

对于我们矩形放在一起之后的形状，我们可以把这个图形分割成很多个小的没有交集的矩形

所以，我们可以把这条线进行左右移动，每次线和图形相交的地方是一定的，并且都是矩形，所以线的长度会有最多 2n 个，用这 2n 条线长度乘上横坐标的距离（矩形的宽度），就可以把我们的总面积求出来咯

有另一道题使用到了扫描线算法的（太累了不想写）
P1502 窗口的星星

P4198 楼房重建题目链接

这道题是真的。。。很好。。。

首先很容易想到的是每一个数我们可以通过求斜率来判断是否能看见这栋楼

我们考虑答案，就是 1-n 这个区间之内，求单增的斜率个数最长递增的斜率

因为我们的区间是固定的，我们可以通过将区间分为两半进行处理，就可以想到使用线段树

线段树中维护两个信息：区间最大值和区间单增斜率数量

build,pushdown 都不需要。。。但是 pushup 操作就很烦。。。

最大值的 pushup 是很简单的，两个区间的最大值嘛

可是单增斜率数量是个很棘手的东西:

我们设 lx 为我 pushup 进这个大区间里，必须大于的最小值

先说边界：

如果 l==r 那 numk[rt]=a[l]>lx;如果只有一个元素，那么我如果递归的原来区间的最左端是比它大于等于的，那 numk[rt]=0，否则等于 1（显然）

对于我需要 pushup 的区间，左半边区间可以直接 pushup 上去，没影响，右半边要考虑和左半边儿子的关系，lx 便是左区间的最大值
考虑右儿子的左右两个子区间：

设 s1 为左区间 s2 为右区间 1.如果 s1 的最大值小于等于 lx 直接舍去递归 s2 2.如果 s1 的最大值大于 lx 那么我的 s2 里原本看不看得见的

直接 pushup 上去就可以，然而右半区间的看得见的应该是 numk[rk]-num[rk_2]而不是 numk[rk_2+1]因为右半区间有的是不能上去的

撒花完结（终于**写完了）（怎么可能

update 2022.4.23 新的题目

P2824 [HEOI2016/TJOI2016]排序

这个题的套路非常好用

首先我们看到，如果在序列上直接排序十分麻烦……

我们考虑一个简化版：如果这个序列里只有0和1呢？

那么排序变得很简单对吧

如果……我们把原来这个序列转化成只有0和1呢？

soga！我们设定一个中间值，将比中间值大于等于的变成1，其他是0……

就可以进行排序了

然后我们就可以得知我们当前要求的这个部分与中间值的大小关系

那么……是不是很像二分！

我们二分这个中间值，最后二分的答案就是我们要求的东西！

P3722[AH2017/HNOI2017]影魔

好题！

我们考虑：如果一个区间是有贡献的，那么这个区间在什么时候回被统计到呢？

在一个左端点小于等于当前左端点，右端点大于等于当前右端点的区间会被统计到，那么……我们可以进行二维矩阵扫描线……

我们把一个坐标系的横轴设为区间的右端点，纵轴设为区间的左端点，那么我们对于每一个有贡献的区间都可以找到一个有贡献的矩阵

那么我们考虑怎么找到有贡献的区间……

首先对于一个符合第一种情况的区间来说，如果说在去掉两个端点的情况下，左右两个端点一定是剩下的区间的最大值左右两边第一个比它大的数字

然后，对于第二种情况来说就是最大值左边左端点右边这段区间作为当前区间的左端点，右端点作为当前区间的右端点，另一种情况同理（读者自行思考……我太懒了不想证明

反正就是求出来了，但是我们会发现，第二种情况区间个数太多了，但是都是连续的区间，那么我们就可以在扫描线上面做超级树状数组，就可以搞定了

P4513 小白逛公园

简单地说：区间最大子段和

我们会发现，一个区间的最大子段和，要不然是在左半边，要不然是在右半边，要不然是跨过中间

所以我们记录四个线段树（啊你没听错

一个记录区间最大前缀和，一个记录区间最大后缀和，一个记录区间最大子段和，另一个是区间和

合并显然（zrq讲课的时候课件上就是这么写的