[Ynoi2016]掉进兔子洞

洛咕

题意:一个长为\(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<=100000,1<=a[i]<=1000000000\).

分析:首先\(a[i]\)肯定要离散化,但是本题的离散化有个特点,设每个数出现了\(cnt_i\)次,则\(a[i]\)占据的是从所有比它小的数的个数\(sum+1\)到\(sum+cnt_i\)这一段区间,它们的值都是\(sum+1\).因为\(\sum cnt_i=n\),所以这样离散化后每个元素的值还是在\(n\)的范围内.那么如何实现这一点呢,其实就是离散化的时候不要\(unique\),\(sort\)之后直接\(lower\)_\(bound\)即可.

对于本题这种很多个区间内一些元素个数的维护,不难想到莫队.毕竟莫队的模板题小Z的袜子就是这样一种题型.

所以老套路,把长度为n的序列,分成\(unit=\sqrt n\)块,然后把所有询问的区间\(3m\)个,以\(l\)为第一关键字,\(r\)为第二关键字从小到大排序.接下来考虑如何统计答案.

首先对于每一个询问\(i\),\(ans=r1-l1+1+r2-l2+1+r3-l3+1-3*num\).其中\(num\)表示删掉的元素的个数.所以只要考虑如何求\(num\).

对每一个询问开一个长度为\(N\)的\(bitset\),每一位是否为1表示当前这个询问是否删这个数(显然,M个长度为N的bitset还是会爆空间,所以考虑把M个询问拆成几个部分.)设\(sum[i]\)表示离散化后\(i\)这个数在当前区间内出现的次数,然后实时维护另一个\(bitset\):\(now\),每一位是否为1表示当前这个区间是否有这个数.

一个询问如果要删这个数,就是这个询问的三个区间的\(now\)取交(即&运算).之所以这里统计答案能够如此简单,就是因为我们之前的离散化,保证了相同的数在\(bitset:now\)上占据了一段区间,那么三个取&,就是取最短的那一段区间,是符合题意的.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=100005;
const int M=25005;
int a[N],b[N],bel[N],sum[N],ans[N],visit[N];
struct query{int l,r,id;}q[N];
inline bool cmp(query x,query y){return bel[x.l]==bel[y.l]?x.r<y.r:x.l<y.l;}
bitset<N>s[M],now;//NM/8个字节,不会爆
inline void solve(int m){
    int tot=0;
    memset(sum,0,sizeof(sum));//忘记初始化这个数组,调了半个小时
    for(int i=1;i<=m;++i){
        visit[i]=0;ans[i]=0;//初始化
        for(int j=1;j<=3;++j){
            q[++tot].l=read();q[tot].r=read();q[tot].id=i;
            ans[i]+=q[tot].r-q[tot].l+1;
        }
    }
    sort(q+1,q+tot+1,cmp);now.reset();int l=1,r=0;
    for(int i=1;i<=tot;++i){
//四个while的顺序,先扩大区间,即l--和r++,再考虑缩小区间,即l++和r--.
//刚开始这里随便写的,调了一下午,一直RE
        while(l>q[i].l)--l,now[a[l]+sum[a[l]]]=1,++sum[a[l]];
        while(r<q[i].r)++r,now[a[r]+sum[a[r]]]=1,++sum[a[r]];
        while(r>q[i].r)--sum[a[r]],now[a[r]+sum[a[r]]]=0,--r;
        while(l<q[i].l)--sum[a[l]],now[a[l]+sum[a[l]]]=0,++l;
        if(!visit[q[i].id])visit[q[i].id]=1,s[q[i].id]=now;//这个询问之前没访问过,先直接赋值
        else s[q[i].id]&=now;//否则取交
    }
    for(int i=1;i<=m;++i)printf("%d\n",ans[i]-3*(int)s[i].count());
}
int main(){
    int n=read(),m=read(),unit=sqrt(n);
    for(int i=1;i<=n;++i)a[i]=read(),b[i]=a[i],bel[i]=i/unit+1;
    sort(b+1,b+n+1);for(int i=1;i<=n;++i)a[i]=lower_bound(b+1,b+n+1,a[i])-b;//离散化
    while(m){if(m<=25000)solve(m),m=0;else solve(25000),m-=25000;}//分成每个部分25000个询问来做
    return 0;
}

[Ynoi2016]掉进兔子洞

原文：https://www.cnblogs.com/PPXppx/p/11715631.html