【题意】一开始车上有编号为0~a的红茶，过程中出现的红茶编号仅有[0,b)，有三种操作：
1.买进编号未在车上出现过的红茶。
2.丢掉车上指定编号的红茶。
3.将最早丢出去的红茶捡回来。
每次操作后求编号最小的不在车上的红茶。
【算法】单调队列
【题解】本题最重要的性质在于早丢早捡。
因此，当进行丢掉编号为x的红茶这一操作时，如果编号>x的红茶早丢，那么也一定早捡，所以这些红茶没有贡献。
所以用单调队列维护所有有效的红茶，那么捡回来的时候判断是否队头，每次答案就是min(队头,maxs+1)，maxs是当前已买过的红茶编号。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
namespace IO{
int c;
unsigned int seed;
unsigned int randnum(){
seed^=seed<<;
seed^=seed>>;
seed^=seed<<;
return seed;
} inline int read(int &x){scanf("%d",&x);return x;}
inline void init_case(int &m,int &a,int &b,int &d,int p[]){
scanf("%d%u%d%d%d%d",&m,&seed,&a,&b,&c,&d);
for(int i=;i<=m;i++){
if(randnum()%c==)p[i]=-;
else p[i]=randnum()%b;
}
} inline void update_ans(unsigned int &ans_sum,unsigned int cur_ans,int no){
const static unsigned int mod=;
ans_sum^=(long long)no*(no+)%mod*cur_ans%mod;
}
}
using IO::read;
using IO::init_case;
using IO::update_ans;
const int maxn=;
int p[maxn];
bool A[maxn],B[maxn];
int q[maxn],head,tail;
queue<int>Q;
void ins(int x){
while(head<tail&&q[tail-]>x)tail--;
q[tail++]=x;
}
int main(){
int T;read(T);
int m,a,b,d;
while(T--){
unsigned int ans_sum=,cur_ans=;
init_case(m,a,b,d,p);
memset(A,,sizeof(A));
memset(B,,sizeof(B));
head=;tail=;
for(int i=;i<=a;i++)A[i]=B[i]=;
while(!Q.empty())Q.pop();
int ans=a+,maxs=a;
for(int i=;i<=m;i++){
bool ok=;
if(p[i]==-){
if(Q.empty()||d)ok=;else{
int x=Q.front();
A[x]=;Q.pop();
if(head<tail&&q[head]==x)head++;
if(head<tail)ans=min(maxs+,q[head]);else ans=maxs+;
}
}
else if(!B[p[i]]){
A[p[i]]=B[p[i]]=;
while(B[maxs+]){
if(ans==maxs+)ans++;
maxs++;
}
if(head<tail&&maxs+>=q[head])ans=q[head];
}
else if(A[p[i]]){
if(d)ok=;else{
Q.push(p[i]);A[p[i]]=;
ins(p[i]);
ans=min(ans,q[head]);
}
}
else{
if(Q.empty()||d)ok=;else{
int x=Q.front();
A[x]=;Q.pop();
if(head<tail&&q[head]==x)head++;
if(head<tail)ans=min(maxs+,q[head]);else ans=maxs+;
}
}
if(!ok)cur_ans=;else cur_ans=ans;
update_ans(ans_sum,cur_ans,i);
}
printf("%u\n",ans_sum);
}
return ;
}