洛谷::P1972 [SDOI2009]HH的项链
2024-09-01 08:11:14
题目背景
无
题目描述
HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运,所以每次散步完后,他都会随意取出一段贝壳,思考它们所表达的含义。HH 不断地收集新的贝壳,因此,他的项链变得越来越长。有一天,他突然提出了一个问题:某一段贝壳中,包含了多少种不同的贝壳?这个问题很难回答……因为项链实在是太长了。于是,他只好求助睿智的你,来解决这个问题。
输入输出格式
输入格式:
第一行:一个整数N,表示项链的长度。
第二行:N 个整数,表示依次表示项链中贝壳的编号(编号为0 到1000000 之间的整数)。
第三行:一个整数M,表示HH 询问的个数。
接下来M 行:每行两个整数,L 和R(1 ≤ L ≤ R ≤ N),表示询问的区间。
输出格式:
M 行,每行一个整数,依次表示询问对应的答案。
********************************************************
莫队模板题,也没啥好说的,同学们可以到 http://blog.csdn.net/wzw1376124061/article/details/67640410
去学习一下
*****************************************
#include<cmath>
#include<cstdio>
#include<algorithm>
#define maxn 200001
using namespace std;
struct goio
{
int l,r;
int id;
}note[maxn];
int visited[maxn * ];
int print[maxn];
int hanin[];
int lc = ;int rc = ;int ans = ;int biaozhun;
int read()
{
int num = ;
char c = getchar();
int f = ;
while(c < ''||c > '')
{
if(c == '-')f = -;
c = getchar();
}
while(c >= '' && c <= '')
{
num *= ;
num += c - '';
c = getchar();
}
return num * f;
}
void add(int x)
{
visited[hanin[x]]++;
ans += (visited[hanin[x]] == );
}
void Upout(int x)
{
visited[hanin[x]]--;
ans -= (visited[hanin[x]] == );
}
bool cmp(const goio &a,const goio &b)
{
int aa = a.l/biaozhun;
int bb = b.l/biaozhun;
if(aa == bb)return a.r < b.r;
else return aa < bb;
}
int main()
{
int n = read();
biaozhun = sqrt(n);
for(int i = ;i <= n;i ++)
{
hanin[i] = read();
}
int m = read();
for(int i = ;i <= m;i ++)
{
note[i].l = read();
note[i].r = read();
note[i].id = i;
}
sort(note + ,note + m + ,cmp);
for(int i = ;i <= m;i ++)
{
int l = note[i].l;
int r = note[i].r;
while(lc < l)Upout(lc),lc++;
while(lc > l)lc--,add(lc);
while(rc < r)rc++,add(rc);
while(rc > r)Upout(rc),rc--;
print[note[i].id] = ans;
}
for(int i = ;i <= m;i ++)
printf("%d\n",print[i]);
return ;
}
最新文章
- EZchip花1.3亿美元买Tilera然后以8亿美元把自己与Tilera一起卖掉
- mysql 5.7配置文件参数详解
- AJAX 页面数据传递
- 用urlencode(String str)对URL传递参数进行编码,提高安全
- 更方便的函数回调——Lambda
- YoMail 邮箱客户端的社会化之路,起于邮箱,不止于邮件
- Clover3(可以让Windows Explorer像浏览器一样有标签页)
- SIP协议搭建电信级VOIP/IM运营平台--架构篇(sip集群)
- [ML] 数据处理
- APP压力稳定性测试之monkey入门
- svn的基本使用方法
- re模块、hashlib模块
- 备份与还原ORACLE数据库(通过CMD命令执行)
- JavaScript 从入门到放弃(一)事件委托和使用innerHTML添加元素
- 洛谷AC破百题纪念!
- leetcode 7->; Reverse Integer(32-bit signed integer)
- Excel中的常用功能
- 为Qemu aarch32添加BeautifulSoup4模块
- flask with gae开发小结
- linux环境中安装NRPE插件执行远程";本地资源";检查?NRPE安装?
热门文章
- 2.2 linux中的信号分析
- Eclipse之NDK编译-- Type &#39;jint&#39; could not be resolved, and JNIEnv, jclass错误解决办法
- .NET 除了用 Task 之外,如何自己写一个可以 await 的对象?
- 写个简单的chrome插件-京东商品历史价格查询
- WinHex简介
- CH4101 银河英雄传说
- string str将str转字符数组以及字符数组初始化
- RabbitMQ负载均衡方案之LVS
- 使用Apriori进行关联分析(二)
- jquery ajax 上传文件