2018 Nowcoder Multi-University Training Contest 1
2024-09-05 03:27:07
J. Different Integers
题意：
给出\(n\)个数，每次询问\((l_i, r_i)\)，表示\(a_1, \cdots, a_i, a_j, \cdots, a_n\)中有多少个不同的数。
思路：
先分别离线求出\(a_1, \cdots a_i\)以及\(a_j, \cdots, a_n\)中有多少个不同的数。
再考虑有多少个数既在\([1, i]\)中也在\([j, n]\)中，再离线做一次。
考虑一个数第一次出现的时候，那么这个数下一次出现的位置以及之后的所有询问区间都要减去一个贡献。
代码：
#include <bits/stdc++.h>
using namespace std;
#define N 100010
int n, q, a[N], b[N], c[N], nx[N], ans[N];
struct node {
int l, r, id;
node() {}
void scan(int id) {
this->id = id;
scanf("%d%d", &l, &r);
if (l >= r) {
l = 1;
r = 2;
}
}
}qrr[N];
struct BIT {
int a[N];
void init() {
memset(a, 0, sizeof a);
}
void update(int x, int v) {
for (; x > 0; x -= x & -x) {
a[x] += v;
}
}
int query(int x) {
int res = 0;
for (; x < N; x += x & -x) {
res += a[x];
}
return res;
}
int query(int l, int r) {
return query(l) - query(r + 1);
}
}bit;
int main() {
while (scanf("%d%d", &n, &q) != EOF) {
for (int i = 1; i <= n; ++i) {
scanf("%d", a + i);
}
for (int i = 1; i <= q; ++i) {
qrr[i].scan(i);
}
if (n == 1) {
for (int i = 1; i <= q; ++i) {
printf("1\n");
}
continue;
}
sort(qrr + 1, qrr + 1 + q, [&](node x, node y) {
return x.l < y.l;
});
memset(b, 0, sizeof b);
for (int i = 1, j = 1, k = 0; i <= q; ++i) {
while (j <= n && j <= qrr[i].l) {
if (b[a[j]] == 0) {
b[a[j]] = 1;
++k;
}
++j;
}
ans[qrr[i].id] = k;
}
sort(qrr + 1, qrr + 1 + q, [&](node x, node y){
return x.r > y.r;
});
memset(b, 0, sizeof b);
for (int i = 1, j = n, k = 0; i <= q; ++i) {
while (j >= 1 && j >= qrr[i].r) {
if (b[a[j]] == 0) {
b[a[j]] = 1;
++k;
}
--j;
}
ans[qrr[i].id] += k;
}
memset(b, 0, sizeof b);
for (int i = 1; i <= n; ++i) {
nx[i] = n + 1;
}
for (int i = n; i >= 1; --i) {
c[i] = nx[a[i]];
if (nx[a[i]] == n + 1) {
nx[a[i]] = i;
}
}
bit.init();
sort(qrr + 1, qrr + 1 + q, [&](node x, node y){
return x.l < y.l;
});
for (int i = 1, j = 1; i <= q; ++i) {
while (j <= n && j <= qrr[i].l) {
if (b[a[j]] == 0) {
bit.update(c[j], -1);
b[a[j]] = 1;
}
++j;
}
ans[qrr[i].id] += bit.query(qrr[i].r, n);
}
for (int i = 1; i <= q; ++i) {
printf("%d\n", ans[i]);
}
}
return 0;
}
最新文章
- 关系型数据库与NOSQL
- 请求网络get
- 在公司内网上创建自己的 OSM.Planet 街道级别地图服务器及其客户端程序
- rar 命令
- 保存登录信息的Cookie加密技术
- java使用httpcomponents发送get请求
- 总结一下工作中遇到的NPOI以及在ASP.NET MVC中的使用
- 批量建立EXCHANGE邮件帐号建立三部曲
- 【Android】还原“微信”apk中的“发现”和“我”两个模块
- HTTP代理与SPDY协议（转）
- react基础学习
- Spring+SpringMVC+MyBatis深入学习及搭建(八)——MyBatis查询缓存
- python学习===实现定时发送，方法一
- SQL监测语句
- Ext JS 6开发实例（四） ：调整主视图
- linux下64位汇编的系统调用(5)
- 最详细的Windows平台安装MongoDB教程
- 身边有个漂亮的java女程序员是什么体验？
- MongoDB启动文件配置参数详解
- 【二分图带权匹配】Anagram @山东省第九届省赛 A