绍兴游记Day8 b 题解

(Updated: )
oi

官方题目传送门 官方题解传送门

题意

$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
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
#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(dq.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');//输出最终结国
    }
}

完结撒花✿✿ヽ(°▽°)ノ✿