BZOJ3236 [Ahoi2013]作业 【莫队+分块】

tonyfang posted @ 2015年8月29日 07:57 in BZOJ with tags c++ OI , 758 阅读
 

Description

 

Input

Output

Sample Input

3 4
1 2 2
1 2 1 3
1 2 1 1
1 3 1 3
2 3 2 3

Sample Output

2 2
1 1
3 2
2 1

HINT

N=100000,M=1000000

Source

【题解】

首先就普通莫队来维护每个块中出现的数的个数和出现的数的值的个数,再用一个数组统计区间内每个数出现的次数,就行了,$O(\sqrt{n})$每次询问,那么总复杂度$O(m\sqrt{n})$,正好够。

 

# include <stdio.h>
# include <math.h> 
# include <algorithm>
using namespace std;
int n,m,t,left=1,right;
int a[100010],cnt[100010],w[100010];
int f[10010],g[10010];
int a1[1000010],a2[1000010];


struct quest {
	int l,r,a,b,id;
	bool operator <(const quest &A) const{
		if (w[l]==w[A.l]) return r<A.r;
		else return l<A.l;
	}
}q[1000010];

inline void xy(int l,int r,int id) {
	if(w[l]==w[r]) {
		for (int i=l;i<=r;++i) if(cnt[i]) a1[id]+=cnt[i],a2[id]++;
	} else {
		for (int i=w[l]*t-1;i>=l;--i) if(cnt[i]) a1[id]+=cnt[i],a2[id]++;
		for (int i=w[r]*t-t;i<=r;++i) if(cnt[i]) a1[id]+=cnt[i],a2[id]++; 
		for (int i=w[l]+1;i<w[r];++i) a1[id]+=f[i],a2[id]+=g[i];
	}
}

inline void u(int x) {
	++f[w[x]];++cnt[x];
	if(cnt[x]==1) g[w[x]]++;
}

inline void v(int x) {
	--f[w[x]];--cnt[x];
	if(cnt[x]==0) g[w[x]]--;
}

int main() {
	scanf("%d%d",&n,&m);
	t=sqrt(n/2);
	for (int i=1;i<=n;++i) scanf("%d",&a[i]),w[i]=i/t+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);
	for (int i=1;i<=m;++i) {
		while(right<q[i].r) u(a[++right]);
		while(left<q[i].l) v(a[left++]);
		while(right>q[i].r) v(a[right--]);
		while(left>q[i].l) u(a[--left]);		
		xy(q[i].a,q[i].b,q[i].id); 
	}
	for (int i=1;i<=m;++i) printf("%d %d\n",a1[i],a2[i]);
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter