https://www.lydsy.com/JudgeOnline/problem.php?id=4939
ans= r1-l1+1 + r2-l2+1 +r3-l3+1 – ∑ min(cnt1[i],cnt2[i],cnt3[i])*3
计算cnt可以用莫队
关键在与如何对3个区间取小
用bitset
假设5个数为 1 5 5 3 3
他们离散化之后为 1 4 4 2 2
那么1对应着bitset的第0位
区间里出现的第一个2对应着bitset的第1位
区间里出现的第二个2对应着bitset的第2位
区间里出现的第一个3对应着bitset的第3位
区间里出现的第二个3对应着bitset的第4位
区间[2,3]的bitset为 0 0 0 1 1
区间[3,4]的bitset为 0 1 0 1 0
这两个bitset执行 & 操作,得到 0 0 0 1 0
1的个数即为 ∑ min(cnt1[i],cnt2[i],cnt3[i])
#include<cmath>
#include<cstdio>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>using namespace std;#define N 100000
#define T 25000int a[N+],b[N+];int S,bl[N+];bitset<N>F[T+],f;int cnt[N+];bool mark[T+];
int ans[T+];struct node
{
int id,l,r;
}e[T*+];void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
}bool cmp(node p,node q)
{
if(bl[p.l]!=bl[q.l]) return bl[p.l]<bl[q.l];
return p.r<q.r;
}void update(int pos,bool ty)
{
int x=a[pos];
if(ty)
{
cnt[x]++;
f[x+cnt[x]-]=;
}
else
{
f[x+cnt[x]-]=;
cnt[x]--;
}
}void solve(int t)
{
int n=;
memset(mark,false,sizeof(mark));
memset(ans,,sizeof(ans));
for(int i=;i<=t;++i)
{
read(e[++n].l); read(e[n].r);
e[n].id=i;
ans[i]+=e[n].r-e[n].l+;
read(e[++n].l); read(e[n].r);
e[n].id=i;
ans[i]+=e[n].r-e[n].l+;
read(e[++n].l); read(e[n].r);
e[n].id=i;
ans[i]+=e[n].r-e[n].l+;
}
sort(e+,e+n+,cmp);
f.reset();
memset(cnt,,sizeof(cnt));
int L=,R=;
for(int i=;i<=n;++i)
{
while(R<e[i].r) update(++R,true);
while(R>e[i].r) update(R--,false);
while(L<e[i].l) update(L++,false);
while(L>e[i].l) update(--L,true);
if(!mark[e[i].id]) F[e[i].id]=f,mark[e[i].id]=true;
else F[e[i].id]&=f;
}
for(int i=;i<=t;++i)
{
ans[i]-=F[i].count()*;
printf("%d\n",ans[i]);
}
}int main()
{
//freopen("xp1.in","r",stdin);
//freopen("xp1.ans","w",stdout);
int n,m;
read(n); read(m);
S=sqrt(n);
for(int i=;i<=n;++i) bl[i]=(i-)/S+;
for(int i=;i<=n;++i) read(a[i]),b[i]=a[i];
sort(b+,b+n+);
for(int i=;i<=n;++i) a[i]=lower_bound(b+,b+n+,a[i])-b;
while(m)
{
if(m<=T) solve(m),m=;
else solve(T),m-=T;
}
return ;
}