「LOJ 6201」「YNOI2016」掉进兔子洞

LOJ #6201

题意

您正在打galgame,然后突然发现您今天太颓了,于是想写个数据结构题练练手:

给出一个长为\(n\)的序列\(a\)

\(m\)个询问,每次询问三个区间,把三个区间中同时出现的数一个一个删掉,问最后三个区间剩下的数的个数和,询问独立。

注意这里删掉指的是一个一个删,不是把等于这个值的数直接删完,比如三个区间是\([1,2,2,3,3,3,3]\),\([1,2,2,3,3,3,3]\)\([1,1,2,3,3]\),就一起扔掉了\(1\)\(1\)\(1\)\(2\)\(2\)\(3\)

\(n,m\le 10^5,a_i\le 10^9\)


分析

询问可以转化为\(3\)个区间的总长度-每个数在三个区间中出现的最小次数的三倍的和。

数字可以离散化

考虑数字至多出现一次的情况

用bitset表示一个区间中每个数是否出现

三个区间的bitset的AND和中\(1\)的个数就是所有数的最小出现次数和。

我们使用莫队来求一个区间的bitset

然后如果有重复数字,我们预留出空位,当数字\(x\)出现了不少于\(y\)次,把bitset的第\(x+y\)位赋成\(1\)

最后统计答案不需要改变

这样bitset的长度恰好是\(n\),可以接受

开不下\(m\)个bitset,那分成若干次处理就好了

复杂度 \(\mathcal O(m\sqrt{n}+\frac{nm}{32})\)


代码

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
#include<cstdio>
#include<algorithm>
#include<ctype.h>
#include<string.h>
#include<math.h>
#include<bitset>

using namespace std;
#define ll long long

inline char read() {
static const int IN_LEN = 1000000;
static char buf[IN_LEN], *s, *t;
return (s==t?t=(s=buf)+fread(buf,1,IN_LEN,stdin),(s==t?-1:*s++):*s++);
}
template<class T>
inline void read(T &x) {
static bool iosig;
static char c;
for (iosig=false, c=read(); !isdigit(c); c=read()) {
if (c == '-') iosig=true;
if (c == -1) return;
}
for (x=0; isdigit(c); c=read()) x=((x+(x<<2))<<1)+(c^'0');
if (iosig) x=-x;
}
const int OUT_LEN = 10000000;
char obuf[OUT_LEN], *ooh=obuf;
inline void print(char c) {
if (ooh==obuf+OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), ooh=obuf;
*ooh++=c;
}
template<class T>
inline void print(T x) {
static int buf[30], cnt;
if (x==0) print('0');
else {
if (x<0) print('-'), x=-x;
for (cnt=0; x; x/=10) buf[++cnt]=x%10+48;
while(cnt) print((char)buf[cnt--]);
}
}
inline void flush() { fwrite(obuf, 1, ooh - obuf, stdout); }

const int N = 100005, M = 40005;
int n, m, len, Ans[M], g[N], a[N], bl[N];
pair<int,int> p[N];
bitset<N> f, ans[M];
struct query{
int l, r, id;
inline bool operator <(const query &rhs)const{
return bl[l]==bl[rhs.l]?r<rhs.r:l<rhs.l;
}
} q[M*3];
inline void ins(int x){ f[++g[x]+x]=1;}
inline void del(int x){ f[g[x]--+x]=0;}
inline void solve(int m){
int cnt=0;
for(int i=0; i<m; ++i){
Ans[i]=0;
read(q[cnt].l), read(q[cnt].r), Ans[i]+=q[cnt].r-q[cnt].l+1;
q[cnt++].id=i;
read(q[cnt].l), read(q[cnt].r), Ans[i]+=q[cnt].r-q[cnt].l+1;
q[cnt++].id=i;
read(q[cnt].l), read(q[cnt].r), Ans[i]+=q[cnt].r-q[cnt].l+1;
q[cnt++].id=i;
ans[i].set();
}
sort(q, q+cnt);
int l=1, r=0;
f.reset(), memset(g, 0, sizeof g);
for(int i=0; i<cnt; ++i){
while(l>q[i].l) ins(a[--l]);
while(r<q[i].r) ins(a[++r]);
while(l<q[i].l) del(a[l++]);
while(r>q[i].r) del(a[r--]);
ans[q[i].id]&=f;
}
for(int i=0; i<m; ++i) print(Ans[i]-ans[i].count()*3), print('\n');
}
int main() {
read(n), read(m);
len=sqrt(n);
for(int i=1; i<=n; ++i)
read(a[i]), p[i]=make_pair(a[i], i), bl[i]=(i+len-1)/len;
sort(p+1, p+n+1);
for(int i=1; i<=n; ++i)
a[p[i].second]=(p[i].first==p[i-1].first?a[p[i-1].second]:i-1);
while(m>0) solve(min(M, m)), m-=M;
return flush(), 0;
}
0%