[Ynoi2016]掉进兔子洞题解

佚名 5年前 (2019-06-11) 算法 1652人围观抢沙发百度已收录

题面传送门：https://www.luogu.org/problemnew/show/P4688
（温馨提示，请直接翻至题目描述部分）

1e5的数据范围，以及对区间每个权值出现次数取min此类主席树才能解决的操作会让我们想到莫队；
三个区间取交集的操作会让我们想到bitset。
然而同个数值在多个位置出现需要分别计算，这点让我们对于使用bitset产生了怀疑。
但实际上我们可以利用一个小trick来解决这个问题，那就是利用不寻常的离散化，就是sort之后不用unique，让bitset每一位不只代表数值，还代表这个数值出现的次数。
这样我们莫队的时候，对于当前区间维护一个桶cnt，记录每个离散化后的权值在此区间出现的次数，和一个bitset，维护权值及权值出现的次数信息。然后三个区间的bitset取交，再用三个区间的长度和减去交集1的个数就是答案。
具体实现请看代码：

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(register int i=(a);i<=(b);++i)
const int N =100505;
const int M =33350;
int n,m,blo[N],K,a[N],R;
struct la{int l,r,id;}ask[N];
bitset<N> ans[M],now;
int cnt[N],p[N],tot;
bool cmp(la x,la y){
    return blo[x.l]==blo[y.l]?x.r<y.r:blo[x.l]<blo[y.l];
}
inline void del(int x){cnt[x]--;now[x-cnt[x]]=0;}
inline void add(int x){now[x-cnt[x]]=1;cnt[x]++;}
void doit(int y){
    tot=0;
    rep(i,1,y)p[i]=0;
    rep(i,1,y){
        ++tot;scanf("%d%d",&ask[tot].l,&ask[tot].r);p[i]+=ask[tot].r-ask[tot].l+1;
        ++tot;scanf("%d%d",&ask[tot].l,&ask[tot].r);p[i]+=ask[tot].r-ask[tot].l+1;
        ++tot;scanf("%d%d",&ask[tot].l,&ask[tot].r);p[i]+=ask[tot].r-ask[tot].l+1;
        ask[tot].id=ask[tot-1].id=ask[tot-2].id=i;
    }
    sort(ask+1,ask+tot+1,cmp);
    int l=1,r=0;
    rep(i,1,y)ans[i].set();//不用带参，直接全置为 1
    rep(i,1,tot){
        while(ask[i].l<l)add(a[--l]);
        while(ask[i].r>r)add(a[++r]);
        while(ask[i].l>l)del(a[l++]);
        while(ask[i].r<r)del(a[r--]);
        ans[ask[i].id]&=now;
    }
    while(l<=r)del(a[l++]);
    rep(i,1,y)printf("%d\n",p[i]-3*(int)ans[i].count());
}
int main(){
    scanf("%d%d",&n,&m);K=sqrt(n)+1;
    rep(i,1,n)scanf("%d",&a[i]),p[i]=a[i],blo[i]=(i-1)/K+1;
    sort(p+1,p+n+1);
    rep(i,1,n)a[i]=upper_bound(p+1,p+n+1,a[i])-p-1;
    R=m/3;
    if(R)doit(R);
    if(R)doit(R);
    doit(m-2*R);
    return 0;
}