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]);
	}
}