Description
Input
Output
每组数据输出一行表示答案。
Sample Input
1
7 327711436 4 6 3 0
Sample Output
292
Data Constraint
Solution
用一个普通队列维护扔出去的红茶的编号，这是为了快速找到最早扔的并放回来。
再用一个单调队列维护扔出去的红茶的编号，这是为了更新答案。
如果一个编号更小的红茶在之后被扔出去了，那么之前编号大于它的红茶一定在它之前被捡回来，并且答案不会比这个较小的编号的红茶更大。因此我们可以维护一个扔出去的编号递增的红茶单调队列，每次如果队头的红茶被捡回来了就不断加l+1，如果队尾的编号大于当前加入的编号就不断r-1。更新答案时判断一下，如果l<=r则用队头更新，否则用当前连续的最大的数更新。
注意还是memset好。
Code
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define I int
#define ui unsigned int
#define ll long long
#define F(i,a,b) for(I i=a;i<=b;i++)
#define Fd(i,a,b) for(I i=a;i>=b;i--)
#define mem(a,b) memset(a,b,sizeof a)
#define N 1000002
#define M 998244353
using namespace std;
I p,T,m,a,b,c,d,bz[N<<1],in[N<<1],s[N],L,R,q[N],l,r,now;
ll ans[N];
ui seed;
ui randnum(){
seed^=seed<<13;
seed^=seed>>17;
seed^=seed<<5;
return seed;
}
void up(I x){
while(l<=r&&in[q[l]]) l++;
if(l<=r&&q[l]<=now) ans[x]=q[l];
else{
while(in[now+1]) now++;
ans[x]=now+1;
}
}
void back(I x){
if(L>R) ans[x]=0;
else{
in[s[L]]=1;L++;
up(x);
}
}
void out(I x){
in[s[++R]=p]=0;
while(l<=r&&p<q[r]) r--;
q[++r]=p;
up(x);
}
I main(){
freopen("sage.in","r",stdin);
freopen("sage.out","w",stdout);
scanf("%d",&T);
while(T--){
scanf("%d%u%d%d%d%d",&m,&seed,&a,&b,&c,&d);
mem(in,0),mem(bz,0);
L=l=1,R=r=0;
F(i,0,a) in[i]=bz[i]=1;
now=a;
F(i,1,m){
if(randnum()%c==0){
if(d) continue;
back(i);
}
else{
p=randnum()%b;
if(!bz[p]){bz[p]=in[p]=1;up(i);}
else if(in[p]){if(d) continue;out(i);}
else{if(d) continue;back(i);}
}
}
ans[0]=0;
F(i,1,m){
ans[0]^=((ll)i*((ll)i+7)%M*(ll)ans[i])%M;
ans[i]=0;
}
printf("%lld\n",ans[0]);
}
return 0;
}
