题意: n个数和m个询问, 问位置[l, r]中是否存在一个数出现的次数大于(r-l+1)/2, 如有则输出, 否则报告不存在. (每个数是不超过n的正整数, n, m ≤ 5*10^5) 如果存在这样一个数, 那么它是唯一的, 所以才叫我们输出. 如果有一棵位置[L, R]的权值线段树[l, r], 若[l, r]内数小于等于(R-L+1)/2, 则无解, 否则递归地询问数较多的子区间[l, m]或[m+1, r]. 边界是l=r.
可持久化线段树正能帮我们完成这件事. 如果每一点都有一棵权值线段树 (虽然这棵线段树里只有一个数), 由于规模相等的线段树形态相同, [L, R]的权值线段树就是若干个这样的线段树的和. 用两个前缀和作差以优化权值线段树的求和运算, 即, [L, R]的权值线段树=[1, R]的权值线段树-[1, L]的权值线段树. [1, pos]的权值线段树是[1, pos-1]的权值线段树添加一个数得到的, 如果将线段树持久化, 很容易建出一系列前缀权值线段树.
线段树形态固定, 可以自顶向下实现, 很方便持久化. 把修改一个结点改为创建一个新的版本即可. 先将新结点的左右儿子链接到旧结点的左右儿子上, 然后递归地修改. 这样, 只用记录新的根结点, 就能像访问普通线段树一样访问可持久化线段树了. 由此看来, 得放弃堆式存储的写法, 显式地记录左右儿子. 这种算法的时空复杂度是
#include <bits/stdc++.h>
#define Rep(i, a, b) for (int i = (a), i##_ = (b); i < i##_; ++i)
#define For(i, a, b) for (int i = (a), i##_ = (b); i <= i##_; ++i)
#define Down(i, a, b) for (int i = (a), i##_ = (b); i >= i##_; --i)
using namespace std;
const int MAX_N = 5e5, LG_N = 19;
struct Node {
Node* lc, * rc;
int s;
} nodes[MAX_N*(LG_N+1)+1], * nil = nodes, * root[MAX_N+1] = {nil};
inline void init()
{
*nil = (Node){nil, nil, 0};
}
inline Node* new_node(int v)
{
static Node* cur = nodes + 1;
*cur = (Node){nil, nil, v};
return cur++;
}
void insert(Node*& o, Node* p, int x, int l, int r)
{
o = new_node(p->s + 1);
if (l != r) {
int m = (l+r)/2;
if (x <= m)
insert(o->lc, p->lc, x, l, m), o->rc = p->rc;
else
insert(o->rc, p->rc, x, m+1, r), o->lc = p->lc;
}
}
int query(Node* o, Node* p, int t, int l, int r)
{
if (o->s - p->s <= t) return 0;
if (l == r) return l;
int m = (l+r)/2;
return o->lc->s - p->lc->s > t ?
query(o->lc, p->lc, t, l, m) : query(o->rc, p->rc, t, m+1, r);
}
int main()
{
init();
int n, m;
scanf("%d%d", &n, &m);
For (i, 1, n) {
int a;
scanf("%d", &a);
insert(root[i], root[i-1], a, 1, n);
}
For (i, 1, m) {
int l, r;
scanf("%d%d", &l, &r);
printf("%d\n", query(root[r], root[l-1], (r-l+1)/2, 1, n));
}
return 0;
}