线段树一开始查询里面可能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;
}
}