【卡常 bitset 分块】loj#6499. 「雅礼集训 2018 Day2」颜色

时间:2021-01-27 20:45:58

 好不容易算着块大小,裸的分块才能过随机极限数据;然而这题在线的数据都竟然是构造的……

题目描述

有 $n$ 个数字,第 $i$ 个数字为 $a_i$。

有 $m$ 次询问,每次给出 $k_i$ 个区间,每个区间表示第 $l_{i, j}$ 到 $r_{i, j}$ 的数字,求这些区间中一共出现了多少种不同的数字。

部分数据强制在线。

第一行包含三个整数 $n, m, p$,$p$ 为 $0$ 或 $1$ 表示是否强制在线。

第二行 $n$ 个正整数,第 $i$ 个表示 $a_i$。

接下来依次给出每个询问,每个询问第一行一个正整数,表示 $k_i$,接下来 $k_i$ 行,每行两个正整数,分别表示 $l_{i, j}$ 和 $r_{i, j}$,若 $p = 1$ 且这不是第一个询问,输入的 $l_{i, j}$ 和 $r_{i, j}$ 是经过加密的,你需要将这两个数字分别异或上上一个询问的答案,对 $n$ 取模后再加 $1$,两者较小值为真实的 $l_{i, j}$,较大值为真实的 $r_{i, j}$。

对于全部数据,$1 \leq n, m, \sum k_i, a_i \leq 10^5, 1 \leq l_{i, j} \leq r_{i, j} \leq n$。

  • 子任务 $\rm 1(points:10)$:$n, m, \sum k_i, a_i \leq 5000$
  • 子任务 $\rm 2(points:10)$:$n, m, \leq 5000$
  • 子任务 $\rm 3(points:20)$:$k_i = 1$
  • 子任务 $\rm 4(points:20)$: $p = 0$
  • 子任务 $\rm 5(points:20)$:$1 \leq n, m, \sum k_i, a_i \leq 50000$
  • 子任务 $\rm 6(points:20)$:无特殊限制

题目分析

首先会有一个朴素的分块想法:将序列分块,每个块维护一个bitset。

但是我们会很快意识到bitset一次或操作的复杂度是$O(值域)$的,这么大的复杂度显然我们无法接受。这个想法的最大瓶颈在于中间连续一段bitset的操作复杂度太高。

用以维护分块处理这个瓶颈的方法有两种:线段树/ST表,也就是用基础的区间数据结构来维护一段区间的bitset值。

让我们冷静分析一下这两种方法的复杂度:

我们很容易想到用`bitset`做,先不管空间限制的话会想到这两种方法:

  • 1. 线段树:构造 $O({ n^2\over\omega })​$ ,询问 $O({ n^2\over\omega }log_2n)​$ 。
  • 2. ST表:构造 $O({ n^2\over\omega }log_2n)$ ,询问 $O({ n^2\over\omega })$ 。

都是无法承受的,于是考虑分块来降低复杂度,只记录块之间的信息:

  • 1. 线段树:构造 $O({ n^2\over\omega S })$ ,询问 $O({ n^2\over\omega }log_2{ n\over S }+nS)$ 。
  • 2. ST表:构造 $O({ n^2\over\omega S }log_2{ n\over S })$ ,询问 $O({ n^2\over\omega }+nS)$ 。

发现线段树的那个 $log_2{n\over S}$ 搞不掉,于是gg了,而ST表 $S$ 设置的正常点复杂度都没什么问题。

不过这道题卡内存,所以 $S$ 需要给大点。

这是一个非常规分块的技巧,好像叫四毛子算法?

——摘自ZZK的题解

那么,只需要手写bitset+卡常+分块就可以解决这题了。

 1 #include<bits/stdc++.h>
 2 const int maxn = 100013;
 3 const int maxp = (100000>>5)+3;
 4 const int maxt = (1<<16)-1;
 5 const int maxb = 73;
 6 
 7 int a[maxn],dt[maxn],lg2[maxn],t[maxn],tot;
 8 struct bitset
 9 {
10     unsigned int a[maxp];
11     bitset operator |(bitset b) const
12     {
13         bitset c;
14         for (int i=0; i<=tot; i++)
15             c.a[i] = a[i]|b.a[i];
16         return c;
17     }
18     void reset()
19     {
20         for (int i=0; i<=tot; i++) a[i] = 0;
21     }
22     void set(int x)
23     {
24         a[x>>5] |= 1u<<(x&31);
25     }
26     int count()
27     {
28         int ret = 0;
29         for (int i=0; i<=tot; i++)
30             ret += dt[a[i]>>16]+dt[a[i]&maxt];
31         return ret;
32     }
33 }f[maxb][9],ans;
34 int n,m,p,lastans;
35 int blk[maxn],size,bkTot;
36 
37 int read()
38 {
39     char ch = getchar();
40     int num = 0, fl = 1;
41     for (; !isdigit(ch); ch=getchar())
42         if (ch=='-') fl = -1;
43     for (; isdigit(ch); ch=getchar())
44         num = (num<<1)+(num<<3)+ch-48;
45     return num*fl;
46 }
47 void init()
48 {
49     for (int i=1, Mx=65535; i<=Mx; i++)
50         for (int x=i; x; x&=(x-1)) ++dt[i];
51     for (int i=2, Mx=100000; i<=Mx; i++)
52         lg2[i] = lg2[i>>1]+1;
53 }
54 void deal(int l, int r)
55 {
56     int ls = blk[l], rs = blk[r];
57     if (ls==rs){
58         for (int i=l; i<=r; i++) ans.set(a[i]);
59         return;
60     }
61     for (int i=l; blk[i]==ls; i++) ans.set(a[i]);
62     for (int i=r; blk[i]==rs; i--) ans.set(a[i]);
63     if (ls+1 < rs){
64         int t = lg2[rs-ls-1];
65         ans = ans|f[ls+1][t]|f[rs-(1<<t)][t];
66     }
67 }
68 int main()
69 {
70     n = read(), m = read(), p = read();
71     init(), size = sqrt(1.2*n*log2(n+1)), bkTot = n/size+1;
72     for (int i=1; i<=n; i++)
73         t[i] = a[i] = read(), blk[i] = i/size+1;
74     std::sort(t+1, t+n+1);
75     tot = std::unique(t+1, t+n+1)-t-1;
76     for (int i=1; i<=n; i++)
77         a[i] = std::lower_bound(t+1, t+tot+1, a[i])-t,
78         f[blk[i]][0].set(a[i]);
79     tot >>= 5;
80     for (int j=1; j<=lg2[bkTot]; j++)
81         for (int i=1; i+(1<<j)-1<=bkTot; i++)
82             f[i][j] = f[i][j-1]|f[i+(1<<(j-1))][j-1];
83     for (int tim=0; m; --m, ++tim)
84     {
85         ans.reset();
86         for (int k=read(); k; --k)
87         {
88             int l = read(), r = read();
89             if (p&&tim) l = (l^lastans)%n+1, r = (r^lastans)%n+1;
90             if (l > r) std::swap(l, r);
91             deal(l, r);
92         }
93         lastans = ans.count();
94         printf("%d\n",lastans);
95     }
96     return 0;
97 }

 

END