「雅礼集训2018Day2」颜色

发表于 | 更新于 | 分类于 | 阅读次数：

所以这个题场上没写出来就是完全蠢了吧……

而且为啥加了各种优化还是跑不过最优解……

[LOJ 6499]

题意简述

给定一个长 $n$ 的整数序列， $m$ 次询问，每次给定 $k_i$ 个区间 $[i_{i,j},r_{i,j}]$ ，求这些区间中一共出现了多少种不同的数字。

部分数据强制在线。 $1\le n,m,a_i,\sum k_i\le 10^5$ 。

ML : 8MiB, TL : 1000ms.

主要思路

对序列分块。设分成 $K$ 块。

考虑如何记录答案。一个比较显然的想法是对每个块记录一个 bitset 来表示这个块有哪些数，询问就暴力把所有块或起来。

这样做出一个总时间复杂度 $O(n(\dfrac{nK}{\omega}+\dfrac{n}{K}))$ ，空间复杂度 $O(K\dfrac{n}{\omega})$ 的垃圾，然后跑得比暴力还慢。

然后发现可以用 $K^2$ 个 bitset 来维护两个块之间有哪些数，时间复杂度 $O(\dfrac{n^2}{K})$ 但是空间 $O(K^2\dfrac{n}{\omega})$ 。发现如果这样 $K$ 只能开几十，然后也跑得慢得一批。

考虑如何保持快速求出两个块之间答案的同时减少需要的空间。接下来就是本题最神仙的思路：可以使用一个ST表来维护两个块之间的答案。

这样总时间复杂度变为 $O(n(\dfrac{n}{\omega}+\dfrac{n}{K}))$ ，空间复杂度降至 $O(\dfrac{n}{\omega}\times K\log_2 K)$ ， $K$ 可以开到一百，手写个 bitset 大概就能过了。

参考代码

主要有两个优化：

首先， $k_i$ 个区间先排个序，然后取并集，再把并集分成互不相交的若干个区间来做，具体详见代码。

其次，可以把序列中只出现一次的数丢出来做一个前缀和，不加到 bitset 里，询问一个区间把前缀和直接加到答案。这样 bitset 的长度减小到原来的 $\dfrac{1}{2}$ 。

代码可读性极差
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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#define __AVX__ 1
#define __AVX2__ 1
#define __SSE__ 1
#define __SSE2__ 1
#define __SSE2_MATH__ 1
#define __SSE3__ 1
#define __SSE4_1__ 1
#define __SSE4_2__ 1
#define __SSE_MATH__ 1
#define __SSSE3__ 1
// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
//神奇优化 
#include<bits/stdc++.h>
namespace my_std{
    using namespace std;
    #define reg register
    #define Rint register int
    #define FOR(i,a,b) for(register int i=(a),ed_##i=(b);i<=ed_##i;++i)
    #define ROF(i,a,b) for(register int i=(a),ed_##i=(b);i>=ed_##i;--i)
    #define FORit(templ,arr,i,a,b) for(register templ *i=(arr)+(a),*ed_##i=(arr)+(b)+1;i!=ed_##i;++i)
    #define ROFit(templ,arr,i,a,b) for(register templ *i=(arr)+(a),*ed_##i=(arr)+(b)-1;i!=ed_##i;--i)
    #define GO(x,p,e,i,v) for(register int i=p[x].head,v;i;i=e[i].link)
    #define MEM(x,v) memset(x,v,sizeof(x))
    #define fir first
    #define sec second
    #define pq priority_queue
    #define MP make_pair
    typedef long long LL;
    typedef unsigned long long uLL;
    typedef double DB;
    typedef pair<int,int> PII;
    #define Templ(T) template<typename T>
    inline int read(){
        Rint ans=0,f=1;reg char c=getchar();
        while(!isdigit(c)){ f^=(c=='-'); c=getchar(); }
        for(;isdigit(c);c=getchar()) ans=ans*10+c-'0'; return f?ans:-ans;
    }
    Templ(_Tp) inline int chkmin(_Tp &x,_Tp y){ return x>y?x=y,1:0; }
    Templ(_Tp) inline int chkmax(_Tp &x,_Tp y){ return x<y?x=y,1:0; }
    #define using_mod
    const int mod = 998244353, N = 100010, MX = 100000, BC = 145, ToT = 782;
    #ifdef using_mod
    inline void inc(int &x,const int &y){ x+=y; if(x>=mod) x-=mod; }
    inline int ksm(int x,LL y){ int res=1; for(;y;y>>=1,x=1ll*x*x%mod) if(y&1) res=1ll*res*x%mod; return res;}
    #endif
    Templ(_Tp) inline _Tp gcd(_Tp x,_Tp y){ return y?gcd(y,x%y):x; }
    #define FILE(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
    #define PBTXDY
}
using namespace my_std;

struct my_bitset{
    uLL val[ToT];
    inline void operator |= (const my_bitset &A){ FOR(i, 0, ToT - 1) val[i] |= A.val[i]; }
    inline my_bitset operator | (const my_bitset &A)const{
        my_bitset res;
        FOR(i, 0, ToT - 1) res.val[i] = val[i] | A.val[i];
        return res;
    }
    inline void set(int k){
        val[k >> 6] |= (1ull << (k & 63));
    }
    inline void reset(){ FOR(i, 0, ToT - 1) val[i] = 0; }
    inline int count(){ Rint res = 0; FOR(i, 0, ToT - 1) res += __builtin_popcountll(val[i]); return res; }
}st[BC][8], ans;
//手写 bitset 

int n, m, datatype, a[N], bl[N], loog[BC], blo, bcnt, cnt[N], real_num[N], rcnt, S[N];
int Blo_L[BC], Blo_R[BC];
struct Query{
    int l, r;
    inline bool operator < (const Query &A)const{ return r == A.r ? l < A.l : r < A.r ; }
}Q[N], RQ[N], *rtop;

int main(){
    Rint lastans = 0;
    n = read(), m = read(), datatype = read(), blo = ceil(n / 140.0);
    Rint cb = 1, qk;
    FOR(i, 1, n) cnt[a[i] = read()]++;
    FOR(i, 1, MX) real_num[i] = cnt[i] > 1 ? rcnt++ : -1;
    FOR(i, 1, n){
        S[i] = S[i - 1] + (cnt[ a[i] ] == 1);
        a[i] = real_num[ a[i] ];
        bl[i] = (i % blo) ? cb : cb++;
        if(a[i] != -1) st[ bl[i] ][0].set(a[i]);
    }
    //把数量是 1 的数扔出来搞个前缀和 
    bcnt = bl[n], cb = -1;
    FOR(i, 1, bcnt){
        Blo_L[i] = (i - 1) * blo + 1;
        Blo_R[i] = (i == bcnt) ? n : i * blo ;
        if(i == 1) continue;
        loog[i] = loog[i >> 1] + 1;
    }
    FOR(i, 1, loog[bcnt]){
        FOR(j, 1, bcnt - (1 << i) + 1) st[j][i] = st[j][i - 1] | st[j + (1 << (i - 1))][i - 1];
    }
    FOR(qry, 1, m){
        ans.reset(), qk = read();
        FORit(Query, Q, i, 0, qk - 1){
            i->l = read(), i->r = read();
            if(datatype && qry > 1){
                i->l = (i->l ^ lastans) % n + 1, i->r = (i->r ^ lastans) % n + 1;
                if(i->l > i->r) swap(i->l, i->r);
            }
        }
        if(qk > 1) sort(Q, Q + qk);
        *(rtop = RQ) = Q[0];
        FORit(Query, Q, i, 1, qk - 1){
            if(rtop->r == i->r && rtop->l <= i->l) continue;
            while(rtop != RQ - 1 && rtop->l >= i->l) --rtop;
            if(rtop != RQ - 1 && rtop->r >= i->l) rtop->r = i->r;
            else *(++rtop) = *i;
        }//把 k 个区间排序再把这些区间的并分为不交的区间 
        Rint l, r, lb, rb, k_k;
        lastans = 0;
        FORit(Query, 0, i, RQ, rtop){
            l = i->l, r = i->r, lb = bl[l], rb = bl[r];
            lastans += S[r] - S[l - 1];
            if(lb == rb){
                FOR(i, l, r) if(a[i] != -1) ans.set(a[i]);
            }
            else{
                FOR(i, l, Blo_R[lb]) if(a[i] != -1) ans.set(a[i]);
                FOR(i, Blo_L[rb], r) if(a[i] != -1) ans.set(a[i]);
                k_k = loog[rb - lb - 1];
                if(lb + 1 <= rb - 1) ans |= st[lb + 1][k_k] | st[rb - (1 << k_k)][k_k];
            }
        }
        printf("%d\n", lastans += ans.count());
    }
    return 0;
}