传送门
解题思路
因为是求区间的不同种类数,所以我们用树状数组(貌似并没有什么直接联系)
(...表示到)
还是和原来一样,用s[i]来表示a[i-lowbit(i)]...a[i]的种类数。
因为有一个类似于去重的操作,所以就有一个数组记录一下is[i]表示编号为i的贝壳上一次出现的地方,每一次更新结果时s[is[i]]--;s[i]++;is[i]=i。
但是我们想,假设询问的一个区间为a...b,下一个区间为a...b-5,并且x这种贝壳在b-3,b-7都出现过(a<b-7<b-5<b-3<b),那么我们在询问a...b时使s[b-7]--;然后再询问a...b-5时就会导致答案出错(少算了一个)。(解释的不太清楚,感性理解一下)
所以这里我们用到一个操作——离线,所谓离线,就是一次性把问题全部输入,根据一定的顺序排序(便于解题),保存好答案后再根据原顺序输出。
怎样用程序实现离线呢?我们可以用结构体来存储数据,每一个结构体变量中有一个保存数值,另一个保存序号,全部读入后按照数值的关键字sort一遍,输出答案前按照关键字序号再sort一遍,这样就达到了目的。
比如说这一道题:
struct ques {
int l,r,ans,id;
} q[maxn];
bool cmp1(ques a,ques b) {
return a.r<b.r;
}
bool cmp2(ques a,ques b) {
return a.id<b.id;
}
int main() {
//读入数据
sort(q+,q+m+,cmp1);//第一遍sort
//求出答案
sort(q+,q+m+,cmp2);//第二遍sort
//输出答案
return ;
}
AC代码
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int maxn=;
int s[maxn],n,a[maxn],m;
int is[maxn*];
inline int lowbit(int x) {
return x&(-x);
}
void insert(int id,int k) {
for(int i=id; i<=n; i+=lowbit(i)) {
s[i]+=k;
}
}
int query(int id) {
int res=;
for(int i=id; i>; i-=lowbit(i)) {
res+=s[i];
}
return res;
}
struct ques {
int l,r,ans,id;
} q[maxn];
bool cmp1(ques a,ques b) {
return a.r<b.r;
}
bool cmp2(ques a,ques b) {
return a.id<b.id;
}
int main() {
cin>>n;
int cnt=;
for(int i=; i<=n; i++) {
scanf("%d",&a[i]);
}
cin>>m;
for(int i=; i<=m; i++) {
scanf("%d%d",&q[i].l,&q[i].r);
q[i].id=i;
}
sort(q+,q+m+,cmp1);
for(int i=; i<=n; i++) {
if(is[a[i]]) {
insert(is[a[i]],-);
}
insert(i,);
is[a[i]]=i;
while(q[cnt].r==i&&cnt<=m) {
q[cnt].ans=query(q[cnt].r)-query(q[cnt].l-);
cnt++;
}
}
sort(q+,q+m+,cmp2);
for(int i=; i<=m; i++) {
printf("%d\n",q[i].ans);
}
return ;
}
洛谷 P1972 [SDOI2009]HH的项链(树状数组,离线)的更多相关文章
-
洛谷 P1972 [SDOI2009]HH的项链——树状数组
先上一波题目 https://www.luogu.org/problem/P1972 这道题是询问区间内不同数的个数 明显不是正常的数据结构能够维护的 首先考虑 因为对于若干个询问的区间[l,r],如 ...
-
【题解】P1972 [SDOI2009]HH的项链 - 树状数组
P1972 [SDOI2009]HH的项链 声明:本博客所有题解都参照了网络资料或其他博客,仅为博主想加深理解而写,如有疑问欢迎与博主讨论✧。٩(ˊᗜˋ)و✧*。 题目描述 \(HH\) 有一串由各种 ...
-
luogu P1972 [SDOI2009]HH的项链 |树状数组 或 莫队
题目描述 HH 有一串由各种漂亮的贝壳组成的项链.HH 相信不同的贝壳会带来好运,所以每次散步完后,他都会随意取出一段贝壳,思考它们所表达的含义.HH 不断地收集新的贝壳,因此,他的项链变得越来越长. ...
-
【bzoj1878】[SDOI2009]HH的项链 - 树状数组 - 离线处理
[SDOI2009]HH的项链 Time Limit: 4 Sec Memory Limit: 64 MBSubmit: 4834 Solved: 2384[Submit][Status][Dis ...
-
BZOJ1878: [SDOI2009]HH的项链[树状数组 离线]
1878: [SDOI2009]HH的项链 Time Limit: 4 Sec Memory Limit: 64 MBSubmit: 3486 Solved: 1738[Submit][Statu ...
-
BZOJ1878: [SDOI2009]HH的项链[树状数组+离线 | 主席树]
题意: 询问区间不同种类颜色数 [2016-11-15] 离线好厉害 对于每一个区间询问,一个数只考虑一次,那么考虑他最后出现的一次 将询问按r排序 从1到n扫描,用树状数组维护一个位置应不应该考虑( ...
-
洛谷——P1972 [SDOI2009]HH的项链(线段树)
P1972 [SDOI2009]HH的项链 HH 有一串由各种漂亮的贝壳组成的项链.HH 相信不同的贝壳会带来好运,所以每次散步完后,他都会随意取出一段贝壳,思考它们所表达的含义.HH 不断地收集新的 ...
-
洛谷 P1972 [SDOI2009]HH的项链-二维偏序+树状数组+读入挂(离线处理,思维,直接1~n一边插入一边查询),hahahahahahaha~
P1972 [SDOI2009]HH的项链 题目背景 无 题目描述 HH 有一串由各种漂亮的贝壳组成的项链.HH 相信不同的贝壳会带来好运,所以每次散步完后,他都会随意取出一段贝壳,思考它们所表达的含 ...
-
洛谷 P1972 [SDOI2009]HH的项链 解题报告
P1972 [SDOI2009]HH的项链 题目描述 HH 有一串由各种漂亮的贝壳组成的项链.HH 相信不同的贝壳会带来好运,所以每次散步完后,他都会随意取出一段贝壳,思考它们所表达的含义.HH 不断 ...
-
洛谷 P1972 [SDOI2009]HH的项链【莫队算法学习】
P1972 [SDOI2009]HH的项链 题目背景 无 题目描述 HH 有一串由各种漂亮的贝壳组成的项链.HH 相信不同的贝壳会带来好运,所以每次散步完后,他都会随意取出一段贝壳,思考它们所表达的含 ...
随机推荐
-
从Bayesian角度浅析Batch Normalization
前置阅读:http://blog.csdn.net/happynear/article/details/44238541——Batch Norm阅读笔记与实现 前置阅读:http://www.zhih ...
-
Window 常用文件
*.msm ntwdblib.dll是一款用于PHP连接MSSQL2005或2008的驱动文件,如果连接BDE的时候出现“cannot load an idapi service liabray fi ...
-
SQL SERVER 2008中输入汉字乱码的问题
搭建服务器时,系统是英文版windows server 2008 ,安装的中文语言包.安装SqlServer2008 后,数据库中文显示乱码. baidu 后,说是 排序规则 的问题.修改为 Chin ...
-
VBA高效删除不连续多行
最近在搞VBA,在感叹Excel功能强大的同时,对于新接触的一门编程语言也很烦恼.很多基础的语法都要靠网上搜索.现总结一些学习到的心得. VBA高效删除不连续多行 在一个拥有几万条数据的Excel中, ...
-
APUE-文件和目录(三)函数chown 和lchown
下面的几个chown函数可用于更改文件的用户ID和组ID.如果两个参数owner或group中的任意一个是-1,则对应的ID不变. #include<unistd.h> int chown ...
-
ArrayList和LinkedList区别及性能测试
ArrayList和LinkedList是Java Lis接口的2个实现.它们的区别如下表所示: 底层结构 强项 弱项 ArrayList 数组 随机访问get和set 插入删除 LinkedList ...
-
CAD 在ARCGIS中的坐标系问题
近期在使用服务(文本写入dxf方式)导出CAD的时候发现导出的CAD文件和原始数据在ArcMap中叠加后不能重合,出现了错位的现象. 查看CAD文件后发现CAD的坐标系及投影和数据不一致导致的.遇到这 ...
-
轻松学C#----第一篇笔记
C#是微软公司推出的一种面向对象的开发语言,于2002年发布,经历了10年的发展,已经广泛应用于各种生产领域.以它为基础语言的ASP.NET已经称为主流网站开发技术.[入门] 共三章: 第一篇:C#概 ...
-
架构模式逻辑层模式之:表模块(Table Model)
表模块和领域模型比,有两个显著区别: 1:表模块中的类和数据库表基本一一对应,而领域模型则无此要求: 2:表模块中的类的对象处理表中的所有记录,而领域模型的一个对象代表表中的一行记录: 一般情况下,我 ...
-
extjs_08_界面布局
watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvYWRhbV93enM=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA ...