Description

懒得概括了,,,直接看题面吧

本题 C/C++ 时限 2.5 秒，Pascal 时限 5 秒。最后将改时限重测所有 Pascal 提交。

不知道大家有没有听过物凄系列的一首歌，帕秋莉用卡车给博丽老板运货的故事。

又一次，卡车司机帕秋莉被拜托。红魔馆之主蕾米莉亚喜欢喝红茶，一天她要求帕秋莉开卡车帮她运红茶过来。

红茶其实是编好号了的，每个红茶都用一个非负整数来编号，从 \(0\) 开始一直到正无穷。帕秋莉请来好朋友魔理沙，帮她一起运红茶。

一开始卡车上已经有了编号为 \(0\) 到 \(a\) 的红茶（注意 \(a=-1\) 就表示初始卡车上没有任何红茶），然后接下来到红魔馆的路上有 \(m\) 个时刻，每个时刻都会发生一种事件。

• 第一种事件，帕秋莉到了一个红茶店，买了一个编号为 \(x\) 的红茶（卡车上初始没有这种编号的红茶，之前也不会买过相同编号的红茶）。
• 第二种事件，一个目前在卡车上的编号为 \(x\) 的红茶飞出了卡车。
• 第三种事件，魔理沙把目前不在卡车上的最早飞出去的红茶捡回了卡车上（如果一个红茶曾经飞出去被捡回来过然后再飞出去，这里认为其飞出去的时间为最近一次飞出去的时间）。

由于描述这些事件实在是太麻烦了，聪明的魔理沙用了一个长度为 \(m\) 的整数序列 \(p\) 来描述每个时刻发生的事件。

• 这个序列 \(p\) 里所有元素均为 \([-1,b)\) 的整数。
• 若 \(p_i=-1\) 则表示时刻 \(i\) 发生了第三种事件，如果此时并不存在满足条件的飞出去的红茶，则代表魔理沙脑子没转过来，忽视此次事件。
• 否则，如果在时刻 \(i\) 编号为 \(p_i\) 的红茶初始不在卡车上也从来没有通过第一种事件买过，则表示时刻 \(i\) 发生了一个买编号为 \(p_i\) 的红茶的第一种事件。
• 否则，如果在时刻 \(i\) 编号为 \(p_i\) 的红茶在卡车上，则表示时刻 \(i\) 发生了一个编号为 \(p_i\) 的红茶飞出卡车的第二种事件。
• 否则，表示时刻 \(i\) 发生了第三种事件，如果此时并不存在满足条件的飞出去的红茶，则忽视此次事件。

如果某个时刻的事件被忽视，那么我们不执行对应的操作，也不计算此时的答案。

帕秋莉是一个勤奋的人，每个时刻过后，如果这个时刻 \(i\) 发生了事件（如果一个时刻发生的事件被忽视了，就不认为这个时刻发生了事件），令 \(ans_i\) 表示时刻 \(i\) 过后卡车上所有编号小于 \(ans_i\) 的红茶都出现了，而编号为 \(ans_i\) 的红茶没有出现（很显然这个值是唯一的）。当然如果时刻 \(i\) 没有发生事件，则令 \(ans_i=0\) 。

请你对于 \(1 \leq i \leq m\) 计算出 \(ans_i\times (i^2+7i)\ mod\ 998244353\) 的异或和。

Solution

比较像NOIP2016 D2T2蚯蚓的一道题目。

60pts的做法比较显然，像HEOI2016排序那题的在线做法一样拿一个\(set\)维护所有的区间，动态合并区间，提取区间元素就行了。

考虑\(d=1\)如何做

相当于只有加元素和求\(mex\)，维护一个桶表示每个编号是否出现。发现答案是不降的，可以维护一个指针，每次加入后尝试向右移动指针即可。时间复杂度\(O(max(a,b))\)。

考虑在\(d=1\)的做法的基础上维护删除和恢复两种操作。

同样维护出加入操作的答案\(x\)，和被删除元素的最小值\(y\)，容易发现\(mex\)为\(min(x,y)\)。

如果用堆维护删除元素的最小值，时间复杂度\(O(n\log n)\)，期望得分\(70\sim 80\)

如果用单调队列维护删除元素的最小值，时间复杂度\(O(n)\)，期望得分\(100\)！

Code

#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<cctype>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using std::min;
using std::max;
using std::swap;
using std::vector;
const int N=1e6+5;
typedef double db;
typedef long long ll;
typedef unsigned int uint;
#define pb(A) push_back(A)
#define pii std::pair<int,int>
#define all(A) A.begin(),A.end()
#define mp(A,B) std::make_pair(A,B)

uint ans,now;
int ptr,hd,tail,q[N][2];
int T,m,a,b,d,p[N],remm[N];
int hasbuy[N<<1],isin[N<<1];

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;
    }
}
using IO::read;
using IO::init_case;
using IO::update_ans;

int getint(){
    int X=0,w=0;char ch=0;
    while(!isdigit(ch))w|=ch=='-',ch=getchar();
    while( isdigit(ch))X=X*10+ch-48,ch=getchar();
    if(w) return -X;return X;
}

void rem(int x){
    isin[remm[x]]=1;
    while(hd<=tail and q[hd][1]<=x) hd++;
}

signed main(){
    read(T);
    while(T--){
        ans=now=0;
        int cnt1=0,cnt2=0;
        memset(isin,0,sizeof isin);
        memset(hasbuy,0,sizeof hasbuy);
        init_case(m,a,b,d,p);
        for(int i=0;i<=a;i++) isin[i]=hasbuy[i]=1;
        ptr=a+1;hd=1,tail=0;
        for(int i=1;i<=m;i++){
            if(p[i]==-1){
                if(d or hd>tail) continue;
                cnt1++;rem(cnt1);
                while(isin[ptr]) ptr++;
            } else if(!hasbuy[p[i]]){
                isin[p[i]]=hasbuy[p[i]]=1;
                while(isin[ptr]) ptr++;
            } else if(isin[p[i]]){
                if(d) continue;
                cnt2++;remm[cnt2]=p[i];
                while(hd<=tail and q[tail][0]>p[i]) tail--;
                q[++tail][0]=p[i];q[tail][1]=cnt2;
                isin[p[i]]=0;
                while(isin[ptr]) ptr++;
            } else{
                if(hd>tail or d) continue;
                cnt1++;rem(cnt1);
                while(isin[ptr]) ptr++;
            } now=ptr;
            if(hd<=tail) now=min(now,(uint)q[hd][0]);
            update_ans(ans,now,i);
        } printf("%u\n",ans);
    } return 0;
}