前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >P1972 [SDOI2009]HH的项链 离线树状数组计数

P1972 [SDOI2009]HH的项链 离线树状数组计数

作者头像
用户2965768
发布2019-07-08 18:00:29
4340
发布2019-07-08 18:00:29
举报
文章被收录于专栏:wym

P1972 [SDOI2009]HH的项链

对询问按照右端点排序,然后 计算按照树状数组求和计算 l,r = sum(r) - sum(l-1)

对a[i] = x , vis[x] = i

当值x没出现过 就add(x,1)

出现过,add(vis[x],-1 ) , add(i,1) 

为什么要清除影响,因为你前面先对区间排序, r 递增,计算sum 时递减往前求和

代码语言:javascript
复制
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000005;
struct Q{
	int l,r,id;
}q[maxn];
int a[maxn],s[maxn];int n,m;
int ans[maxn],vis[maxn];
int lowbit(int x){
	return x&(-x);
}
int query(int x){
	int ans = 0;
	while(x>0){
		ans+=s[x];
		x-=lowbit(x);
	}
	return ans;
}
void add(int x,int k){
	while(x<=n){
		s[x]+=k;
		x+=lowbit(x);
	}
}
int cmp(Q c,Q d){
	return c.r<d.r;
}
int main()
{
	
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	scanf("%d",&m);
	for(int i=1;i<=m;i++)scanf("%d %d",&q[i].l,&q[i].r),q[i].id = i;
	sort(q+1,q+m+1,cmp);
	int t=1;
	for(int i=1;i<=n;i++){
		if(!vis[a[i]])add(i,1),vis[a[i]]=i;
		else add(vis[a[i]],-1),add(i,1),vis[a[i]] = i;
		while(q[t].r==i){
			ans[q[t].id] = query(q[t].r) - query(q[t].l-1);
			t++;
		}
	}
	for(int i=1;i<t;i++){
		printf("%d\n",ans[i]);
	}
	return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019年07月04日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档