P9588 队列

思路

观察发现 \(x\)，\(y\)，\(z\) 都可以很大，所以如果直接用队列老老实实地操作，肯定过不了。

因为每次加入都是 \(1,2,3,\cdots x\) 所以这段是连续的，所以我们考虑一段一段的存入队列，记录每一段的左右端点。

操作 \(2\) 的删除，就一段一段地删除，如果删不完一段，就改这一段的左端点。

操作 \(3\) 的查询可以记录每段的长度的前缀和（如果用操作 \(2\) 的办法的话就会 TLE）。

操作 \(4\) 的最大值只可能出现在每段的 \(x\)，考虑用 multiset 存 \(x\)，但是不知道为什么我的 multiset 炸了，改成 map 和 set 才对。

AC code

#include<bits/stdc++.h>
using namespace std;
struct node{long long l,r;}dl[200005];
long long c,q,op,x,he,ta,len[200005];
set<long long>s;
map<long long ,int>m;
int main()
{
	scanf("%lld%lld",&c,&q);
	while(q--)
	{
		scanf("%lld",&op);
		if(op==1) scanf("%lld",&x),dl[++ta].l=1,dl[ta].r=x,s.insert(x),m[x]++,len[ta]=dl[ta].r+len[ta-1];
		else if(op==2)
		{
			scanf("%lld",&x);
			while(x>=dl[he+1].r-dl[he+1].l+1){x-=dl[he+1].r-dl[he+1].l+1,++he;if(m[dl[he].r]==1) s.erase(dl[he].r);m[dl[he].r]--;}
			if(x) dl[he+1].l+=x;
		}
		else if(op==3)
		{
			scanf("%lld",&x);
			x+=len[he]+dl[he+1].l-1;
			long long l=he,r=ta,mid,ansp;
			while(l<=r)
			{
				mid=l+r>>1;
				if(x>len[mid]) ansp=mid,l=mid+1;
				else r=mid-1;
			}
			printf("%lld\n",x-len[ansp]);
		}
		else
		{
			auto i=s.end();--i;
			printf("%lld\n",*i);
		}
	}
	return 0;
}