[平衡結合][分塊莫隊]Gty的二逼妹子序列

bzoj3809

常見的平衡結合思想，用權值分塊優化使莫隊的add 和 del 操作變為 O ( 1 ) O(1) O(1)，相應的，query變為 O ( s q r t ( n ) ) O(sqrt(n)) O(sqrt(n))

Code:

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int res=0,f=1;char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-') f=-f;ch=getchar();}
	while(isdigit(ch)) {res=(res<<1)+(res<<3)+(ch^48);ch=getchar();}
	return res*f;
}
const int N=100005,M=1000005;
int n,m,sum[N][2],cnt[N],a[N],ans[M],sqr1,sqr2,mx=0;
struct Node{int l,r,a,b,id;}q[M];
inline int idx(int p,int blo){return (p-1)/blo+1;}
inline bool cmp(const Node&a,const Node&b){
	int ia=idx(a.l,sqr1),ib=idx(b.l,sqr1);
	return ia==ib?a.r<b.r:ia<ib;
}
inline void add(int p){
	int val=a[p],blo=idx(val,sqr2);
	++sum[blo][0],++cnt[a[p]];
	if(cnt[a[p]]==1) ++sum[blo][1];
}
inline void del(int p){
	int val=a[p],blo=idx(val,sqr2);
	--sum[blo][0],--cnt[a[p]];
	if(!cnt[a[p]]) --sum[blo][1];
}
inline int query(int val){
	int blo=idx(val,sqr2),ret=0;
	for(int i=blo-1;i;--i) ret+=sum[i][1];
	for(int i=(blo-1)*sqr2+1;i<=val;++i) ret+=cnt[i]?1:0;
	return ret;
}
int main(){
	n=read(),m=read();
	for(int i=1;i<=n;++i) a[i]=read(),mx=max(mx,a[i]);
	sqr1=sqrt(n+0.5),sqr2=sqrt(mx+0.5);
	for(int i=1;i<=m;++i) q[i].l=read(),q[i].r=read(),q[i].a=read(),q[i].b=read(),q[i].id=i;
	sort(q+1,q+m+1,cmp);
	int pl=1,pr=0;
	for(int tt=1;tt<=m;++tt){
		while(pl<q[tt].l) del(pl++);
		while(pl>q[tt].l) add(--pl);
		while(pr<q[tt].r) add(++pr);
		while(pr>q[tt].r) del(pr--);
		ans[q[tt].id]=query(q[tt].b)-query(q[tt].a-1);
	}
	for(int i=1;i<=m;++i) cout<<ans[i]<<'\n';
	return 0;
}