提交记录

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1e5+1;
queue<int> q[N];
struct SegmentTree
{
	struct Node
	{
		int sum;
		long long minimum;
	};
	Node node[N<<2];
	int len,d;
	void init(int l,int dt);
	void init(int now,int l,int r);
	void add(int id,int t);
	void add(int now,int l,int r,int pos,int val);
	int findpos(int id,int t);
	int findpos(int now,int l,int r,int pos,int t);
	int find(int t);
	int find(int now,int l,int r,int t);
	void pushUp(int now);
	int getSum(int l,int r);
	int getSum(int now,int l,int r,int ql,int qr);
};
void SegmentTree::init(int now,int l,int r)
{
	node[now].minimum=1e18;
	node[now].sum=0;
	if(l==r)
	{
		for(;q[l].size();q[l].pop());
		return;
	}
	int mid=(l+r)>>1;
	init(now<<1,l,mid);
	init(now<<1|1,mid+1,r);
	return;
}
void SegmentTree::init(int l,int dt)
{
	len=l;
	d=dt;
	init(1,1,l);
	return;
}
void SegmentTree::add(int id,int t)
{
	add(1,1,len,id,t);
	return;
}
void SegmentTree::add(int now,int l,int r,int pos,int val)
{
	if(l==r)
	{
		q[l].push(val);
		node[now].minimum=q[l].front();
		node[now].sum=q[l].size();
		return;
	}
	int mid=(l+r)>>1;
	if(pos<=mid)
	{
		add(now<<1,l,mid,pos,val);
	}
	else
	{
		add(now<<1|1,mid+1,r,pos,val);
	}
	pushUp(now);
	return;
}
void SegmentTree::pushUp(int now)
{
	node[now].sum=node[now<<1].sum+node[now<<1|1].sum;
	node[now].minimum=min(node[now<<1].minimum,node[now<<1|1].minimum);
	return;
}
int SegmentTree::findpos(int id,int t)
{
	return findpos(1,1,len,id,t);
}
int SegmentTree::findpos(int now,int l,int r,int pos,int t)
{
	if(l==r)
	{
		if(q[l].size())
		{
			if(q[l].front()+d-t>0)
			{
				return q[l].front()+d-t;
			}
			else
			{
				q[l].pop();
				node[now].sum=q[l].size();
				if(q[l].size())
				{
					node[now].minimum=q[l].front();
				}
				else
				{
					node[now].minimum=1e18;
				}
				return 0;
			}
		}
		return -1;
	}
	int mid=(l+r)>>1;
	int ret=0;
	if(pos<=mid)
	{
		ret=findpos(now<<1,l,mid,pos,t);
	}
	else
	{
		ret=findpos(now<<1,mid+1,r,pos,t);
	}
	pushUp(now);
	return ret;
}
int SegmentTree::find(int t)
{
	return find(1,1,len,t);
}
int SegmentTree::find(int now,int l,int r,int t)
{
	if(node[now].minimum+d-t>0)
	{
		return 0;
	}
	if(l==r)
	{
		q[l].pop();
		node[now].sum=q[l].size();
		if(q[l].size())
		{
			node[now].minimum=q[l].front();
		}
		else
		{
			node[now].minimum=1e18;
		}
		return l;
	}
	int mid=(l+r)>>1;
	int ret=0;
	if(node[now<<1].minimum+d-t<=0)
	{
		ret=find(now<<1,l,mid,t);
	}
	else
	{
		ret=find(now<<1|1,mid+1,r,t);
	}
	pushUp(now);
	return ret;
}
int SegmentTree::getSum(int l,int r)
{
	return getSum(1,1,len,l,r);
}
int SegmentTree::getSum(int now,int l,int r,int ql,int qr)
{
	if(r<ql || l>qr)
	{
		return 0;
	}
	if(ql<=l && r<=qr)
	{
		return node[now].sum;
	}
	int mid=(l+r)>>1;
	return getSum(now<<1,l,mid,ql,qr)+getSum(now<<1|1,mid+1,r,ql,qr);
}
int n,cd[N],mx;
SegmentTree seg;
void work()
{
	int t;
	scanf("%d",&t);
	for(int nowt=1;nowt<=t;nowt++)
	{
		scanf("%d",&n);
		mx=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&cd[i]);
			mx=max(mx,cd[i]);
		}
		seg.init(n,mx);
		int qq;
		scanf("%d",&qq);
		for(int nowq=1;nowq<=qq;nowq++)
		{
			int t,opt;
			scanf("%d%d",&t,&opt);
			if(opt==0)
			{
				int id;
				scanf("%d",&id);
				seg.add(id,t+cd[id]-mx);
			}
			else if(opt==1)
			{
				int res=seg.find(t);
				if(res)
				{
					printf("%d\n",res);
				}
				else
				{
					printf("Yazid is angry.\n");
				}
			}
			else if(opt==2)
			{
				int id;
				scanf("%d",&id);
				int res=seg.findpos(id,t);
				if(res==-1)
				{
					printf("YJQQQAQ is angry.\n");
				}
				else if(res==0)
				{
					printf("Succeeded!\n");
				}
				else
				{
					printf("%d\n",res);
				}
			}
			else if(opt==3)
			{
				int l,r;
				scanf("%d%d",&l,&r);
				printf("%d\n",seg.getSum(l,r));
			}
		}
	}
	return;
}
int main()
{
	freopen("data.txt","r",stdin);
	work();
	return 0;
}