LOJ541 - 「LibreOJ NOIP Round #1」七曜圣贤

2017/11/06

题面

链接

做法 #1

01-Tire 维护 mex ,大力压位可以做到

期望得分:70 分
实际得分:60 分惨案

做法 #2

离线维护出每个值不存在的时间段,并查集维护答案(应该属于离线维护 mex 的基本操作)。

复杂度

期望得分:70分

做法 #3

单调队列维护被扔出去的元素。

期望得分:100分

用数组 T 了很多发,换 bitset 居然 A 了。 (然而坊间传言说 int 数组存 flag 会比较快)

代码

  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
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <bitset>
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;
    }
}
using IO::read;
using IO::init_case;
using IO::update_ans;
const int SIZ = 1e6 + 2007;
int M, A, B, D, P[SIZ], M2;

typedef unsigned int uint32;
uint32 ans_sum0, ans_sum1;

queue<int> dq;
int mq[SIZ<<1]; int hd, ta;
bitset<(SIZ<<1)> vis; int vpos = 0;
bitset<(SIZ<<1)> in;

#define query_mex() \
    (hd == ta ? 0x7FFFFFFF : mq[hd])

void solve() {
    dq = queue<int>();
    hd = ta = 0;
    vis = 0; in = 0;
    vpos = 0;

    for(int i=0;i<=A;i++)
        in[i] = vis[i] = 1;
    vpos = A+1;

    for(int i=1;i<=M;i++) {
        if(P[i] == -1) {
            if(dq.empty()) {
                update_ans(ans_sum0, 0, i);
                update_ans(ans_sum1, 0, i);
            } else {
                int x = dq.front();
                in[x] = 1;
                if(hd < ta && mq[hd] == x) hd++;
                dq.pop();
                update_ans(ans_sum0, min(query_mex(), vpos), i);
                update_ans(ans_sum1, 0, i);
            }
        } else {
            if(!vis[P[i]]) {
                vis[P[i]] = in[P[i]] = 1;
                while(vis[vpos]) vpos++;
                update_ans(ans_sum0, min(query_mex(), vpos), i);
                update_ans(ans_sum1, vpos, i);
            } else if(in[P[i]]) {
                in[P[i]] = 0;
                while(hd < ta && mq[ta-1] > P[i]) ta--;
                mq[ta++] = P[i];
                dq.push(P[i]);
                update_ans(ans_sum0, min(query_mex(), vpos), i);
                update_ans(ans_sum1, 0, i);
            } else {
                if(dq.empty()) {
                    update_ans(ans_sum0, 0, i);
                    update_ans(ans_sum1, 0, i);
                } else {
                    int x = dq.front();
                    in[x] = 1;
                    if(hd < ta && mq[hd] == x) hd++;
                    dq.pop();
                    update_ans(ans_sum0, min(query_mex(), vpos), i);
                    update_ans(ans_sum1, 0, i);
                }
            }
        }
    }
}

int T;
int main() {
    scanf("%d", &T);
    while(T--) {
        init_case(M, A, B, D, P);
        M2 = M<<1;
        ans_sum0 = ans_sum1 = 0;
        solve();
        printf("%u\n", (D ? ans_sum1 : ans_sum0));
    }
}