洛谷 4688 「Ynoi 2016」掉进兔子洞

说实话的确有点难想的说……
莫队 + bitset 倒是很好想到。

直接莫队 + bitset 只能求出交集的颜色种数而不能直接求交集大小。
考虑同颜色集合的交集，即两者大小中的较小值。

再考虑如何在 bitset 上体现较小值。
也即用集合操作体现较小值。
对于两个数 a,b，构造两个集合 A={x∣x∈Z,1≤x≤a} 和 B={x∣x∈Z,1≤x≤b}。
则显然 |A⋂B|=min(a,b)。

在此题中，每种颜色 x 在 bitset 中占据的位置为 [x,x+cntx)，其中 cntx 表示颜色 x 的出现次数。
这样子就可以了。

还有一个问题就是 bitset 的空间问题。
把询问分三组，每组做一次莫队就行了。

常数极大。
（毕竟是 bitset 科技）

代码：

#include <cstdio>
#include <cmath>
#include <cstring>
#include <bitset>
#include <algorithm>
using namespace std;
const int N = 1e5;
const int MBLK = 33333;
int n,m,a[N + 5],block,pos[N + 5],mblock = MBLK;
int ind[N + 5],cnt[N + 5],len[N + 5];
bitset<N + 5> ans[MBLK + 5],cur;
struct s_query
{
    int l,r,id;
    inline bool operator<(const s_query &o) const
    {
        return pos[l] ^ pos[o.l] ? pos[l] < pos[o.l] : pos[l] & 1 ? r < o.r : r > o.r;
    }
} qry[N + 5];
inline void solve(int m)
{
    memset(cnt,0,sizeof cnt),cur.reset();
    for(register int i = 1;i <= m;++i)
        scanf("%d%d%d%d%d%d",&qry[3 * i - 2].l,&qry[3 * i - 2].r,&qry[3 * i - 1].l,&qry[3 * i - 1].r,&qry[3 * i].l,&qry[3 * i].r),qry[3 * i - 2].id = qry[3 * i - 1].id = qry[3 * i].id = i,
        len[i] = qry[3 * i - 2].r - qry[3 * i - 2].l + 1 + qry[3 * i - 1].r - qry[3 * i - 1].l + 1 + qry[3 * i].r - qry[3 * i].l + 1,ans[i].set();
    sort(qry + 1,qry + 3 * m + 1);
    for(register int i = 1,l = 1,r = 0;i <= 3 * m;++i)
    {
        for(;l > qry[i].l;--l,cur[a[l] + ++cnt[a[l]] - 1] = 1);
        for(;r < qry[i].r;++r,cur[a[r] + ++cnt[a[r]] - 1] = 1);
        for(;l < qry[i].l;cur[a[l] + cnt[a[l]]-- - 1] = 0,++l);
        for(;r > qry[i].r;cur[a[r] + cnt[a[r]]-- - 1] = 0,--r);
        ans[qry[i].id] &= cur;
    }
    for(register int i = 1;i <= m;++i)
        printf("%llu\n",len[i] - 3 * ans[i].count());
}
int main()
{
    scanf("%d%d",&n,&m),block = n / sqrt(mblock);
    for(register int i = 1;i <= n;++i)
        scanf("%d",a + i),ind[i] = a[i],pos[i] = (i - 1) / block + 1;
    sort(ind + 1,ind + n + 1);
    for(register int i = 1;i <= n;++i)
        a[i] = lower_bound(ind + 1,ind + n + 1,a[i]) - ind;
    for(register int p = 1;p <= (m - 1) / mblock + 1;++p)
        solve(min(p * mblock,m) - (p - 1) * mblock);
}