学习笔记3：扫描线线段树的应用

前置知识：线段树

F - Apples (atcoder.jp)

分析：根据题意，我们知道需要维护一个大矩阵（一维是空间，一维是时间）中的一个固定大小区域（一维是盆的长度，一维是盆的耐久/时间）的最大值，初见时认为是二维前缀和，然而数据范围是2*1e5

我们设t[i]是苹果落下的时间，x[i]是苹果落下的地点，d是盆的耐久/时间，w是盆的长度

苹果会对脸盆可能的右端点的贡献范围（x[i],min(N,x[i]+w-1)），什么意思呢？通俗的来讲，你得把盆放在右端点在（x[i],min(N,x[i]+w-1)）里时，你才可能接到这个苹果。

这个时候没有考虑时间维度。我们考虑离线处理，先将数据预处理，这里用到了前缀和的思想。其实我们知道苹果对时间的贡献范围是（t[i],min(N,t[i]+d-1)），和右端点贡献范围同理，你需要在（t[i],min(N,t[i]+d-1)）放盆才有可能接到这个苹果,如果我们可以实现区间修改，那么就可以转换成

t[i]的时间节点+1，t[i]+d的时间节点-1（苹果只会影响到 t[i]+d-1 所以t[i]+d直接-1）

那么一个需要区间修改的维护区间内最大值的线段树刚好专业对口（答案是当前所有区间的最大值）

#include <iostream>
#include <cstring>
#include <algorithm>
#include<vector>
#include<array>
using namespace std;
#define int long long
const int N=200010;
struct edge{
    int l;
    int r;
    int mx;
    int add;
}tr[N*4];
vector<array<int,2>>v[N];
int t[N],x[N];
void pushup(int u){
    tr[u].mx=max(tr[u<<1].mx,tr[u<<1|1].mx);
}
void pushdown(int u){
    if(tr[u].add!=0){
        tr[u<<1].add+=tr[u].add;
        tr[u<<1|1].add+=tr[u].add;
        tr[u<<1].mx+=tr[u].add;
        tr[u<<1|1].mx+=tr[u].add;
        tr[u].add=0;
    }
}
void build(int u,int l,int r){
    if(l==r){
        tr[u]={l,r,0,0};
        return ;
    }else{
        tr[u]={l,r,0,0};
        int mid =l+r>>1;
        build(u<<1,l,mid);
        build(u<<1|1,mid+1,r);
        pushup(u);
    }
}
void change(int u,int l,int r,int w){
    if(tr[u].l>=l &&tr[u].r<=r){
        tr[u].mx+=w;
        tr[u].add+=w;
        return ;
    }else{
        pushdown(u);
        int mid =tr[u].l+tr[u].r>>1;
        if(mid>=l)change(u<<1,l,r,w);
        if(mid<r)change(u<<1|1,l,r,w);
        pushup(u);
    }
}

signed main(){
    int n,d,w;
    cin>>n>>d>>w;
    
    build(1,1,N);
    for(int i=1;i<=n;i++){
        cin>>t[i]>>x[i];  
        v[t[i]].push_back({x[i],1});
        if(t[i]+d<=N)v[t[i]+d].push_back({x[i],-1});//-0.5只能拿到1s前的
    }
     int ans=-1e18;
    for(int i=0;i<N;i++){
        for(auto c:v[i]){
            change(1,c[0],min(N,c[0]+w-1),c[1]);
        }
       // cout<<tr[1].mx<<endl;
        ans=max(ans,tr[1].mx);
    }
    
    cout<<ans<<endl;
}