代码的一个玄学问题
查看原帖
代码的一个玄学问题
511268
PIKA_PIKA楼主2024/9/14 17:01

线段树一开始查询里面可能l>r,提交后AC,然后我将t数组开到2e5+10,线段树空间不变,RE了(4e5时AC)。请问怎么回事?

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int c,T,n,m,k,d,t[N],tot;
int dp[N];
struct Edg{
    int x,y,w;
}a[100010];
int pos(int x){
    return lower_bound(t+1,t+n+1,x)-t;
}
bool cmp(Edg A,Edg B){
    return A.x<B.x;
}
struct Edge{
    int l,r,mx,add;
}tr[N<<2];
void build(int p,int l,int r){
    tr[p]={l,r,0,0};
    if(l==r) return;
    int mid=l+r>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
}
inline void Add(int p,int x){
    tr[p].add+=x;tr[p].mx+=x;
}
inline void pushdown(int p){
    if(tr[p].add){
        Add(p<<1,tr[p].add);Add(p<<1|1,tr[p].add);
        tr[p].add=0;
    }
}
inline int query(int p,int l,int r){
    if(l>r) return -1e13;
    if(l<=tr[p].l&&r>=tr[p].r){
        return tr[p].mx;
    }
    pushdown(p);
    int mid=tr[p].l+tr[p].r>>1,ans=-1e13;
    if(l<=mid) ans=max(ans,query(p<<1,l,r));
    if(r>mid) ans=max(ans,query(p<<1|1,l,r));
    return ans;
}
inline void pushup(int p){
    tr[p].mx=max(tr[p<<1].mx,tr[p<<1|1].mx);
}
inline void change(int p,int l,int r,int x){
    if(l<=tr[p].l&&r>=tr[p].r){
        tr[p].add+=x;tr[p].mx+=x;
        return;
    }
    pushdown(p);
    int mid=tr[p].l+tr[p].r>>1;
    if(l<=mid) change(p<<1,l,r,x);
    if(r>mid) change(p<<1|1,l,r,x);
    pushup(p);
}
signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>c>>T;
    while(T--){
        cin>>n>>m>>k>>d;tot=0;
        for(int i=1;i<=m;i++){
            cin>>a[i].x>>a[i].y>>a[i].w;a[i].y=a[i].x-a[i].y;
            t[++tot]=a[i].x;t[++tot]=a[i].y;
        }
        sort(t+1,t+tot+1);
        n=unique(t+1,t+tot+1)-t-1;
        for(int i=1;i<=m;i++) a[i].x=pos(a[i].x),a[i].y=pos(a[i].y);
        int lf=1;sort(a+1,a+m+1,cmp);
        build(1,1,n);
        for(int i=1;i<=n;i++){
            dp[i]=0;int l=pos(t[i]-k);
            change(1,i,i,dp[i-1]+t[i]*d);
            while(lf<=m&&a[lf].x<=i){
                if(a[lf].y>=l) change(1,1,a[lf].y,a[lf].w);
                lf++;
            }
            dp[i]=max(dp[i-1],query(1,l,i-1)-t[i]*d);
        }
        cout<<dp[n]<<endl;
    }
}
2024/9/14 17:01
加载中...