为什么25pts,小号关注
查看原帖
为什么25pts,小号关注
538683
Enoch006楼主2024/4/4 23:49

rt,十分奇怪。

#include <bits/stdc++.h>
#define int long long
#define maxm 1000005
#define maxn 1005
#define inf 0x3f3f3f3f3f3f
using namespace std;
int q,n,m,sum;
int x[maxm],y[maxm];
struct Seg{
	int l,r,sum,mx;//sum维护这段区间骑士拜访时间之和,mx维护需要等到的  时刻  !!! 
}t[maxm<<2],ans;
#define lc k<<1
#define rc k<<1|1
void Build(int k,int l,int r){
	t[k]=(Seg){l,r,0,l};
	if(l==r)return;
	int mid=(l+r)>>1;
	Build(lc,l,mid);
	Build(rc,mid+1,r);
} 
void Pushup(int k){
	t[k].sum=t[lc].sum+t[rc].sum;
	t[k].mx=max(t[rc].mx,t[rc].sum+t[lc].mx);
}
void Add(int k,int x,int y){
	if(t[k].l>x||t[k].r<x)return;
	if(t[k].l==t[k].r){
		t[k].sum+=y;
		t[k].mx=t[k].l+t[k].sum;
		return;
	}
	Add(lc,x,y);
	Add(rc,x,y);
	Pushup(k);
}
void Ask(int k,int x){
	if(t[k].l>x)return;
//	cout<<t[k].l<<" "<<t[k].r<<" "<<t[k].sum<<" "<<t[k].mx<<"\n";
	if(t[k].r<=x){
		ans.sum+=t[k].sum;
		ans.mx=max(t[k].mx,ans.mx+t[k].sum);
		return;
	}
	Ask(lc,x);
	Ask(rc,x);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	cin>>q;
	Build(1,1,maxm);
    for(int i=1;i<=q;i++){
		char op;
		int z;
		cin>>op;
		if(op=='+'){
			cin>>x[i]>>y[i];
			Add(1,x[i],y[i]);
		}
		if(op=='-'){
			cin>>z;
			Add(1,x[z],-y[z]);
		}
		if(op=='?'){
			ans.mx=ans.sum=0;
			cin>>z;
			Ask(1,z);
			ans.mx=max(ans.mx,ans.sum);
			cout<<ans.mx-z<<"\n";
		}
	}
    return 0;
}

这样就会获得25分,但稍微改一下:

#include <bits/stdc++.h>
#define int long long
#define maxm 1000005
#define maxn 1005
#define inf 0x3f3f3f3f3f3f
using namespace std;
int q,n,m,sum;
int x[maxm],y[maxm];
struct Seg{
	int l,r,sum,mx;//sum维护这段区间骑士拜访时间之和,mx维护需要等到的  时刻  !!! 
}t[maxm<<2],ans;
#define lc k<<1
#define rc k<<1|1
void Build(int k,int l,int r){
	t[k]=(Seg){l,r,0,l};
	if(l==r)return;
	int mid=(l+r)>>1;
	Build(lc,l,mid);
	Build(rc,mid+1,r);
} 
void Pushup(int k){
	t[k].sum=t[lc].sum+t[rc].sum;
	t[k].mx=max(t[rc].mx,t[rc].sum+t[lc].mx);
}
void Add(int k,int x,int y){
	if(t[k].l>x||t[k].r<x)return;
	if(t[k].l==t[k].r){
		t[k].sum+=y;
		t[k].mx=t[k].l+t[k].sum;
		return;
	}
	Add(lc,x,y);
	Add(rc,x,y);
	Pushup(k);
}
void Ask(int k,int x){
	if(t[k].l>x)return;
//	cout<<t[k].l<<" "<<t[k].r<<" "<<t[k].sum<<" "<<t[k].mx<<"\n";
	if(t[k].r<=x){
		ans.sum+=t[k].sum;
		ans.mx=max(t[k].mx,ans.mx+t[k].sum);
		return;
	}
	Ask(lc,x);
	Ask(rc,x);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	cin>>q;
	Build(1,1,maxm);
    for(int i=1;i<=q;i++){
		char op;
		int z;
		cin>>op;
		if(op=='+'){
			cin>>x[i]>>y[i];
			Add(1,x[i],y[i]);
		}
		if(op=='-'){
			cin>>z;
			Add(1,x[z],-y[z]);
		}
		if(op=='?'){
			ans.mx=ans.sum=0;
			cin>>z;
			Ask(1,z);
			ans.mx=max(ans.mx,ans.sum);
			cout<<max(0ll,ans.mx-z)<<"\n";//////////////////////////////////////////就和0取了个max
		}
	}
    return 0;
}

这样改就 AC 了,问题是为什么线段树中会出现负数呢,按理来说应该不会啊?

2024/4/4 23:49
加载中...