HH的项链洛谷1972 莫队 c++

2019-11-08 19:57:52

字体：大中小

来源：转载

供稿：网友

题目描述

HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH 不断地收集新的贝壳，因此，他的项链变得越来越长。有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答……因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。

输入格式：

第一行：一个整数N，表示项链的长度。

第二行：N 个整数，表示依次表示项链中贝壳的编号（编号为0 到1000000 之间的整数）。

第三行：一个整数M，表示HH 询问的个数。

接下来M 行：每行两个整数，L 和R（1 ≤ L ≤ R ≤ N），表示询问的区间。

输出格式：

M 行，每行一个整数，依次表示询问对应的答案。

数据范围：

对于100%的数据，N <= 50000，M <= 200000。

Solution

线段树例题。。然后用莫队a了呵呵线段树太长不打，那么题目就是一个裸的不带修改的莫队为了提升效率，我们把序列分成n−√ $/sqrt{n}$ 块，对于所有的询问离线处理先按询问的左端点所属块排序，同一块的以右端点为关键字升序排，然后对于每个询问暴力求解。由于只有n−√ $/sqrt{n}$ 个块，每个右端点最多延伸n $n$ ，那么复杂度大概是O(nn−√) $O(n/sqrt{n})$ 的

Code

#include <string.h>#include <stdio.h>#include <algorithm>#include <vector>#define rep(i, st, ed) for (int i = st; i <= ed; i += 1)#define fill(x, t) memset(x, t, sizeof(x))#define pb push_back#define N 50001#define L 250#define M 200001struct Q{int l, r, index;};inline int read(){ int x = 0, v = 1; char ch = getchar(); while (ch < '0' || ch > '9'){ if (ch == '-'){ v = -1; } ch = getchar(); } while (ch <= '9' && ch >= '0'){ x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); } return x * v;}inline int cmp(const Q &a, const Q &b){ return (a.l / L) < (b.l / L) || (a.l / L) == (b.l / L) && a.r < b.r;}int bct[N];inline int add(const int &now){ bct[now] += 1; if (bct[now] == 1){ return 1; } return 0;}inline int del(const int &now){ bct[now] -= 1; if (bct[now] == 0){ return -1; } return 0;}using std:: vector;using std:: sort;int PRt[N];int main(void){ int n = read(); vector<int> num; rep(i, 1, n){ num.pb(read()); } int m = read(); vector<Q> q; rep(i, 1, m){ int l = read(), r = read(); q.pb((Q){l, r, i}); } sort(q.begin(), q.end(), cmp); int l = 1, r = 0; int ans = 0; rep(i, 0, q.size() - 1){ while (r < q[i].r){ r ++; ans += add(num[r - 1]); } while (r > q[i].r){ ans += del(num[r - 1]); r --; } while (l < q[i].l){ ans += del(num[l - 1]); l ++; } while (l > q[i].l){ l --; ans += add(num[l - 1]); } prt[q[i].index] = ans; } rep(i, 1, m){ printf("%d/n", prt[i]); } return 0;}

上一篇：C++的常量成员函数

下一篇：C++编程练习问题汇总--程序员面试宝典+剑指offer