线段树,但不知道哪里写错了
#include<bits/stdc++.h>
#define ls (x<<1)
#define rs (x<<1)|1
using namespace std;
struct node{
int l;
int r;
int sum0;
int sum1;
int sum2;
}tree[3500005];
int t_ls[400005],t[200005],tag[3500005];
void build_tree(int x,int l,int r){
tree[x].sum0=t_ls[r+1]-t_ls[l];
if(l==r){
tree[x].l=l;
tree[x].r=r;
return;
}
int mid=(l+r)>>1;
build_tree(ls,l,mid);
build_tree(rs,mid+1,r);
tree[x].l=l;
tree[x].r=r;
}
void update(int x){
tree[x].sum0=tree[ls].sum0+tree[rs].sum0;
tree[x].sum1=tree[ls].sum1+tree[rs].sum1;
tree[x].sum2=tree[ls].sum2+tree[rs].sum2;
}
void down(int x){
if(tag[x]==0) return;
if(tag[x]==1){
tree[ls].sum2=tree[ls].sum1;
tree[ls].sum1=tree[ls].sum0;
tree[ls].sum0=0;
tree[rs].sum2=tree[rs].sum1;
tree[rs].sum1=tree[rs].sum0;
tree[rs].sum0=0;
}
if(tag[x]==2){
tree[ls].sum2=tree[ls].sum0;
tree[ls].sum1=0;
tree[ls].sum0=0;
tree[rs].sum2=tree[rs].sum0;
tree[rs].sum1=0;
tree[rs].sum0=0;
}
if(tag[x]>2){
tree[ls].sum2=0;
tree[ls].sum1=0;
tree[ls].sum0=0;
tree[rs].sum2=0;
tree[rs].sum1=0;
tree[rs].sum0=0;
}
tag[ls]=tag[x];
tag[rs]=tag[x];
tag[x]=0;
}
void add(int x,int L,int R){
if(L<=t_ls[tree[x].l]&&R>=t_ls[tree[x].r+1]){
tree[x].sum2=tree[x].sum1;
tree[x].sum1=tree[x].sum0;
tree[x].sum0=0;
tag[x]++;
return;
}
if(t_ls[tree[x].l]>=R||t_ls[tree[x].r+1]<=L) return;
down(x);
add(ls,L,R);
add(rs,L,R);
update(x);
}
void mius(int x,int L,int R){
if(L<=t_ls[tree[x].l]&&R>=t_ls[tree[x].r+1]){
tree[x].sum0=tree[x].sum1;
tree[x].sum1=tree[x].sum2;
tree[x].sum2=114514;
tag[x]--;
return;
}
if(t_ls[tree[x].l]>=R||t_ls[tree[x].r+1]<=L) return;
down(x);
mius(ls,L,R);
mius(rs,L,R);
update(x);
}
int main(){
int n,m;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&t[i]);
t_ls[i*2-1]=t[i];
t_ls[i*2]=t[i]+m;
}
sort(t_ls+1,t_ls+1+2*n);
int cnt=unique(t_ls+1,t_ls+1+2*n)-t_ls-1;
build_tree(1,1,cnt-1);
for(int i=1;i<=n;i++){
add(1,t[i],t[i]+m);
}
int maxx=0;
for(int i=1;i<=n;i++){
mius(1,t[i],t[i]+m);
maxx=max(maxx,tree[1].sum1);
add(1,t[i],t[i]+m);
}
printf("%d",maxx+m);
return 0;
}