专栏首页wymP1972 [SDOI2009]HH的项链 离线树状数组计数

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

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 时递减往前求和

#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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Codeforces Round #561 (Div. 2)

    C. 求min(|X-Y|,|X+Y|) <= min(X,Y) <= max(X,Y) <= max(|X-Y|,|X+Y|)

    用户2965768
  • Mato的文件管理 数据离散化+莫队+树状数组求逆序数

    l变化时,区间左边元素,求和减去本身1为逆序数。 即本来有 sum(x) - 1个元素在我后面,现在我在第一个。

    用户2965768
  • ICPC Asia Shenyang 2019 Dudu's maze

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    用户2965768
  • C++ 函数重载

    C++允许用同一个函数名定义多个函数,而这些函数的参数个数和参数类型可以不相同。这就是函数重载。

    chaibubble
  • LeetCode 1030. 距离顺序排列矩阵单元格(排序&Lambda表达式&BFS)

    给出 R 行 C 列的矩阵,其中的单元格的整数坐标为 (r, c),满足 0 <= r < R 且 0 <= c < C。

    Michael阿明
  • Android性能优化实战之界面卡顿

    作者:红橙Darren https://www.jianshu.com/p/18bb507d6e62

    用户1269200
  • 双端队列

    起初用记忆化搜索来写,可以有如下定义f(i, t)表示当前位置下的最小代价,但同时还有前一轮带来的时间总和。

    用户1147447
  • POJ 刷题系列:2993. Emag eht htiw Em Pleh

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 【USACO 1.2】Palindromic Squares

    饶文津
  • 1035. 插入与归并(25)

    插入排序是迭代算法,逐一获得输入数据,逐步产生有序的输出序列。每步迭代中,算法从输入序列中取出一元素,将之插入有序序列中正确的位置。如此迭代直到全部元素有序。

    AI那点小事

扫码关注云+社区

领取腾讯云代金券