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 了,问题是为什么线段树中会出现负数呢,按理来说应该不会啊?