题目描述
题解
一直在往数据随机的方向想
把<=A中的删除操作看成元素的话,那么就是求一个队列里的最小值,单调队列维护
>A的部分再维护一个未选的最小值,选了之后就和上面一样了,最后再取min
code
#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define mod 998244353
#define ll long long
#define file
using namespace std;
int d[2100001][2],d2[2100001],Q,A,B,C,D,n,i,j,k,l,h,t,ans,x,T,t1,t2;
bool bz1[2100001],bz2[2100001],Bz;
unsigned int seed;
char st[21],ch;
ll Ans;
unsigned int Random()
{
seed=seed^(seed<<13);
seed=seed^(seed>>17);
seed=seed^(seed<<5);
return seed;
}
int main()
{
freopen("sage.in","r",stdin);
#ifdef file
freopen("sage.out","w",stdout);
#endif
scanf("%d",&Q);
for (;Q;--Q)
{
scanf("%d%u%d%d%d%d",&n,&seed,&A,&B,&C,&D),T=A+1;
memset(bz1,0,max(A,B)+2),memset(bz2,0,max(A,B)+2);
if (A>=0)
memset(bz1,1,A+1),memset(bz2,1,A+1);
ans=A+1;
Ans=t=0,h=1;t1=1,t2=0;
fo(i,1,n)
{
if (!(Random()%C))
x=-1;
else
x=Random()%B;
Bz=0;
if (!D)
{
if (x>=0)
{
if (!bz1[x])
{
bz1[x]=bz2[x]=1;
while (bz1[T]) ++T;
Bz=1;
}
else
if (bz2[x])
{
bz2[x]=0;
while (h<=t && d[t][0]>x) --t;
++t,d[t][0]=x,d[t][1]=++t2,d2[t2]=x;
Bz=1;
}
else
if (h<=t)
{
if (d[h][1]==t1) ++h;
bz2[d2[t1++]]=1;
Bz=1;
}
}
else
if (h<=t)
{
if (d[h][1]==t1) ++h;
bz2[d2[t1++]]=1;
Bz=1;
}
if (h>t) ans=T; else ans=min(T,d[h][0]);
}
else
if (x>=0)
{
if (!bz2[x])
{
bz2[x]=1;
while (bz2[ans]) ++ans;
Bz=1;
}
}
if (Bz)
Ans^=1ll*ans*(1ll*i*i+i*7)%mod;
// cout<<ans<<endl;
}
printf("%lld\n",Ans);
}
fclose(stdin);
fclose(stdout);
return 0;
}