题目链接
题意分析
尽管是莫队题 但是对于我来说 也是一道bitset入手题
这道题就是 三个区间元素总个数-3*区间元素重复个数
对于区间元素的个数操作 很容易想到使用莫队算法
求区间元素重复个数 也就是区间的交 这个时候我们可以使用bitset
首先 由于(ai≤10^9) 所以我们需要离散化 但是不可以使用去重操作 因为我们需要统计个数
比如说 我们原始为1,1,2,2,3,3,3
离散化之后就是1,1,2,2,4,4,4
这样的话我们就可以很轻松的使用当前个数把他们对应到bitset去
bitset 的长度就是n 每一位代表当前这一位的数字是否有包含在区间里 从而用于求交
但是我们需要注意的是 如果对于m次询问 每一个都开一个n位的bitset的话
由于(n,m≤10^5) 所以妥妥的MLE
所以我们考虑使用分组处理询问 使得bitset可以被多次利用 从而达到节约空间的效果
CODE:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<bitset>
#define N 100080
#define M 18000
using namespace std;
int n,m,tot,sqt;
int num[N],res[N],at[N],ans[N];
bitset<N> cnts[M+10],now;
int cnt[N],le1[N],le2[N],le3[N],ri1[N],ri2[N],ri3[N];
bool vis[N];
struct Query
{
int id,le,ri;
friend bool operator <(const Query &A,const Query &B)
{return at[A.le]==at[B.le] ? A.ri<B.ri : at[A.le]<at[B.le];}
}qe[N<<2];
void update(int nowat,int d)
{
if(d>0) now[num[nowat]+cnt[num[nowat]]]=1;
if(d<0) now[num[nowat]+cnt[num[nowat]]-1]=0;
cnt[num[nowat]]+=d;
}
void solve(int le,int ri)
{
for(int i=1;i<=n;++i) cnt[i]=0;
for(int i=1;i<=m;++i) vis[i]=0;
now.reset();
int lenow=1,rinow=0;tot=0;
for(int i=le;i<=ri;++i)
{
qe[++tot]=(Query){i,le1[i],ri1[i]},ans[i]+=ri1[i]-le1[i]+1;
qe[++tot]=(Query){i,le2[i],ri2[i]},ans[i]+=ri2[i]-le2[i]+1;
qe[++tot]=(Query){i,le3[i],ri3[i]},ans[i]+=ri3[i]-le3[i]+1;
}
sort(qe+1,qe+tot+1);
for(int i=1;i<=tot;++i)
{
while(rinow<qe[i].ri) update(++rinow,1);
while(lenow>qe[i].le) update(--lenow,1);
while(lenow<qe[i].le) update(lenow++,-1);
while(rinow>qe[i].ri) update(rinow--,-1);
if(!vis[qe[i].id-le+1]) vis[qe[i].id-le+1]=1,cnts[qe[i].id-le+1]=now;
else cnts[qe[i].id-le+1]&=now;
}
for(int i=le;i<=ri;++i) ans[i]-=cnts[i-le+1].count()*3;
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>m;sqt=sqrt(n*1.0);
for(int i=1;i<=n;++i) cin>>num[i],res[i]=num[i];
sort(res+1,res+n+1);
for(int i=1;i<=n;++i) num[i]=lower_bound(res+1,res+n+1,num[i])-res;
for(int i=1;i<=n;++i) at[i]=i/sqt+1;
for(int i=1;i<=m;++i)
{
cin>>le1[i]>>ri1[i];
cin>>le2[i]>>ri2[i];
cin>>le3[i]>>ri3[i];
}
for(int i=1;i<=m;i+=M) solve(i,min(m,i+M-1));
for(int i=1;i<=m;++i) printf("%d
",ans[i]);
return 0;
}