【[HEOI2012]采花】

\(HH\)的项链加强版，数据范围和题意都加强了

题意大概：给出n个数，求区间出现次数>=2的数的个数。

一眼莫队，可是我还不会莫队啊

那就树状数组吧

回忆一下\(HH\)的项链，套路差不多，那道题我们维护的是每一种颜色最后出现的位置，因为根据其最后出现的位置我们就可以判断其是否在区间里

而判断这道题也很简单，我们维护每一个颜色倒数第二次出现是在什么位置，这样就能判断其是否出现次数大于等于二了

还是离线+树状数组就可以啦

代码

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#define re register

#define lowbit(x) ((x)&(-x))

#define maxn 2000005

inline int read()

{

	char c=getchar();

	int x=0;

	while(c<'0'||c>'9') c=getchar();

	while(c>='0'&&c<='9')

		x=(x<<3)+(x<<1)+c-48,c=getchar();

	return x;

}

int c[2][maxn];

int n,m,T;

struct Ask

{

	int l,r,rk;

}q[maxn];

inline int cmp(Ask K,Ask M)

{

	return K.r<M.r;

}

inline void add(int x,int o,int val)

{

	for(re int i=x;i<=n;i+=lowbit(i))

		c[o][i]+=val;

}

inline int ask(int x,int o)

{

	int ans=0;

	for(re int i=x;i;i-=lowbit(i))

		ans+=c[o][i];

	return ans;

}

int a[maxn],pre[maxn],col_p[maxn],Ans[maxn];

int main()

{

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

	for(re int i=1;i<=n;i++) a[i]=read();

	for(re int i=1;i<=m;i++)

		q[i].l=read(),q[i].r=read(),q[i].rk=i;

	std::sort(q+1,q+m+1,cmp);

	for(re int i=1;i<=n;i++)

		pre[i]=col_p[a[i]],col_p[a[i]]=i;

	int now=1;

	for(re int i=1;i<=n;i++)

	{

		if(!pre[i]) add(i,0,1);

		else

		{

			if(!pre[pre[i]]) add(i,0,1),add(pre[i],1,1),add(pre[i],0,-1);

			else

			{

				add(i,0,1),add(pre[i],0,-1);

				add(pre[i],1,1),add(pre[pre[i]],1,-1);

			}

		}

		while(i==q[now].r) Ans[q[now].rk]=ask(q[now].r,1)-ask(q[now].l-1,1),now++;

	}

	for(re int i=1;i<=m;i++)

		printf("%d\n",Ans[i]);

	return 0;

}

巴特西

【[HEOI2012]采花】

最新文章

热门文章