[bzoj1878][SDOI2009]HH的项链_树状数组

时间:2021-10-14 06:11:11

HH的项链 bzoj-1878 SDOI-2009

题目大意:给定一个n个数的序列,m次查询。查询区间数的种类个数。

注释:$1\le n \le 5\cdot 10^4$,$1\le m\le 2\cdot 10^5$。


想法:在线的我不会啊qwq。

我们考虑离线做法,将所有的询问以左端点递增为关键字排序。

nxt数组表示当前位置的数的后面第一个和它相等的位置。

这样我们从1枚举到n,将当前的val[i]--,val[nxt[i]]++。然后查询前缀和相减就可以了。

开始的时候第一个出现的种类为1,其余都是0。

最后,附上丑陋的代码... ...

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 50010
#define M 200010
using namespace std;
struct Node
{
int l,r,id,ans;
}q[M];
int nxt[N<<1],tree[N],a[N],p[1000005],n;
inline bool cmp1(const Node &x,const Node &y)
{
return x.l==y.l?x.r<y.r:x.l<y.l;
}
inline bool cmp2(const Node &x,const Node &y)
{
return x.id<y.id;
}
inline int lowbit(int x) {return x&(-x);}
void update(int x,int val)
{
for(int i=x;i<=n+1;i+=lowbit(i))
{
tree[i]+=val;
}
}
int query(int x)
{
int ans=0;
for(int i=x;i>=1;i-=lowbit(i))
{
ans+=tree[i];
}
return ans;
}
int main()
{
cin >> n ;
int mx=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
mx=max(mx,a[i]);
}
for(int i=n;i>=1;i--)
{
nxt[i]=p[a[i]];
p[a[i]]=i;
}
for(int i=1;i<=mx;i++)
{
if(p[i]) update(p[i],1);
}
int m; 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,cmp1);
int l=1;
for(int i=1;i<=m;i++)
{
while(l<q[i].l)
{
if(nxt[l]) update(nxt[l],1);
update(l,-1);
l++;
}
q[i].ans=query(q[i].r)-query(q[i].l-1);
}
sort(q+1,q+m+1,cmp2);
for(int i=1;i<=m;i++)
{
printf("%d\n",q[i].ans);
}
return 0;
}

小结:离线好强大啊...

[bzoj1878][SDOI2009]HH的项链_树状数组的更多相关文章

  1. &lbrack;BZOJ1878&rsqb;&lbrack;SDOI2009&rsqb; HH的项链 (树状数组)

    link 一道简单题. 不用可持久化. 对于统计颜色个数,可以看与其颜色一样的前一个位置. 设$las(i)$表示其与$i$颜色相等的上一个位置. 则对于二元组$(l,r)$,其答案为$\sum_{i ...

  2. BZOJ 1878&colon; &lbrack;SDOI2009&rsqb;HH的项链 离线树状数组

    1878: [SDOI2009]HH的项链 Time Limit: 1 Sec Memory Limit: 256 MB 题目连接 http://www.lydsy.com/JudgeOnline/p ...

  3. 【BZOJ】1878&colon; &lbrack;SDOI2009&rsqb;HH的项链(树状数组)

    http://www.lydsy.com/JudgeOnline/problem.php?id=1878 我太弱了,看题解才过的. 一开始看到此题,我想了想在线做法,但之后觉得这个想法可能是错的:维护 ...

  4. P1972 &lbrack;SDOI2009&rsqb;HH的项链&lbrack;离线&plus;树状数组&sol;主席树&sol;分块&sol;模拟&rsqb;

    题目背景 无 题目描述 HH 有一串由各种漂亮的贝壳组成的项链.HH 相信不同的贝壳会带来好运,所以每次散步完后,他都会随意取出一段贝壳,思考它们所表达的含义.HH 不断地收集新的贝壳,因此,他的项链 ...

  5. 洛谷P1972 &lbrack;SDOI2009&rsqb;HH的项链(树状数组)

    题目链接: https://www.luogu.org/problemnew/show/P1972 题目描述: HH 有一串由各种漂亮的贝壳组成的项链.HH 相信不同的贝壳会带来好运,所以每次散步完后 ...

  6. bzoj 1878&colon; &lbrack;SDOI2009&rsqb;HH的项链【树状数组】

    对于一个lr,每个颜色贡献的是在(1,r)区间里出现的最右位置,所以记录一个b数组表示当前点这个颜色上一个出现的位置 然后把询问离线,按r升序排序 每次把右端点右移,把这个点在树状数组上+1,并且在当 ...

  7. 洛谷 P1972 &lbrack;SDOI2009&rsqb;HH的项链(树状数组,离线)

    传送门 解题思路 因为是求区间的不同种类数,所以我们用树状数组(貌似并没有什么直接联系) (...表示到) 还是和原来一样,用s[i]来表示a[i-lowbit(i)]...a[i]的种类数. 因为有 ...

  8. 【洛谷P1972】HH的项链 离线&plus;树状数组

    题目大意:静态查询序列区间颜色数. 题解:对于一个查询区间 [l , r] ,若有两个相同颜色的点在这个区间中,则总是取下标靠近端点 r 的颜色计入答案贡献.对于每个下标,记录下在这个下标之前,且距离 ...

  9. &lbrack;bzoj1878&rsqb;&lbrack;SDOI2009&rsqb;HH的项链&lowbar;莫队

    HH 的项链 bzoj-1878 SDOI-2009 题目大意:给定一个n个数的序列.m次询问,每次询问一段区间内数的种类数. 注释:$1\le n\le 5\cdot 10^4$,$1\le m\l ...

随机推荐

  1. Windows Azure 服务器时间问题

    最近一直在做学校的一个小项目,前期在没有服务器端的情况下意淫做出来了手机客户端.在寒假里使用ASP.NET快速做了一个网站并且设计好了需要使用其他内容,在Windows Azure上测试评估,为学校的 ...

  2. POJ3208 Apocalypse Someday&lpar;二分 数位DP&rpar;

    数位DP加二分 //数位dp,dfs记忆化搜索 #include<iostream> #include<cstdio> #include<cstring> usin ...

  3. git&lowbar;sop 脚本使用说明

    tags : git 前言 脚本下载地址: git是功能非常强大的版本管理工具,同时它带来的是学习成本的上升.最近我们团队的部分项目采用了git进行版本管理,一部分小伙伴对于git使用不是很熟悉.一方 ...

  4. 使用clssneme改变图片或样式

    <title>使用className改变样式</title> <style type="text/css"> li{ font-size: 12 ...

  5. svn resolve&sol;merge

    svn merge http://svn.a.com/branches/20150129_168954_sales-impr_1 svn resolve --accept working web/sr ...

  6. Sql Server 2008日志满的解决办法

    通过sql命令 USE ZGZY; GO --由完整模式设置为简单恢复模式 ALTER DATABASE ZGZY SET RECOVERY SIMPLE WITH NO_WAIT GO --收缩日志 ...

  7. CentOS6&period;3重新加载网卡报错 Active connection path&colon; &sol;org&sol;freedesktop&sol;NetworkManager&sol;ActiveConnection

    现象系统无法上网,ping本地127.0.0.1不通,局域网IP也不通,网关也无法ping通 通过 ifconfig 查看网卡和lo回环口 都已启用 重启network服务报错如下: # servic ...

  8. iOS 第三方框架-SDWebImage

    iOS中著名的牛逼的网络图片处理框架.包含的功能:图片下载.图片缓存.下载进度监听.gif处理等等.用法极其简单,功能十分强大,大大提高了网络图片的处理效率.国内超过90%的iOS项目都有它的影子. ...

  9. 30个开源电子商务系统&lpar;PHP&rpar;

    osCommerce osCommerce是一款著名的PHP开源电子商务解决方案,提出“开箱即用”的强大功能,使网上商店安装非常方便快捷,并可以作为GNU通用公共授权的开源项目免费发布.osComme ...

  10. stardog 基本试用&lpar;社区版&rpar;

    stardog 是一个知识图谱的实现,实现了sparql 以及graphql 协议,使用起来也比较简单,官方文档挺全 下载 社区版,注册之后会有邮件通知,里面会包含license 以及软件包 下载地址 ...