[HEOI2012]采花（树状数组+离线）

听说这题的所发和HH的项链很像。

然而那道题我使用莫队写的。。。

这是一个套路，pre数组加升维（在线）。

记录一个\(pre\)数组，\(pre[i]\)代表上一个和i颜色相同的下标。

我们把询问离线，扫一遍\(a\)数组。然后每扫过一个点，就把\(pre[pre[i]]\)这个位置上减1，把\(pre[i]\)加1。然后每一个询问，就输出\([l,r]\)的权值和就行了。

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<vector>

using namespace std;

const int N=2010100;

typedef pair<int,int> p;

vector<p> vec[N];

int n,c,m,pre[N],last[N];

long long tr[N],ans[N];

int lowbit(int x){

	return x&-x;

}

void add(int x,int w){

	if(x==0)return;

	for(int i=x;i<=n;i+=lowbit(i))tr[i]+=w;

}

int getsum(int x){

	int tmp=0;

	for(int i=x;i;i-=lowbit(i))tmp+=tr[i];

	return tmp;

}

int read(){

	int sum=0,f=1;char ch=getchar();

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

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

	return sum*f;

}

int main(){

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

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

		int a=read();

		pre[i]=last[a];

		last[a]=i;

	}

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

		int l=read(),r=read();

		vec[r].push_back(make_pair(l,i));

	}

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

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

		add(pre[i],1);

		for(int j=0;j<vec[i].size();j++)

			ans[vec[i][j].second]=getsum(i)-getsum(vec[i][j].first-1);

	}

	for(int i=1;i<=m;i++)printf("%lld\n",ans[i]);

	return 0;

}

巴特西

[HEOI2012]采花（树状数组+离线）

最新文章

热门文章