前言

最近cf在疯狂掉分，真受不了了……

一、线段树的离散化——掉落的方块

class Solution {
public:

    //辅助数组
    vector<int>edges;
    
    //线段树
    vector<int>mx;
    //懒信息
    vector<int>info;
    //是否更新过
    vector<bool>update;

    vector<int> fallingSquares(vector<vector<int>>& positions) {
        int n=positions.size();

        //注意！！每个positions有两个信息，要在四倍的基础上再开双倍！！
        edges.resize(n<<2);
        mx.resize(n<<3);
        info.resize(n<<3);
        update.resize(n<<3);

        //设置数组height表示数轴上每个点当前的高度
        //所以每次方块下落都是范围查询最大值和范围重置操作
        //每次返回整个范围上的最大值
        
        //因为数轴上是点坐标，所以考虑将区间转化成左闭右开
        //由于数轴的范围非常大，所以要考虑对其进行离散化
        //方法是对所有边界排序，将数值转化成排名

        int len=collect(positions);

        build(1,len,1);

        vector<int>ans;
        int Max=0;
        for(int i=0,l,r,h;i<n;i++)
        {
            //左右边界的排名
            l=rank(len,positions[i][0]);
            r=rank(len,positions[i][0]+positions[i][1]-1);
            //查询当前落下后的高度
            h=query(l,r,1,len,1)+positions[i][1];
            //更新最大值
            Max=max(Max,h);
            ans.push_back(Max);
            change(l,r,h,1,len,1);
        }
        return ans;
    }

    //离散化
    int collect(vector<vector<int>>&positions)
    {
        int sz=1;
        for(int i=0;i<positions.size();i++)
        {
            edges[sz++]=positions[i][0];
            edges[sz++]=positions[i][0]+positions[i][1]-1;//线段树里的右边界 -> 开区间减一
        }
        //排序
        sort(edges.begin()+1,edges.begin()+sz);
        //去重
        int len=1;
        for(int i=2;i<sz;i++)
        {
            if(edges[len]!=edges[i])
            {
                edges[++len]=edges[i];
            }
        }
        return len;
    }

    //二分搜索排名
    int rank(int n,int v)
    {
        int l=1;
        int r=n;
        int m;
        int ans=0;
        while(l<=r)
        {
            m=(l+r)/2;
            if(edges[m]>=v)
            {
                ans=m;
                r=m-1;
            }
            else
            {
                l=m+1;
            }
        }
        return ans;
    }

    //构建线段树
    void build(int l,int r,int i)
    {
        if(l<r)
        {
            int m=(l+r)>>1;
            build(l,m,i<<1);
            build(m+1,r,i<<1|1);
        }
        //初始全为0
        mx[i]=0;
        info[i]=0;
        update[i]=false;
    }

    //懒更新
    void lazy(int i,int v)
    {
        mx[i]=v;
        info[i]=v;
        update[i]=true;
    }

    //汇总
    void up(int i)
    {
        mx[i]=max(mx[i<<1],mx[i<<1|1]);
    }

    //下发
    void down(int i)
    {
        if(update[i])
        {
            lazy(i<<1,info[i]);
            lazy(i<<1|1,info[i]);
            update[i]=false;
        }
    }

    //范围重置
    void change(int jobl,int jobr,int jobv,int l,int r,int i)
    {
        if(jobl<=l&&r<=jobr)
        {
            lazy(i,jobv);
        }
        else
        {
            int m=(l+r)>>1;
            down(i);
            if(jobl<=m)
            {
                change(jobl,jobr,jobv,l,m,i<<1);
            }
            if(m+1<=jobr)
            {
                change(jobl,jobr,jobv,m+1,r,i<<1|1);
            }
            up(i);
        }
    }

    //范围查询
    int query(int jobl,int jobr,int l,int r,int i)
    {
        if(jobl<=l&&r<=jobr)
        {
            return mx[i];
        }
        else
        {
            int m=(l+r)>>1;
            down(i);
            int ans=0;
            if(jobl<=m)
            {
                ans=max(ans,query(jobl,jobr,l,m,i<<1));
            }
            if(m+1<=jobr)
            {
                ans=max(ans,query(jobl,jobr,m+1,r,i<<1|1));
            }
            return ans;
        }
    }
};

这个题其实思路不难想，就是用数组表示每个点上当前的高度，那么就可以考虑线段树去维护区间内的最大值，所以每次方块下落就是去查落下区间的最大值，然后直接进行区间重置操作即可。需要注意的是，因为数轴上是点坐标，所以可以考虑将下落区间看作左闭右开，防止两方块在同一个点上重叠。

跟之前的题一样，因为是用数组表示坐标，而坐标的范围非常大，所以要考虑对其进行离散化。所以collect就是在对数组进行排序并去重，之后和之前离散化的方法一样，去二分搜索排名，然后根据这个排名去构建线段树，这样就把数组长度从跟坐标轴的长度相关转化为和方块数相关了。

需要注意的是，每个position里有两个坐标，所以线段树要在四倍的基础上再开双倍，因为这个报错了好多次。

思路是不难，但代码是真难写，一不小心就报错了……

二、线段树的二分搜索——Vases and Flowers

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll>pll;

const int MAXN=50001+5;

//线段树
vector<int>sum(MAXN<<2);
//懒信息 -> 重置
vector<int>info(MAXN<<2);
//是否更新
vector<bool>update(MAXN<<2);

//懒更新
void lazy(int i,int v,int n)
{
    sum[i]=v*n;
    info[i]=v;
    update[i]=true;
}

//汇总
void up(int i)
{
    sum[i]=sum[i<<1]+sum[i<<1|1];
}

//下发懒信息
void down(int i,int ln,int rn)
{
    if(update[i])
    {
        lazy(i<<1,info[i],ln);
        lazy(i<<1|1,info[i],rn);
        update[i]=false;
    }
}

//构建线段树
void build(int l,int r,int i)
{
    if(l<r)
    {
        int m=(l+r)>>1;
        build(l,m,i<<1);
        build(m+1,r,i<<1|1);
    }
    sum[i]=0;
    info[i]=0;
    update[i]=false;
}

//范围重置
void change(int jobl,int jobr,int jobv,int l,int r,int i)
{
    if(jobl<=l&&r<=jobr)
    {
        lazy(i,jobv,r-l+1);
    }
    else
    {
        int m=(l+r)>>1;

        down(i,m-l+1,r-m);

        if(jobl<=m)
        {
            change(jobl,jobr,jobv,l,m,i<<1);
        }
        if(m+1<=jobr)
        {
            change(jobl,jobr,jobv,m+1,r,i<<1|1);
        }

        up(i);
    }
}

//范围查询
int query(int jobl,int jobr,int l,int r,int i)
{
    if(jobl<=l&&r<=jobr)
    {
        return sum[i];
    }

    int m=(l+r)>>1;

    down(i,m-l+1,r-m);

    int ans=0;
    if(jobl<=m)
    {
        ans+=query(jobl,jobr,l,m,i<<1);
    }
    if(m+1<=jobr)
    {
        ans+=query(jobl,jobr,m+1,r,i<<1|1);
    }
    return ans;
}

//二分找从from到最后第k个0的位置
int findZero(int s,int n,int k)
{
    int l=s;
    int r=n;
    int m;
    int ans=0;
    while(l<=r)
    {
        m=(l+r)>>1;

        //如果[s,m]范围上0的个数大于等于k
        //那就去左侧二分
        if(m-s+1-query(s,m,1,n,1)>=k)
        {
            ans=m;
            r=m-1;
        }
        else
        {
            l=m+1;
        }
    }

    return ans;
}

//插入
vector<int> insert(int from,int flowers,int n)
{
    int start,end;
    //范围上0的个数 -> 能插的位置数
    int zeros=n-from+1-query(from,n,1,n,1);

    //一个也插不了
    if(zeros==0)
    {
        return {-1,-1};
    }

    //第一个0出现的位置
    start=findZero(from,n,1);
    //最后一个0出现的位置
    end=findZero(from,n,min(zeros,flowers));
    //插花
    change(start,end,1,1,n,1);

    return {start-1,end-1};
}

//清理
int clear(int l,int r,int n)
{
    //区间内的累加和 -> 1的个数
    int ans=query(l,r,1,n,1);

    //清空
    change(l,r,0,1,n,1);

    return ans;
}

void solve()
{
    int n,m;
    cin>>n>>m;

    build(1,n,1);

    int type;
    while(m--)
    {
        cin>>type;

        if(type==1)
        {
            int a,f;
            cin>>a>>f;

            //0出现的最左和最右位置
            vector<int> lr=insert(a+1,f,n);
            
            //全被插满了
            if(lr[0]==-1)
            {
                cout<<"Can not put any one."<<endl;
            }
            else
            {
                cout<<lr[0]<<" "<<lr[1]<<endl;
            }
        }
        else
        {
            int a,b;
            cin>>a>>b;

            cout<<clear(a+1,b+1,n)<<endl;
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    cin>>t;
    while(t--)
    {
        solve();    
    }
    return 0;
}

这个题就要用到线段树上的二分搜索了。

首先，整体思路是用1表示这个花瓶里有花，0表示没花。所以清空操作就是先求范围上的累加和，即1的个数，再将整个范围重置为0。

但对于插花操作，需要每次给出范围内0的具体位置，所以可以考虑二分搜索从某个位置开始到最后第k个0的位置。方法是，每次求一下范围内的累加和，如果范围上花瓶的个数减去累加和大于等于k，表示这个范围上0的个数大于等于k，所以之后就再去这个范围二分。那么插花操作可以先求一下范围内0的个数，即区间长度减去范围累加和。若0的个数为0，说明一朵花也没法插，那么就直接返回两个-1表示没法插。否则就分别查一下范围上第一个0出现的位置start和最后一个0出现的位置end，然后把从start到end范围上的数全重置成1即可。注意查最后一个0出现的位置时，第k个0的k要取0的个数和插花数量的最小值。

三、线段树的特别修改

1.上帝造题的七分钟 2 / 花神游历各国

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll>pll;

const int MAXN=1e5+5;

//范围修改的前提是要保证在进行了某个修改操作后
//可以在O(1)的时间内把要维护的信息加工出来
//而开平方的操作无法在O(1)时间内将累加和加工出来

//观察可以发现，数值最大就是10^12
//所以开根号最多开6次就到1了，之后不管开几次根号结果都是1
//所以考虑同时用线段树维护最大值
//每次暴力扎到叶节点执行开平方操作
//若范围上有n个数，树高为h，那么时间复杂度就是O(n*h)
//当范围上的最大值为1，即所有数字均为1
//那么这个范围就再也不用去了

//所以若数组长度为n，树高为h
//因为每个叶节点最多来6次
//所以时间复杂度最多就是O(n*6*h)，即O(n*6*logn)
//即使有再多的query和sqrt的操作
//时间复杂度最多就是O(n*6*logn)
//此时称势能为n*6*logn


//原始数组
vector<ll>arr(MAXN);
//累加和
vector<ll>sum(MAXN<<2);
//最大值
vector<ll>mx(MAXN<<2);

//汇总
void up(int i)
{
    sum[i]=sum[i<<1]+sum[i<<1|1];
    mx[i]=max(mx[i<<1],mx[i<<1|1]);
}

//构建线段树
void build(int l,int r,int i)
{
    if(l==r)
    {
        sum[i]=arr[l];
        mx[i]=arr[l];
    }
    else
    {
        int m=(l+r)>>1;

        build(l,m,i<<1);
        build(m+1,r,i<<1|1);

        up(i);
    }
}

//开根号
void sqrt(int jobl,int jobr,int l,int r,int i)
{
    //扎到了根节点
    if(l==r)
    {
        ll ans=(ll)sqrt(mx[i]);
        sum[i]=ans;
        mx[i]=ans;
    }
    else
    {
        int m=(l+r)>>1;

        //有数且最大值大于1 -> 可以执行开根号的操作 
        if(jobl<=m&&mx[i<<1]>1)
        {
            sqrt(jobl,jobr,l,m,i<<1);
        }
        if(m+1<=jobr&&mx[i<<1|1]>1)
        {
            sqrt(jobl,jobr,m+1,r,i<<1|1);
        }

        up(i);
    }
}

//查询
ll query(int jobl,int jobr,int l,int r,int i)
{
    if(jobl<=l&&r<=jobr)
    {
        return sum[i];
    }

    int m=(l+r)>>1;

    ll ans=0;
    if(jobl<=m)
    {
        ans+=query(jobl,jobr,l,m,i<<1);
    }
    if(m+1<=jobr)
    {
        ans+=query(jobl,jobr,m+1,r,i<<1|1);
    }

    return ans;
}

void solve()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>arr[i];
    }

    build(1,n,1);

    int m;
    cin>>m;

    int type;
    while(m--)
    {
        cin>>type;

        int l,r;
        cin>>l>>r;

        if(l>r)
        {
            swap(l,r);
        }

        if(type==0)
        {
            sqrt(l,r,1,n,1);
        }
        else
        {
            cout<<query(l,r,1,n,1)<<endl;
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--)
    {
        solve();    
    }
    return 0;
}

这个题就牵扯到线段树一个很重要的技巧——势能分析了。

在之前的博客里提到过，如果线段树的范围修改功能想要做到O(logn)，那么就必须保证当在某个范围上统一进行了某种修改操作，可以用O(1)的时间把这个范围上要维护的信息加工出来。而在这个题里，对一个范围进行了开平方操作后没法在O(1)的时间里把累加和信息加工出来。但是观察一下就能发现，虽然数列里的数有10^12这么大，但对其开平方的话最多开六次就到1了，那么之后无论开多少次平方结果都会维持在1不变。所以可以考虑设置一个剪枝操作，用线段树再维护一个范围最大值信息。如果范围上的最大值是1，那么就没必要进行开平方操作了，直接返回即可。此时，就可以考虑每次暴力扎到最底层执行开平方操作。假如树高为h，那么此时就称扎到一个叶节点的势能为h。若单次要操作的数有n个，那么势能就是n*h。又因为每个数最多就开六次平方，即每个叶节点最多来六次，所以整体的势能就是6*n*logn。所以，因为有了剪枝操作，那么无论有多少次开平方操作，时间复杂度最多就是O(n*logn)。

之后唯一不同的就是开平方的sqrt函数，那么就是只有扎到叶节点时才暴力开平方，中间每次都判断一下范围最大值是否大于1即可。

2.D. The Child and Sequence

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll>pll;

const int MAXN=1e5+5;

//取模操作无法懒更新，所以需要进行势能分析
//对于一个数x，若模上的数mod比x大，那么就不需要进行操作
//若mod比x小，那么x会随着不断取模逐渐变小直到1，之后就再也不用取模了
//所以存在一个结论：数x模上一个比自己小的数，结果最大都不到x的一半
//所以一个数一共最多能取模的次数为logx

//同样设置max维护最大值，若max小于mod那就不用去了
//所以总的势能就是n*logv*logn
//对于每个单点增加操作
//增加的势能为logv*logn，是可以接受的

//原数组
vector<ll>arr(MAXN);
//累加和
vector<ll>sum(MAXN<<2);
//最大值
vector<ll>mx(MAXN<<2);

//汇总
void up(int i)
{
    sum[i]=sum[i<<1]+sum[i<<1|1];
    mx[i]=max(mx[i<<1],mx[i<<1|1]);
}

//构建
void build(int l,int r,int i)
{
    if(l==r)
    {
        sum[i]=arr[l];
        mx[i]=arr[l];
    }
    else
    {
        int m=(l+r)>>1;

        build(l,m,i<<1);
        build(m+1,r,i<<1|1);

        up(i);
    }
}

//查询累加和
ll query(int jobl,int jobr,int l,int r,int i)
{
    if(jobl<=l&&r<=jobr)
    {
        return sum[i];
    }

    int m=(l+r)>>1;

    ll ans=0;
    if(jobl<=m)
    {
        ans+=query(jobl,jobr,l,m,i<<1);
    }
    if(m+1<=jobr)
    {
        ans+=query(jobl,jobr,m+1,r,i<<1|1);
    }

    return ans;
}

//范围取模
void mod(int jobl,int jobr,int jobv,int l,int r,int i)
{
    //mod比范围最大值还大 -> 不去了
    if(jobv>mx[i])
    {
        return;
    }

    //单点取模
    if(l==r)
    {
        sum[i]%=jobv;
        mx[i]%=jobv;
    }
    else
    {
        int m=(l+r)>>1;

        if(jobl<=m)
        {
            mod(jobl,jobr,jobv,l,m,i<<1);
        }
        if(m+1<=jobr)
        {
            mod(jobl,jobr,jobv,m+1,r,i<<1|1);
        }

        up(i);
    }
}

//单点修改
void change(int jobi,ll jobv,int l,int r,int i)
{
    if(l==r)
    {
        sum[i]=jobv;
        mx[i]=jobv;
    }
    else
    {
        int m=(l+r)>>1;

        if(jobi<=m)
        {
            change(jobi,jobv,l,m,i<<1);
        }
        else//只可能去一边
        {
            change(jobi,jobv,m+1,r,i<<1|1);
        }

        up(i);
    }
}

void solve()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>arr[i];
    }

    build(1,n,1);

    int type;
    while(m--)
    {
        cin>>type;

        if(type==1)
        {
            int l,r;
            cin>>l>>r;

            cout<<query(l,r,1,n,1)<<endl;
        }
        else if(type==2)
        {
            int l,r,x;
            cin>>l>>r>>x;

            mod(l,r,x,1,n,1);
        }
        else
        {
            int k,x;
            cin>>k>>x;

            change(k,x,1,n,1);
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--)
    {
        solve();    
    }
    return 0;
}

和上个题一样，取模操作后同样无法在O(1)的时间里加工出累加和信息，所以同样需要进行势能分析。观察可以发现，对于一个数x，若取模的数mod比x大的话，那结果肯定还是x不会变。而若取模的数比x小的话，打个表可以发现结果最大都不超过x的一半。而当x最小变为1后就永远不需要进行取模操作了，所以一个数最多就能进行logx次操作。所以和上个题类似，同样用线段树再维护一个范围最大值信息，若范围最大值小于mod就不用去了，所以整体势能就是n*logv*logn。此外，对于单点增加操作，增加的势能是logv*logn，是可以接受的。

所以，单点修改就是直接扎到叶节点修改即可。范围取模就是每次判断一下范围最大值，如果比取模的数mod小，那就直接返回不用去了，否则就一直扎到叶节点修改即可。

3.贴海报

这tm是绿题？？！

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll>pll;

const int MAXM=1e3+5;

//假如有三张海报，范围分别是[3,12][3,5][10,12]
//如果对其离散化，那么3,5,10,12会对应1,2,3,4
//但此时如果查[1,4]范围的数量，第一张[3,12]的海报会被忽略
//所以考虑在离散化时，如果两数之间相差大于1，那么就在中间添一个数
//所以就是3,4,5,6,10,11,12就对应1,2,3,4,5,6,7
//此时因为多添了一个6，就不会漏掉答案了

//范围上海报数量的这个信息，无法用线段树维护
//因为大范围上的信息没法由子范围得到
//所以考虑用线段树维护某个范围上是否被设置成同一张海报

//左边界
vector<int>pl(MAXM);
//右边界
vector<int>pr(MAXM);
//离散化后的数组 -> 一次有两边界，最多每次都补 -> 四倍
vector<int>nums(MAXM<<2);
//线段树 -> 范围上是否被同一海报覆盖，是的话被几号海报覆盖
//离散化最多四倍，线段树要再多开四倍
vector<int>poster(MAXM<<4);
//最终统计
set<int>s;

//下发，不需要信息汇总
void down(int i)
{
    //被同一海报覆盖
    if(poster[i]!=0)
    {
        poster[i<<1]=poster[i];
        poster[i<<1|1]=poster[i];
        poster[i]=0;
    }
}

//构建线段树
void build(int l,int r,int i)
{
    if(l<r)
    {
        int m=(l+r)>>1;

        build(l,m,i<<1);
        build(m+1,r,i<<1|1);
    }
    poster[i]=0;
}

//贴海报
void change(int jobl,int jobr,int jobv,int l,int r,int i)
{
    if(jobl<=l&&r<=jobr)
    {
        poster[i]=jobv;
    }
    else
    {
        int m=(l+r)>>1;

        //下发
        down(i);

        if(jobl<=m)
        {
            change(jobl,jobr,jobv,l,m,i<<1);
        }
        if(m+1<=jobr)
        {
            change(jobl,jobr,jobv,m+1,r,i<<1|1);
        }
    }
}

//最后查询
void query(int jobl,int jobr,int l,int r,int i)
{
    //到了叶节点
    if(l==r)
    {
        //被覆盖了
        if(poster[i]!=0)
        {
            s.insert(poster[i]);
        }
    }
    else
    {
        int m=(l+r)>>1;

        down(i);

        if(jobl<=m)
        {
            query(jobl,jobr,l,m,i<<1);
        }
        if(m+1<=jobr)
        {
            query(jobl,jobr,m+1,r,i<<1|1);
        }
    }
}

//离散化
int collect(int sz)
{
    sort(nums.begin()+1,nums.begin()+sz+1);

    int len=1;
    //去重
    for(int i=2;i<=sz;i++)
    {
        if(nums[len]!=nums[i])
        {
            nums[++len]=nums[i];
        }
    }
    //补数字
    int cnt=len;
    for(int i=2;i<=len;i++)
    {
        if(nums[i-1]+1<nums[i])
        {
            nums[++cnt]=nums[i-1]+1;
        }
    }

    sort(nums.begin()+1,nums.begin()+cnt+1);

    return cnt;
}

//查排名
int rk(int l,int r,int v)
{
    int m;
    int ans=0;
    while(l<=r)
    {
        m=(l+r)>>1;

        if(nums[m]>=v)
        {
            ans=m;
            r=m-1;
        }
        else
        {
            l=m+1;
        }
    }
    return ans;
}

void solve()
{
    int n,m;
    cin>>n>>m;
    int sz=0;
    for(int i=1,l,r;i<=m;i++)
    {
        cin>>l>>r;
        pl[i]=l;
        pr[i]=r;
        nums[++sz]=l;
        nums[++sz]=r;
    }
    //存墙的边界 -> 后续查墙的排名
    nums[++sz]=n;

    //离散化
    int len=collect(sz);

    build(1,len,1);

    for(int i=1,jobl,jobr;i<=m;i++)
    {
        jobl=rk(1,len,pl[i]);
        jobr=rk(1,len,pr[i]);

        change(jobl,jobr,i,1,len,1);
    }

    //有可能存在贴出去的海报 -> 查整面墙范围[1,n]的数量
    query(1,rk(1,len,n),1,len,1);

    cout<<s.size()<<endl;
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--)
    {
        solve();    
    }
    return 0;
}

这个题是真的难，因为正常的离散化在这个题上不适用。举个例子，假如有三张海报，范围分别是[3,12]，[3,5]，[10,12]。如果对其进行正常的离散化，那么3,5,10,12会分别对应1,2,3,4。但此时如果要查[1,4]范围上的海报，那么只会查出有两张海报。最底层的海报正常来讲是会从[5,10]这里漏出来，但是因为离散化的原因所以被漏过去了。为了避免这种情况，就可以考虑在离散化时，若两数相隔大于1的话，就往中间插一个数，防止像这个例子一样被跳过。

但进一步观察可以发现，范围上海报数量的这个信息，根本无法用线段树维护。因为大范围上的问题根本无法由子范围得到，所以就需要转化一下维护的信息了。

这里，可以考虑用线段树去维护范围上是否被设置为同一张海报。

在这个例子中，当第一张海报来时，还是从头往下扎。当来到[3,4]和[5,6]范围上时，由于能被全包，所以这两个范围都被这一张海报覆盖，所以都设置为海报的序号。

之后，当第二张海报[1,3]来时，当扎到[1,2]时，由于被全包，所以设置为2。但来到[3,4]上时，此时由于该范围出现了两张不同的海报，所以就是先把信息往下传，然后把这个范围设置为0。

之后，当第三张海报来时，当扎到[5,8]时，由于被全包了，所以直接设置为3，同样叶节点4就被修改成3。

当所有的海报都统计完后，就让所有的信息沉底。如图所示，那么最终能看到的海报数就是所有叶节点上不同的编号数。

这个就体现出线段树题目的灵活了，在这个题里，只需要down方法，不需要up方法了，因为整个过程只牵扯到信息的下发。最后查询时，当扎到叶节点时，若标号不为0，即被海报覆盖了，那么就用一个set统计种数即可。注意collect函数里多了补数字的过程，还有因为会存在贴出去的海报，所以最后要查一下整面墙的范围。所以就要在初始化时要多存一下墙的边界，因为最后牵扯到查排名的操作。

总结

太难了，加油吧……

END