You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
87 lines
2.6 KiB
87 lines
2.6 KiB
##[$P3567$ [$POI2014$]$KUR-Couriers$](https://www.luogu.com.cn/problem/P3567)
|
|
|
|
### 一、题目大意
|
|
给一个长度为 $n$ 的正整数序列 $a$。共有 $m$ 组询问，每次询问一个区间 $[l,r]$ ，是否存在一个数在 $[l,r]$ 中 **出现的次数严格大于一半** 。如果存在，输出这个数，否则输出 $0$。
|
|
|
|
$1 \leq n,m \leq 5 \times 10^5,1 \leq a_i \leq n$
|
|
|
|
### 二、解题思路
|
|
主席树入门题啦
|
|
|
|
主席树基础请先去打 [模板题](https://www.luogu.org/problemnew/show/P3834)
|
|
|
|
题面大意就是给定一个区间$[l,r]$,让你求出一个数字$x$的出现次数大于$\frac{r-l+1}{2}$。
|
|
|
|
思路:出现次数大于一半而且是绝对的,如果左儿子的数字个数值已经大于$\frac{r-l+1}{2}$,那么右儿子肯定小于$\frac{r-l+1}{2}$。也可能两边都等于$\frac{r-l+1}{2}$ ,不过这样说明没有答案,返回$0$就行了。
|
|
|
|
如果左儿子(或者右儿子)的$cnt$值大于$\frac{r-l+1}{2}$,那么答案肯定在左子树(或右子树)中,这样就可以$log\ n$的时间求出答案。
|
|
|
|
|
|
### 三、实现代码
|
|
```cpp {.line-numbers}
|
|
#include <cstdio>
|
|
#include <algorithm>
|
|
using namespace std;
|
|
|
|
int read() {
|
|
int x = 0, f = 1;
|
|
char ch = getchar();
|
|
while (ch < '0' || ch > '9') {
|
|
if (ch == '-') f = -1;
|
|
ch = getchar();
|
|
}
|
|
while (ch >= '0' && ch <= '9') {
|
|
x = (x << 3) + (x << 1) + (ch ^ 48);
|
|
ch = getchar();
|
|
}
|
|
return x * f;
|
|
}
|
|
const int N = 5e5 + 10;
|
|
struct Node {
|
|
int l, r, cnt;
|
|
} tr[N << 5];
|
|
|
|
int root[N], idx;
|
|
int n, m;
|
|
|
|
void insert(int &u, int l, int r, int x) {
|
|
tr[++idx] = tr[u];
|
|
tr[u].cnt++;
|
|
u = idx;
|
|
if (l == r) return;
|
|
|
|
int mid = (l + r) >> 1;
|
|
if (x <= mid)
|
|
insert(tr[u].l, l, mid, x);
|
|
else
|
|
insert(tr[u].r, mid + 1, r, x);
|
|
}
|
|
|
|
int query(int p, int q, int l, int r, int x) {
|
|
if (l == r) return l;
|
|
int mid = (l + r) >> 1;
|
|
if (2 * (tr[tr[q].l].cnt - tr[tr[p].l].cnt) > x)
|
|
return query(tr[p].l, tr[q].l, l, mid, x);
|
|
if (2 * (tr[tr[q].r].cnt - tr[tr[p].r].cnt) > x)
|
|
return query(tr[p].r, tr[q].r, mid + 1, r, x);
|
|
return 0;
|
|
}
|
|
|
|
int main() {
|
|
#ifndef ONLINE_JUDGE
|
|
freopen("P3567.in", "r", stdin);
|
|
#endif
|
|
n = read(), m = read();
|
|
for (int i = 1; i <= n; i++) {
|
|
int x = read();
|
|
root[i] = root[i - 1];
|
|
insert(root[i], 1, n, x);
|
|
}
|
|
|
|
while (m--) {
|
|
int l = read(), r = read();
|
|
printf("%d\n", query(root[l - 1], root[r], 1, n, r - l + 1));
|
|
}
|
|
return 0;
|
|
}
|
|
``` |