Link
题意
$Hzy$有一个集合,一开始有$[0\dots a]$这些数字(如果$a=-1$则说明集合为空)。接下来有$m$个时刻,每个时刻都会有一种操作。
1. 插入一个数字$x$,保证$x$不在集合中。
2. 删去一个数字$x$。
3. 把目前不在集合中的最早被删除的数字,插回到集合中(如果一个数字曾经被删去被插回来过然后再删去,这里认为其删去的时间为最近一次删去的时间)。
由于描述这$m$个时刻的操作实在太麻烦了,所以$Hzy$用了一个长度为$m$的序列$p$来描述每个时刻的操作种类。对于每个操作,满足以下约定。
1. 这个序列$p$里所有元素均为$[-1,b)$的整数
2. 若$p_i=-1$,则表示时刻i的操作为第三种,如果此时并不存在满足条件且被删去的数字,则忽略此操作。
3. 否则,如果时刻$i$中,大小为$p_i$的数字一开始不在集合中且也从来没有通过第一种操作插入集合中,则表示第$i$个操作为向集合中插入一个大小为$p_i$的数字,即第一种操作。
4. 否则,如果时刻$i$中,大小为$p_i$的数字在集合中,则把$p_i$从集合里删除,即第二种操作。
5. 否则,表示时刻i的操作为第三种,如果此时并不存在满足条件且被删去的数字,则忽略此操作。
$Hzy$现在想知道在第$i$个时刻的操作进行完后,集合的$mex$是什么,即在集合中未出现过的最小的自然数。第$i$个操作的答案设为$ans_i$(如果第$i$个操作被忽略,$ans_i=0$)。但是她不满足仅知道$ans_i$,她想知道$ans_i×(i^2+7i) \mod 998244353$的异或和
如果某个时刻的操作被忽略,那么$Hzy$将不会进行任何操作,也不计算此时的答案。
下面是$IO$输入代码:
1 2 3 4 5 6 7 8 9 |
namespace IO{ int c; unsigned int seed; unsigned int randnum(){seed^=seed<<13;seed^=seed>>17;seed^=seed<<5;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=1;i<=m;i++){if(randnum()%c==0)p[i]=-1;else p[i]=randnum()%b;}} inline void update_ans(unsigned int &ans_sum,unsigned int cur_ans,int no){const static unsigned int mod=998244353;ans_sum^=(long long)no*(no+7)%mod*cur_ans%mod;} } |
题解&Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
#include<bits/stdc++.h> using namespace std; namespace IO{ int c; unsigned int seed; unsigned int randnum(){seed^=seed<<13;seed^=seed>>17;seed^=seed<<5;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=1;i<=m;i++){if(randnum()%c==0)p[i]=-1;else p[i]=randnum()%b;}} inline void update_ans(unsigned int &ans_sum,unsigned int cur_ans,int no){const static unsigned int mod=998244353;ans_sum^=(long long)no*(no+7)%mod*cur_ans%mod;} } void write(int x){if(x<0) putchar('-'),x=-x;if(x<10) putchar(x+'0');else{write(x/10);putchar(x%10+'0');}} unsigned int ans_sum; int T,m,a,b,d,ans,p[4000010],f[4000010],vis[4000010],num[4000010],h,t,g[4000010]; bool did[4000010],tag; queue<int> q; namespace Solve{ inline void Step1(int x){vis[x]=1;did[x]=1;while(vis[ans]&&ans<=b) ans++;}//操作1:加入一个数字,把这个数标记在集合中(did)以及之前或现在加入过(vis),while求出范围内没有加入过的最小值 inline void Step2(int x){if(d==1){tag=1;return ;}did[x]=0;q.push(x);while(h<=t&&g[t]>x) t--;g[++t]=x;}//操作2:删除一个数,如果d=1那么忽略,否则将这个数取消在集合中这个标记(did)并且加入到"删除过的"队列中,再插入到删除的单调度队列 inline void Step3(){if(d||q.empty()){tag=1;return ;}did[q.front()]=1;q.pop();}//操作3:加入最早删除的值,d=1、之前没有删除时忽略,否则把该数字标记在集合中,并且在队列中pop掉这个数 } signed main(){ IO::read(T);//输入数据组数 while(T--){ IO::init_case(m,a,b,d,p);//调用IO读入 for(int i=0;i<=a;i++) vis[i]=1,did[i]=1;//初始化,一开始[0,a]区间内所有的数都在集合中 for(int i=a+1;i<=b;i++) vis[i]=0,did[i]=0;//初始化,一开始(a,b]区间内所有的数都不在集合中 ans=a+1;h=1;t=0;tag=0;ans_sum=0;//一开始ans=a+1(因为[0,a]区间内所有的数已经在集合中) while(!q.empty()) q.pop();//清空队列 for(int i=1;i<=m;i++){ tag=0;//tag表示该操作是否忽略(0表示不忽略,1表示忽略) if(p[i]==-1) Solve::Step3();//如果操作为-1,那么进行操作3 else if(vis[p[i]]==0) Solve::Step1(p[i]);//如果之前没有加入过该数,那么进行操作1 else if(did[p[i]]) Solve::Step2(p[i]);//如果现在还是有这个数,那么进行操作2 else Solve::Step3();//否则进行操作3 if(tag==1) continue ;//如果忽略,那就忽略 while(h<=t&&did[g[h]]) h++;//如果在集合中,那就下一个 if(h>t) IO::update_ans(ans_sum,ans,i);//如果队列里没有了,那么就是ans(加入操作中的最小值) else IO::update_ans(ans_sum,min(ans,g[h]),i);//否则就是加入操作最小值与删除操作最小值的最小值 } write(ans_sum);putchar('\n');//输出最终结国 } } |
完结撒花✿✿ヽ(°▽°)ノ✿