2018牛客网暑期ACM多校训练营(第一场) J - Different Integers - [莫队算法]
2024-09-04 11:20:52
题目链接:https://www.nowcoder.com/acm/contest/139/J
题目描述
Given a sequence of integers a1, a2, ..., an and q pairs of integers (l1, r1), (l2, r2), ..., (lq, rq), find count(l1, r1), count(l2, r2), ..., count(lq, rq) where count(i, j) is the number of different integers among a1, a2, ..., ai, aj, aj + 1, ..., an.
输入描述:
The input consists of several test cases and is terminated by end-of-file.
The first line of each test cases contains two integers n and q.
The second line contains n integers a1, a2, ..., an.
The i-th of the following q lines contains two integers li and ri.
输出描述:
For each test case, print q integers which denote the result.
输入
3 2
1 2 1
1 2
1 3
4 1
1 2 3 4
1 3
输出
2
1
3
备注:
* 1 ≤ n, q ≤ 105
* 1 ≤ ai ≤ n
* 1 ≤ li, ri ≤ n
* The number of test cases does not exceed 10.
题意:
给出序列a[1:n],给出q个查询,每个查询包含(l,r),要求回答a[1:l]和a[r:n]合起来有多少不同的整数。
题解:
莫队算法。
统计a[1:n]有多少不同的整数,记为sum,所有 r - l ≤ 1 的查询答案为sum,
cnt[k]表示整数k出现了几次,sum的变动根据cnt[k]的0→1以及1→0变化判断。
AC代码:
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+;
const int MAXQ=1e5+; struct Query
{
int block;
int id;
int l,r;
bool operator <(const Query &oth) const
{
return (this->block == oth.block) ? (this->r < oth.r) : (this->block < oth.block);
}
}query[MAXQ]; int n,q;
int sum;
int num[MAXN],cnt[MAXN];
int ans[MAXQ]; int main()
{
while(scanf("%d%d",&n,&q)!=EOF)
{
memset(cnt,,sizeof(cnt));
sum=;
for(int i=;i<=n;i++)
{
scanf("%d",&num[i]);
if(cnt[num[i]]==) sum++;
cnt[num[i]]++;
} int len=sqrt(n);
for(int i=;i<=q;i++)
{
scanf("%d%d",&query[i].l,&query[i].r);
if(query[i].r-query[i].l<=) ans[i]=sum;
query[i].block=query[i].l/len;
query[i].id=i;
}
sort(query+,query+q+); int pl=,pr=;
for(int i=;i<=q;i++)
{
if(query[i].r-query[i].l<=) continue; if(pr<query[i].r)
{
for(int j=pr;j<query[i].r;j++)
{
cnt[num[j]]--;
if(cnt[num[j]]==) sum--;
}
}
if(pr>query[i].r)
{
for(int j=pr-;j>=query[i].r;j--)
{
if(cnt[num[j]]==) sum++;
cnt[num[j]]++;
}
}
if(pl<query[i].l)
{
for(int j=pl+;j<=query[i].l;j++)
{
if(cnt[num[j]]==) sum++;
cnt[num[j]]++;
}
}
if(pl>query[i].l)
{
for(int j=pl;j>query[i].l;j--)
{
cnt[num[j]]--;
if(cnt[num[j]]==) sum--;
}
} ans[query[i].id]=sum; pl=query[i].l;
pr=query[i].r;
} for(int i=;i<=q;i++)
{
printf("%d\n",ans[i]);
}
}
}
最新文章
- 安装wamp2.5报权限错误的解决办法
- 李洪强iOS经典面试题143-绘图与动画
- CSS样式表 选择器
- asp.net中TreeView的大数据加载速度优化
- js定时器调用参数的方法
- hdu3555
- [转]Web开发的发展史
- 如何构建日均千万PV Web站点
- ab性能并发测试语法
- HDU FatMouse&#39;s Speed 基本DP
- ABP增删改查代码片段
- oracle 11.2.0.2以后对数据库用户名重命名
- SuperMap 9D 实时数据服务学习笔记
- python编程从入门到实战1-3章
- bzoj3277-串
- CSRF、XSS、clickjacking、SQL 的攻击与防御
- Tips and Tricks for Debugging in chrome
- 在 delphiXE 10.2 上安装 FR5.4.6
- rest api方式实现对文档库的管理
- Java温故而知新(1)集合类