20分求调
查看原帖
20分求调
215817
gyc071116楼主2024/8/4 10:50

线段树,但不知道哪里写错了

#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;
}
2024/8/4 10:50
加载中...