P3567 [POI2014]KUR-Couriers 主席树模板

😊 | Powered By HeartFireY

Problem Analysis

题目大意： 对于给定的序列，输出待查询区间内出现次数严格大于区间长度一半的数字。若不存在输出 0 0 0。

维护区间内数的个数，那么考虑用可持久化权值线段树(主席树)解决。

首先考虑非法状态：因为对于主席树上任意一个节点，其代表的意义是管辖区间内数字的个数。因此对于主席树上某个节点，如果其代表区间数字的数目比区间长度的一半(也就是 r − l + 1 2 \frac{r - l + 1}{2} 2r−l+1​)要小，那么子区间不回再出现满足该条件的数，在这种情况下可以直接返回 0 0 0。

对于其他的情况，按照主席树的套路进行搜索即可。

Accepted Code

#include 
using namespace std;

const int N = 5e5 + 10;

int a[N], b[N];
int tot, root[N  a[i];
        b[i] = a[i];
    }
    sort(b + 1, b + n + 1);
    int m = unique(b + 1, b + n + 1) - b - 1;
    for(int i = 1; i > l >> r;
        int k = (r - l + 1) >> 1;
        cout