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');//输出最终结国 } } |
完结撒花✿✿ヽ(°▽°)ノ✿
