[洛谷P1972][题解][SDOI2009]HH的项链
2024-08-29 09:00:26
自己还是太蒟了……
看了好久,最后抄参考题解打出来的……
前面的可能影响后面的,所以按照询问右端点排序
这时候维护一个前缀和数组就可以了,
那么问题又来了,去重?
可以这样,从前往后枚举,如果被加过了就在前面去掉
具体看代码(题目毒瘤导致卡常卡了好几遍):
#include<bits/stdc++.h>
#define rint register int
#define lowbit(x) (x&(-x))
using namespace std;
int n,m,t[],a[],vis[],ot[];
inline int rd(){
int x=,f=;
char c=getchar();
while(c<''||c>''){
if(c=='-')f=-;
c=getchar();
}
while(c>=''&&c<=''){
x=x*+c-'';
c=getchar();
}
return x*f;
}
struct Question {
int l,r,id;
}q[];
inline bool cmp(Question a,Question b){
return a.r<b.r;
}
inline void AddPoint(int x,int add){
while(x<=n){
t[x]+=add;
x+=lowbit(x);
}
}
inline int Sum(int x){
int ans=;
while(x){
ans+=t[x];
x-=lowbit(x);
}
return ans;
}
inline int QuerySec(int l,int r){
return Sum(r)-Sum(l-);
}
int main(){
n=rd();
for(rint i=;i<=n;i++)a[i]=rd();
cin>>m;
for(rint i=;i<=m;i++){
q[i].l=rd();
q[i].r=rd();
q[i].id=i;
}
sort(q+,q++m,cmp);
int now=;
for(rint i=;i<=m;i++){
for(rint j=now;j<=q[i].r;j++){
if(vis[a[j]]){//如果加过了
AddPoint(vis[a[j]],-);//去掉
}
AddPoint(j,);//新加上的
vis[a[j]]=j;//标记
}
now=q[i].r+;
ot[q[i].id]=QuerySec(q[i].l,q[i].r);//注意顺序
}
for(rint i=;i<=m;i++)cout<<ot[i]<<endl;
return ;
}
因为是离线枚举所以千万不要忘了存回去!
最新文章
- PHP+JQUEY+AJAX实现分页【转】
- MP3播放器团队项目
- Spark集群 + Akka + Kafka + Scala 开发(4) : 开发一个Kafka + Spark的应用
- 利用poi开源jar包操作Excel时删除行内容与直接删除行的区别
- win 8(win 7)批处理设置IP
- glibc 安装( version `GLIBC_2.14&#39; not found";)
- Struts1文件上传、单文件、多文件上传【Struts1】
- DllRegisterServer的调用失败的问题解决方法
- 什么是Actor
- SQL Server-聚焦WHERE Column=@Param OR @Param IS NULL有问题?
- BZOJ 4108: [Wf2015]Catering [上下界费用流]
- Spring MVC 使用介绍(十四)文件上传下载
- php中使用sphinx搜索引擎
- 更新RecyclerView的好方法
- 13.scrapy框架的日志等级和请求传参
- Dispatch Queue 之 dispatch_sync
- URL中的空格
- MySQL修改版本号教程
- 20155205 2016-2017-2 《Java程序设计》第9周学习总结
- [js]ext.js探索
热门文章
- 快速掌握zabbix配置
- WPF 画一个3D矩形并旋转
- Linux内核构建过程
- go 1.13编译遇到xxx/go.mod malformed record data 问题
- WinForm自定义控件之DefaultValue的误解
- 数据库学习笔记day03
- Gradle for Android ( 构建变体 )
- Java面试必看之Integer.parseInt()与Integer.valueOf()
- SpringMVC 自定义参数解析器.
- ReactNative: 使用AsyncStorage异步存储类