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

发布时间:2024年01月12日

前置知识:线段树

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;
}

文章来源:https://blog.csdn.net/rrt517/article/details/135470940
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。