说实话的确有点难想的说……
莫队 + bitset 倒是很好想到。
直接莫队 + bitset 只能求出交集的颜色种数而不能直接求交集大小。
考虑同颜色集合的交集，即两者大小中的较小值。
再考虑如何在 bitset 上体现较小值。
也即用集合操作体现较小值。
对于两个数 \(a,b\)，构造两个集合 \(A=\{x\mid x\in \mathbb Z, 1 \le x \le a\}\) 和 \(B=\{x\mid x\in \mathbb Z, 1 \le x \le b\}\)。
则显然 \(\lvert A \bigcap B\rvert = \min(a,b)\)。
在此题中，每种颜色 \(x\) 在 bitset 中占据的位置为 \([x,x+\mathrm{cnt}_x)\)，其中 \(\mathrm{cnt}_x\) 表示颜色 \(x\) 的出现次数。
这样子就可以了。
还有一个问题就是 bitset 的空间问题。
把询问分三组，每组做一次莫队就行了。
常数极大。
（毕竟是 bitset 科技）
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
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);
}