bzoj 3236: [Ahoi2013]作业 （莫队+分块）

Description

Input

Output

Sample Input

Sample Output

HINT

N=100000,M=1000000

Source

By wangyisong1996加强数据

题解：莫队+分块

对于权值也进行分块，这样修改就变成了O(1),查询就是O(sqrt(n))

#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>#define N 1000003using namespace std;int n,m,belong[N],a[N],cnt[N],num[N],v[N],mark[N],block;struct data{	int l,r,a,b,id;	data(int L=0,int R=0,int A=0,int B=0,int ID=0) {		l=L,r=R,a=A,b=B,id=ID;	};}q[N],ans[N];int cmp(data a,data b){	return belong[a.l]<belong[b.l]||belong[a.l]==belong[b.l]&&a.r<b.r;}void change(int pos,int val){	int t=a[pos];	cnt[t]+=val; num[belong[t]]+=val;	if (val==-1&&!cnt[t]) v[belong[t]]--;	if (val==1&&cnt[t]==1) v[belong[t]]++;}data query(int l,int r){	int t=0; int t1=0;	if (belong[l]==belong[r]) {		int t=0; int t1=0;		for (int i=l;i<=r;i++)		 if (cnt[i]) t1++,t+=cnt[i];		return data(t,t1,0,0);	}	for (int i=l;i<=belong[l]*block;i++) 	 if (cnt[i]) t1++,t+=cnt[i];	for (int i=(belong[r]-1)*block+1;i<=r;i++)	 if (cnt[i]) t1++,t+=cnt[i];	for (int i=belong[l]+1;i<belong[r];i++)	 t1+=v[i],t+=num[i];	return data(t,t1,0,0);}int main(){	freopen("a.in","r",stdin);	scanf("%d%d",&n,&m);	for (int i=1;i<=n;i++) scanf("%d",&a[i]);	block=ceil(sqrt(n));	for (int i=1;i<=n;i++) belong[i]=(i-1)/block+1;	for (int i=1;i<=m;i++) scanf("%d%d%d%d",&q[i].l,&q[i].r,&q[i].a,&q[i].b),q[i].id=i; 	sort(q+1,q+m+1,cmp);	int l=1,r=1; change(1,1);	for (int i=1;i<=m;i++) {		while (q[i].l<l) change(--l,1);		while (q[i].l>l) change(l++,-1);		while (q[i].r>r) change(++r,1);		while (q[i].r<r) change(r--,-1);		ans[q[i].id]=query(q[i].a,q[i].b);	}	for (int i=1;i<=m;i++) 	 PRintf("%d %d/n",ans[i].l,ans[i].r);}