题解【[AHOI2013]作业】

\[\texttt{Preface}
\]

数据貌似很水，据说 \(A_i\leq n\) ，连离散化都不需要。

不知道为啥设块大小为 \(\frac{n}{\sqrt m}\) 会一直 Runtime Error on test 1,3,4 ，改成 \(\sqrt n\) 就 \(A\) 了，据说是 \(m=0\) 的问题，但我明明特判了阿 qwq 。

\[\texttt{Description}
\]

给出一个长度为 \(n\) 的序列 \(A\) ，一共 \(m\) 次询问，每次需要回答 " 区间 \([l,r]\) 内有多少个位置上的数的大小在 \([a,b]\) 内" 以及 " 区间 \([l,r]\) 内出现的所有数中，有多少个数的大小在 \([a,b]\) 内 " 。

\[\texttt{Solution}
\]

莫队 \(+\) 树状数组。

我们知道莫队可以解决 " 区间内数的出现次数 " 这类问题。

在上文提到的，\(A_i \leq n\) 。

所以可以直接开个两个桶，c[x][1] 表示值为 \(x\) 的数的出现次数，c[x][2] 表示值为 \(x\) 的数有没有出现过。

然后我们发现每个询问答案要求的其实是 \(\sum\limits_{i=a}\limits^b c[i][1]\) 和 \(\sum\limits_{i=a}\limits^b c[i][2]\) ，本质上是一个区间求和，但是它还需要支持单点修改（插入和删除）。

于是我们可以用一个 支持 \(O(\log n)\) 单点修改以及区间求和的数据结构 维护这两个桶，此时树状数组就是一个不错的选择。

时间复杂度 \(O(n \sqrt n \log n)\) 。

\[\texttt{Code}
\]

#include<cstdio>

#include<algorithm>

#include<cmath>

#define RI register int

using namespace std;

inline int read()

{

	int x=0,f=1;char s=getchar();

	while(s<'0'||s>'9'){if(s=='-')f=-f;s=getchar();}

	while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}

	return x*f;

}

const int N=100100,M=100100,MaxV=100100;

int n,m;

int S;

int block(int x)

{

	return (x-1)/S+1;

}

int a[N];

struct ask{

	int l,r;

	int a,b;

	int id;

	int ans1,ans2;

}q[M];

bool cmp(ask a,ask b)

{

	return block(a.l)==block(b.l)?a.r<b.r:a.l<b.l;

}

bool rebuild(ask a,ask b)

{

	return a.id<b.id;

}

int cnt[MaxV];//再开一个辅助桶便于维护 

int c[MaxV][3];

void BITadd(int x,int t,int val)

{

	for(;x<=n;x+=x&-x)c[x][t]+=val;

}

int BITask(int x,int t)

{

	int ans=0;

	for(;x;x-=x&-x)ans+=c[x][t];

	return ans;

}

void add(int x)

{

	cnt[a[x]]++;

	BITadd(a[x],1,1);

	if(cnt[a[x]]==1)BITadd(a[x],2,1);

}

void sub(int x)

{

	cnt[a[x]]--;

	BITadd(a[x],1,-1);

	if(cnt[a[x]]==0)BITadd(a[x],2,-1);

}

int main()

{

	n=read(),m=read();

	if(!m)

		return 0;

	S=sqrt(n);

	for(RI i=1;i<=n;i++)

		a[i]=read();

	for(RI 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+1+m,cmp);

	int l=1,r=0;

	for(RI i=1;i<=m;i++)

	{

		while(r<q[i].r)add(++r);

		while(r>q[i].r)sub(r--);

		while(l<q[i].l)sub(l++);

		while(l>q[i].l)add(--l);

		q[i].ans1=BITask(q[i].b,1)-BITask(q[i].a-1,1);

		q[i].ans2=BITask(q[i].b,2)-BITask(q[i].a-1,2);

	}

	sort(q+1,q+1+m,rebuild);

	for(RI i=1;i<=m;i++)

		printf("%d %d\n",q[i].ans1,q[i].ans2);

	return 0;

}

\[\texttt{Thanks} \ \texttt{for} \ \texttt{watching}
\]

巴特西

题解【[AHOI2013]作业】

最新文章

热门文章