BZOJ 4939 （Ynoi 2016）掉进兔子洞（莫队+压位）

发表于 |
字数统计: 878字 | 阅读时长 ≈ 4min

4939: [Ynoi2016]掉进兔子洞

Description

您正在打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。

Input

第一行两个数表示 n , m。
第二行 n个数表示 a[i]。
之后 m 行，每行 6 个数 l1 , r1 , l2, r2 , l3 , r3 表示这三个区间。

Output

对于每个询问，输出一个数表示答案。

Sample Input

5 2
1 2 2 3 3
1 2 2 3 3 4
1 5 1 5 1 5

Sample Output

3
0

HINT

n , m <= 100000 , 1 <= a[i] <= 1000000000

显然是要求$\sum_{i=1}^{3}(r_i-l_i+1)-\sum_{i=1}^{Max}min(cnt_1[i],cnt_2[i],cnt_3[i])$，$cnt_j[i]表示数字i在区间j中出现次数$

考虑求后面的部分。首先肯定要离散化。
可以将每个询问拆成三个，分别处理出每个区间的$cnt$数组。而$cnt$数组可以用莫队来得到。

现在考虑如何较快的将三个$cnt$取最小后求和。这个可以用$bitset$来做到。
考虑离散化的时候，比如样例1 2 2 3 3，离散化后得到1 2 2 4 4，那么在$bitset$中，就可以用第3个bit位来表示第二个出现的2，用第2个bit位来表示第一个出现的2。然后只需要把三个bitset与起来就得到答案了。

代码：

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
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<bitset>
#include<cmath>
#define N 100005
using namespace std;
const int T=25000;
bitset<100000>F[25001],f;
int n,A[N],B[N],cnt[N],id[N],S,tot,ans[N],Ans[N],TOT;
bool mark[N];
struct node{int l,r,id;}K[N];
bool cmp(node a,node b)
{
    if(id[a.l]==id[b.l])return a.r<b.r;
    return id[a.l]<id[b.l];
}
void UD(int k,int ty)
{
    k=A[k];cnt[k]+=ty;
    if(ty==1)f[k+cnt[k]-2]=1;
    else f[k+cnt[k]-1]=0;
}
void Solve(int m)
{
    int i,j,k,L,R,l1,l2,l3,r1,r2,r3;
    memset(cnt,0,sizeof(cnt));
    memset(mark,0,sizeof(mark));
    f.reset();tot=0;
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d%d%d%d",&l1,&r1,&l2,&r2,&l3,&r3);
        K[++tot]=(node){l1,r1,i};
        K[++tot]=(node){l2,r2,i};
        K[++tot]=(node){l3,r3,i};
        ans[i]=r3+r2+r1-l3-l2-l1+3;
    }
    sort(K+1,K+tot+1,cmp);
    L=1;R=0;
    for(i=1;i<=tot;i++)
    {
        while(R<K[i].r)UD(++R,1);
        while(R>K[i].r)UD(R--,-1);
        while(L<K[i].l)UD(L++,-1);
        while(L>K[i].l)UD(--L,1);
        if(mark[K[i].id])F[K[i].id]&=f;
        else F[K[i].id]=f,mark[K[i].id]=1;
    }
    for(i=1;i<=m;i++)
    {
        k=F[i].count();
        printf("%d\n",ans[i]-3*k);
    }
}
int main()
{
    int i,j,k,m,x,y,l,r;
    scanf("%d%d",&n,&m);S=sqrt(n);
    for(i=j=1;i<=n;i++)scanf("%d",&A[i]),B[i]=A[i],id[i]=i%S?j:j++;
    sort(B+1,B+n+1);
    for(i=1;i<=n;i++)A[i]=lower_bound(B+1,B+n+1,A[i])-B;
    while(m)
    {
        if(m<=T)Solve(m),m=0;
        else Solve(T),m-=T;
    }
}