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

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

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]);
}
बोर्ड-हिंदी-प्रश्नपत 说:
2023年4月26日 15:57

Hindi Model Question Papers Bihar School 10th Exam Board BSEB, Bihar Board 10th Class Model Papers 2023 Matric Exam Pattern, BSEB Patna Board Matric 10th Model Papers 2023 Sample Questions, Bihar Board 10th Model Papers 2023 Download, बोर्ड-हिंदी-प्रश्नपत्र.com BSEB Matric Bihar matric model paper 2023 bseb 10th sample paper 2023, bihar board 10th model paper 2023 pdf, bihar board 10th class model test paper 2023, bseb matric previous sample paper class 10th bihar board model question paper, bseb matric model question paper 2023.


登录 *


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