3524专题

BZOJ 3524 [Poi2014]Couriers 主席树

Description 给一个长度为n的序列a。1≤a[i]≤n。 m组询问,每次询问一个区间[l,r],是否存在一个数在[l,r]中出现的次数大于(r-l+1)/2。如果存在,输出这个数,否则输出0。 Input 第一行两个数n,m。 第二行n个数,a[i]。 接下来m行,每行两个数l,r,表示询问[l,r]这个区间。 Output m行,每行对应一个答案。

[BZOJ 3524][Poi2014]Couriers:可持久化线段树

点击这里查看原题 主席树,建立权值线段树进行查询 /*User:SmallLanguage:C++Problem No.:3524*/#include<bits/stdc++.h>#define ll long longusing namespace std;const int M=5e5+5;int n,q,cnt,rt[M];struct no{int ls,rs,su

Bzoj 3524: [Poi2014]Couriers(主席树)

3524: [Poi2014]Couriers Time Limit: 20 Sec Memory Limit: 256 MB Description 给一个长度为n的序列a。1≤a[i]≤n。 m组询问,每次询问一个区间[l,r],是否存在一个数在[l,r]中出现的次数大于(r-l+1)/2。如果存在,输出这个数,否则输出0。 Input 第一行两个数n,m。 第二行n个数,a[