[SDOI2009][bzoj1878] HH的项链 [莫队模板题]
2024-08-29 19:11:57
题面:
思路:
就是一道莫队的模板题目......
开一个1000000的数组记录每个数出现的次数,然后每次从1到0或者从0到1更新答案
莫队讲解看这里:莫队
Code:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
inline int read(){
int re=,flag=;char ch=getchar();
while(ch>''||ch<''){
if(ch=='-') flag=-;
ch=getchar();
}
while(ch>=''&&ch<='') re=(re<<)+(re<<)+ch-'',ch=getchar();
return re*flag;
}
int n,m,cnt[],tot=,x[],curl,curr,block,ans[];
struct query{
int l,r,i;
}a[];
bool cmp(query l,query r){
if(l.l/block!=r.l/block) return (l.l/block)<(r.l/block);
else return l.r<r.r;
}
void add(int i){
cnt[x[i]]++;if(cnt[x[i]]==) tot++;
//cout<<"add "<<i<<" "<<x[i]<<" "<<cnt[x[i]]<<"\n";
}
void erase(int i){
cnt[x[i]]--;if(!cnt[x[i]]) tot--;
//cout<<"erase "<<i<<" "<<x[i]<<" "<<cnt[x[i]]<<"\n";
}
int main(){
//freopen("diff.in","r",stdin);
//freopen("diff.out","w",stdout);
int i;
n=read();for(i=;i<=n;i++) x[i]=read();block=sqrt(n);
//cout<<"input one complete "<<n<<" "<<i<<"\n";
m=read();for(i=;i<=m;i++) a[i].l=read(),a[i].r=read(),a[i].i=i;
//cout<<"input two complete "<<m<<" "<<i<<"\n";
sort(a+,a+m+,cmp);curl=a[].l;curr=a[].r;
for(i=a[].l;i<=a[].r;i++) add(i);
ans[a[].i]=tot;
for(i=;i<=m;i++){
while(curl<a[i].l) erase(curl++);
while(curl>a[i].l) add(--curl);
while(curr<a[i].r) add(++curr);
while(curr>a[i].r) erase(curr--);
ans[a[i].i]=tot;
//cout<<"now "<<curl<<" "<<curr<<"\n";
}
for(i=;i<=m;i++) printf("%d\n",ans[i]);
}
最新文章
- JAVA内存管理之堆内存和栈内存
- python Chrome 开发者模式消失的方法
- background-attachment 定义背景图片随滚动轴的移动方式
- 【Avalon】获取隐藏元素的尺寸
- 不用配置tnsnames.ora,直接通过PL/SQL访问远程数据库
- 讨论.NET Core 配置对GC 工作模式与内存的影响
- GridView 翻页 索引超出范围
- 安卓高级3 RecyclerView结合SwipeRefreshLayout并添加上拉
- MAC下 mySQL及workbench安装
- Linux&#160;目录结构学习与简析&#160;Part2
- Nginx referer防盗链模块
- 说说正则表达式的exec方法
- AnsiString和各种数据类型间相互转换 [数据转换]
- RocketMQ生产者消息篇
- 3dmax 物体的真正局部空间原点
- java编程排序之内置引用类型的排序规则实现,和自定义规则实现+冒泡排序运用
- OSMC Vs. OpenELEC Vs. LibreELEC – Kodi Operating System Comparison
- 51nod1981 如何愉快地与STL玩耍
- ThinkPHP项目笔记之RBAC(权限)上篇
- apache服务器设置