BZOJ3236： [AHOI2013]作业

题目描述

传送门

行，我知道是Please contact lydsy2012@163.com!

传送门2

题目分析

这题两问还是非常，emmmm。

首先第一问非常好解决，随便就可以用各种各样的方法求出来。

考虑第二问，明显可以让人想到莫队。通过在颜色上分块就可以快速解决问题。

离散化还是要离散化的，luogu数据比较毒。

是代码呢

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e6+7;
const int inf=1e9+7;
struct Q{
	int l,r,a,b,id,ans1,ans2;
	inline bool operator <(const Q &rhs)const{
		return id<rhs.id;
	}
}q[MAXN];
int L[MAXN],R[MAXN],st[MAXN],sum[MAXN],T[MAXN],sumk[MAXN],belong[MAXN],col[MAXN],change[MAXN];
int n,m,a[MAXN],b[MAXN],t;
inline bool cmp(Q x,Q y){return belong[x.l]==belong[y.l]?x.r<y.r:x.l<y.l;}
inline void add(int x){sum[col[x]]++;sumk[belong[col[x]]]++;if(sum[col[x]]==1) change[belong[col[x]]]++;}
inline void del(int x){sum[col[x]]--;sumk[belong[col[x]]]--;if(sum[col[x]]==0) change[belong[col[x]]]--;}
inline int read()
{
    int x=0,c=1;
    char ch=' ';
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    while(ch=='-')c*=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*c;
}
int main()
{
	n=read();m=read();
	int S=sqrt(n);
	for(int i=1;i<=n;i++) a[i]=b[i]=col[i]=read(),belong[i]=(i-1)/S+1;
	b[n+1]=-1;b[n+2]=inf;
	sort(b+1,b+n+3);
	t=unique(b+1,b+n+3)-b-1;	
	for(int i=1;i<=n;i++) col[i]=lower_bound(b+1,b+t+1,col[i])-b;
	
	for(int i=1;i<=m;i++){
		q[i].id=i;
		q[i].l=read(),q[i].r=read();
		q[i].a=read(),q[i].b=read();
		q[i].a=lower_bound(b+1,b+t+1,q[i].a)-b;
		q[i].b=upper_bound(b+1,b+t+1,q[i].b)-b-1;
	}
	for(int i=1;i<=n;i++) if(!L[belong[i]]) L[belong[i]]=i;
	for(int i=n;i;i--) if(!R[belong[i]]) R[belong[i]]=i;
	sort(q+1,q+m+1,cmp);
	int l=1,r=0;
	for(int i=1;i<=m;i++){
		while(l<q[i].l) del(l++);
		while(l>q[i].l) add(--l);
		while(r<q[i].r) add(++r);
		while(r>q[i].r) del(r--);
		if(q[i].a>q[i].b) continue;
		if(belong[q[i].a]==belong[q[i].b]){
			for(int j=q[i].a;j<=q[i].b;j++) if(sum[j]) q[i].ans1+=sum[j],q[i].ans2++;
			continue;
		}
		for(int j=q[i].a;j<=R[belong[q[i].a]];j++) if(sum[j]) q[i].ans1+=sum[j],q[i].ans2++;
		for(int j=belong[q[i].a]+1;j<belong[q[i].b];j++) q[i].ans1+=sumk[j],q[i].ans2+=change[j];
		for(int j=L[belong[q[i].b]];j<=q[i].b;j++) if(sum[j]) q[i].ans1+=sum[j],q[i].ans2++;
	}
	sort(q+1,q+m+1);
	for(int i=1;i<=m;i++) printf("%d %d
", q[i].ans1,q[i].ans2);
}