4939: [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。

題解

這題看了路牌——莫隊，什麼想法都沒有

三個區間莫什麼隊啊。。

然後我們可以稍作思考，其實答案就是三個區間的個數和-公共部分嘛。。

于是就是要就公共部分

看了看題解，才知道怎麼做。。感覺并不難

公共部分其實我們是可以用bitset來維護的

對于每一個數字，一開始的下标為x

第一次的時候就标記x出現了，第二次标記為x+1出現了。。如此類推

就可以解決一個數字出現多次的情況了。。

然後答案就是三個bitset與一下，看一下1的個數就可以了

然後呢，聽說這題卡常數（其實我覺得這複雜度本來就有點大，但是給了80s的時限還可以吧），于是要手寫bieset

這裡大概說一下手寫的bitset怎麼寫：

bitset其實就是bool數組，但是這樣太大/慢了

我們考慮将bool數組開為int

然後就可以位壓了

每32位壓一壓。。

這一塊一起處理，這樣時空複雜度都是1/32了

CODE：（時空墊底）

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;
typedef unsigned int Int;
const int N= ;
const int M=;//這麼多操作做一次 
int n,m,nn;
int cal[(<<)+];//這個數有多少個 
int belong[N];
struct qa{int x,id;}a[N];
int A[N];//離散化後的數組 
int b[N];
int head[N];//離散化後這個值在哪裡 
inline int read()
{
    int x=,f=;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
bool cmp (qa x,qa y){return x.x<y.x;}
int l1[N],r1[N],l2[N],r2[N],l3[N],r3[N];
int ans[N];
void Init ()
{
    n=read();m=read();nn=sqrt(n);
    for (int u=;u<(<<);u++) cal[u]=cal[u>>]+(u&);
    for (int u=;u<=n;u++) belong[u]=(u-)/nn+;
    for (int u=;u<=n;u++)  {a[u].x=read();a[u].id=u;}
    sort(a+,a++n,cmp);
    int tot=;A[a[].id]=tot;
    for (int u=;u<=n;u++)
    {
        if (a[u].x!=a[u-].x) tot++;
        A[a[u].id]=tot;
    }
    for (int u=;u<=n;u++) b[u]=A[u];
    sort(b+,b++n);
    for (int u=;u<=n;u++)
        if (b[u]!=b[u-])
            head[b[u]]=u;
    for (int u=;u<=m;u++)
    {
        l1[u]=read();r1[u]=read();
        l2[u]=read();r2[u]=read();
        l3[u]=read();r3[u]=read();
        ans[u]=(r1[u]-l1[u]+)+(r2[u]-l2[u]+)+(r3[u]-l3[u]+);
    }
}
struct qq
{
    int l,r,id;
}q[(M+10)*3];int len;
bool cmp1 (qq x,qq y)
{
    return belong[x.l]==belong[y.l]?x.r<y.r:belong[x.l]<belong[y.l];
}
struct bs //手寫bitset 
{
    Int S[];
    inline void vis (int x)//如果之前存在就把它加上，否則減去 
    {S[x>>]^=(U<<(x&));}
    int count ()//有多少個
    {
        int tot=;
        for (int u=;u<=;u++)
            tot=tot+cal[S[u]>>]+cal[S[u]&];
        return tot;
    }
    void clear (){memset(S,,sizeof(S));}
}now,c[M+];
bs operator ^ (bs x,bs y)
{
    bs z;
    for (int u=;u<=;u++)   z.S[u]=(x.S[u]^y.S[u]);
    return z;
}
bs operator & (bs x,bs y)
{
    bs z;
    for (int u=;u<=;u++)   z.S[u]=(x.S[u]&y.S[u]);
    return z;
}
int h[N];//每個位置使用到的下标 
void Del (int x){now.vis(head[x]+h[x]-);h[x]--;}
void Add (int x){h[x]++;now.vis(head[x]+h[x]-);}
void solve1 ()
{
    now.clear();memset(h,,sizeof(h));
    memset(c,,sizeof(c));//全部清為
    int l=,r=;
    sort(q+,q++len,cmp1); 
    /*for (int u=1;u<=len;u++)
        printf("YES:%d %d %d\n",q[u].l,q[u].r,q[u].id);*/

    for (int u=;u<=len;u++)
    {   
        while (l>q[u].l) Add(A[--l]);
        while (l<q[u].l) Del(A[l++]);
        while (r>q[u].r) Del(A[r--]);
        while (r<q[u].r) Add(A[++r]);
        c[q[u].id]=c[q[u].id]&now;
        //printf("%d %d\n",q[u].id,c[q[u].id].count());
    }
}
void solve ()
{
    for (int u=;u<=m;u+=M)
    {
        len=;
        for (int i=u;i<=u+M-;i++)
        {
            if (i>m) break;
            q[++len]=qq{l1[i],r1[i],i-u+1};
            q[++len]=qq{l2[i],r2[i],i-u+1};
            q[++len]=qq{l3[i],r3[i],i-u+1};
        }
        solve1();
        for (int i=u;i<=u+M-;i++)
        {
            if (i>m) break;
            printf("%d\n",ans[i]-*c[i-u+].count());
        }
    }
}
int main()
{
    Init();
    solve();
    return ;
}