2018-2019 ICPC, NEERC, Northern Eurasia Finals K. King Kog's Reception 线段树

K. King Kog's Reception

题意：有q个操作，第 i 次操作若为 + t d，表示在 t 这个时刻插入一个耗时为 d 的骑士，若 -  i 表示删除第 i 个操作，若 ? t 表示查询如果我要在 t 时刻进行进行活动，至少要排多久的队。

思路：设线段树sum和mx分别表示区间内耗时总长和该区间至少要到mx时刻才能处理完区间内所有骑士，那么两个区间合并时显然mx[ o ]=max(mx[ rs ]，mx[ ls ]+sum[ rs ])，每次查询就是把 1 到 t 区间分为一些小区间不停的合并，最后得到的值 - t 就是答案。

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1e6+10,N=1e6;
typedef long long ll;
int p[maxn],v[maxn],q;
ll sum[maxn*4],mx[maxn*4],ans;
void build(int o,int l,int r)
{
	if(l==r)
	{
		mx[o]=l;
		return;
	}
	int ls=o*2,rs=o*2+1,m=(l+r)/2;
	build(ls,l,m);
	build(rs,m+1,r);
	mx[o]=max(mx[rs],mx[ls]+sum[rs]);
	sum[o]=sum[ls]+sum[rs];
}
void up(int o,int l,int r,int k,int val)
{
	if(l==r)
	{
		sum[o]+=val;
		mx[o]+=val;
		return;
	}
	int ls=o*2,rs=o*2+1,m=(l+r)/2;
	if(k<=m)up(ls,l,m,k,val);
	else up(rs,m+1,r,k,val);
	mx[o]=max(mx[rs],mx[ls]+sum[rs]);
	sum[o]=sum[ls]+sum[rs];
}
ll qu(int o,int l,int r,int k)
{
	if(r<=k)
	{
		ans=max(mx[o],ans+sum[o]);
		return ans;
	}
	int ls=o*2,rs=o*2+1,m=(l+r)/2;
	qu(ls,l,m,k);
	if(k>m)qu(rs,m+1,r,k);
	return ans;	
}
int main()
{
	char op;
	build(1,1,N);
	scanf("%d",&q);
	for(int i=1;i<=q;i++)
	{
		scanf(" %c%d",&op,&p[i]);
		if(op=='+')
		scanf("%d",&v[i]),up(1,1,N,p[i],v[i]);
		else if(op=='-')
		up(1,1,N,p[p[i]],-v[p[i]]);
		else
		ans=0,printf("%I64d\n",qu(1,1,N,p[i])-p[i]);
	}
}