懒得概括了,,,直接看题面吧
本题 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; }