5368. 【NOIP2017提高A组模拟9.16】为逝去的公主献上的七重樱 单调队列

队列"/>

5368. 【NOIP2017提高A组模拟9.16】为逝去的公主献上的七重樱 单调队列

简化题意：求mex，有撤销，删除，添加，询问四种操作,n<=1e7.
WerkeyTom_FTD大爷的题目。
O(n)明显。

亏大发了我，想了半天想出正解但是忘记单调队列怎么维护最小值了，对没错你没有听错我忘记单调队列怎么维护最小值了，发生这种事我很抱歉…想扇自己两耳光。
其实主要是想着要维护原来的队列完整，如果维护一个单调递增那肯定容易啊，问题是要让维护的队列完整，因为我撤销撤的是队头，如果你把队列搞乱了就GG了。
那怎么办？那当然是tm重新开一个队列啊！！！woc我智障无边了我。。

具体一点的话：维护撤销的东西就好了，求最小值，还有就是添加或者删除的x如果>操作数都没有影响，我没认真分析没搞出来，所以我细节炸了，而且我是可以直接暴力往前添加的（num），反正是均摊线性。。。

#include<cstdio>
#include<algorithm>
#include<cstring>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int N=1e7+5;
int n,m;
int op,l,r,num;
int vis[N];
int q1[N],q2[N];
int t1,w1,t2,w2;
int read()
{int x=0,f=1;char ch=getchar();while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
int main()
{freopen("knowledge.in","r",stdin);freopen("knowledge.out","w",stdout);scanf("%d%d",&m,&op);int last=0;t1=t2=1,w1=w2=0;int num=0;fo(i,1,m){int id=read();int x;if (id==1){x=read();if (op)x^=last;if (x<=m)vis[x]=1;while (vis[num])num++;}else if (id==2){x=read();if (op)x^=last;if (x<=m)vis[x]=0;q1[++w1]=x;while (t2<=w2&&q2[w2]>x)w2--;q2[++w2]=x;}else if (id==3){if (t1>w1)continue;if (q1[t1]<=m)vis[q1[t1]]=1;while (vis[num])num++;if (q2[t2]==q1[t1])t2++;t1++;}else if (id==4){last=num;if (t2<=w2)last=min(last,q2[t2]);printf("%d\n",last);}}return 0;
}