P4688 掉进兔子洞

题面

原题链接 click

题解

莫队配合 \(\mathrm{bitset}\) 板子题。
显然六维莫队过不去。
然后先考虑简单情形：如果 \(a\) 是排列，那么我直接开 \(3\) 个 \(\mathrm{bitset}\) 然后 \(\mathrm{\&}\) 一下就完事了。我们开 \(3m\) 个 \(\mathrm{bitset}\)，然后莫队处理，最后按位与，时间复杂度 \(O(\frac{nm}w)\)。
然后如果 \(a\) 中有重复数字，假设 \(u\) 出现 \(v\) 次，那么我在 \(\mathrm{bitset}\) 开 \(v\) 个位置，然后如果当前有 \(k\) 个就把 \(1,2,\cdots,k\) 个位置设为 \(1\)。
还有一个小问题，就是 \(O(\frac{nm}w)\) 的空间无法接受。
不过解决方案也简单，每次处理 \(\frac1t\) 询问即可，在 \(t\) 较小时不影响时间复杂度。

Code

#include<bits/stdc++.h>
using namespace std;
const int lim=8000;
const int Div=100000/sqrt(lim+0.5);
bitset<100000>d[lim*3+5],nw;
int memory[200005];
int *p[100005];
int a[100005];
int tmp[100005];
int t[100005];
int n,q;
struct node{
    int l,r;
    int id;
};
node s[lim*3+5];
bool cmp(node x,node y){
    if(x.l/Div!=y.l/Div) return x.l<y.l;
    return x.r<y.r;
}
void solve(){
    nw.reset();
    memset(t,0,sizeof(t));
    sort(s+1,s+1+q,cmp);
    int nl=1,nr=0;
    for(int i=1;i<=q;i++){
        while(nr<s[i].r){
            nr++; t[a[nr]]++; nw[p[a[nr]][t[a[nr]]]]=1;
        }
        while(nl>s[i].l){
            nl--; t[a[nl]]++; nw[p[a[nl]][t[a[nl]]]]=1;
        }
        while(nr>s[i].r){
            nw[p[a[nr]][t[a[nr]]]]=0; t[a[nr]]--; nr--;
        }
        while(nl<s[i].l){
            nw[p[a[nl]][t[a[nl]]]]=0; t[a[nl]]--; nl++;
        }
        d[s[i].id]=nw;
    }
    for(int i=1;i<=q;i+=3){
        int u=d[i].count(),v=d[i+1].count(),w=d[i+2].count(),h=(d[i]&d[i+1]&d[i+2]).count();
        // cerr<<u<<' '<<v<<' '<<w<<'\n';
        cout<<u+v+w-h-h-h<<'\n';
    }
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) tmp[i]=a[i]; 
    sort(tmp+1,tmp+1+n);
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(tmp+1,tmp+1+n,a[i])-tmp; t[a[i]]++;
    }
    int cnt=0;
    p[0]=memory;
    for(int i=1;i<=n;i++){
        p[i]=p[i-1]+t[i-1]+1;
        for(int j=1;j<=t[i];j++) p[i][j]=cnt++;
    }
    // for(int i=1;i<=n;i++) cerr<<a[i]<<' '; cerr<<'\n';
    // for(int i=1;i<=n;i++){
    //     for(int j=1;j<=t[i];j++) cerr<<p[i][j]<<' '; cerr<<'\n';
    // }
    while(m--){
        int l1,r1,l2,r2,l3,r3; cin>>l1>>r1>>l2>>r2>>l3>>r3;
        q++; s[q]={l1,r1,q}; q++; s[q]={l2,r2,q}; q++; s[q]={l3,r3,q};
        if(m%lim==0){
            solve(); q=0;
        }
    }
    return 0;
}