洛谷 P3567：[POI 2014] KUR-Couriers ← 主席树

【题目来源】https://www.luogu.com.cn/problem/P3567【题目描述】Byteasar 在卖电脑游戏的 BAJ 公司上班。BAJ 公司和多家快递公司合作由这些快递公司将 BAJ 公司销售的游戏送给客户。Byteasar 正在审查 BAJ 公司与快递公司的合作情况。他有一份连续的包裹记录每个包裹都注明了负责配送的快递公司。他想确认没有任何一家快递公司比其他的具有不公平的优势。如果在某个时间段内某家快递公司配送了一半以上的包裹我们就说它在该时间段内占主导地位。Byteasar 想要知道在某些特定的时间段内哪家快递公司占主导地位如果存在的话。来帮 Byteasar 解决这个问题吧请编写一个程序判断在给定时间段内占主导地位的快递公司或者判断不存在这样的公司。【输入格式】第一行包含两个整数 n,m用一个空格分隔分别表示 BAJ 公司发货的包裹总数以及需要查询占主导地位的快递公司的时间段数量。第二行包含 n 个整数 a1,a2,…,an用单个空格隔开ai 表示配送第 i 个包裹的快递公司编号按照配送时间排序。接下来的 m 行每行指定对某个时间段的询问。每个询问包含两个整数 l 和 r用一个空格分隔。这意味着需要确定在第 l 个包裹到第 r 个包裹包含这两个包裹的发货期间占主导地位的快递公司。【输出格式】输出 m 行每行包含一个整数表示对于每个询问的时间段占主导地位公司的编号如果不存在这样的公司则输出 0。【输入样例】7 51 1 3 2 3 4 31 31 43 71 76 6【输出样例】10304【数据范围】对于所有数据1≤n,m≤5×10^51≤ai≤n。【算法分析】● 简化题意 给一个长度为 n 的正整数序列 a。共有 m 组询问每次询问一个区间 [l,r]是否存在一个数在 [l,r] 中出现的次数严格大于一半。如果存在输出这个数否则输出 0。● 复用“洛谷 P3834 → https://blog.csdn.net/hnjzsyjyj/article/details/169217793”框架只改 query 里面一点点不用新知识点。【算法代码】#include bits/stdc.h using namespace std; const int N5e55; int root[N],a[N],tot; vectorint v; struct Node { int L,R,cnt; } tr[N*40]; int getid(int x) { return lower_bound(v.begin(),v.end(),x)-v.begin()1; } int build(int le,int ri) { int ptot; if(leri) return p; int mid(leri)/2; tr[p].Lbuild(le,mid); tr[p].Rbuild(mid1,ri); return p; } int update(int pre,int le,int ri,int x) { int ptot; tr[p]tr[pre]; if(leri) { tr[p].cnt; return p; } int mid(leri)/2; if(xmid) tr[p].Lupdate(tr[pre].L,le,mid,x); else tr[p].Rupdate(tr[pre].R,mid1,ri,x); tr[p].cnttr[tr[p].L].cnttr[tr[p].R].cnt; return p; } int query(int u,int v,int le,int ri,int k) { if(leri) return le; int mid(leri)/2; int leftcnttr[tr[v].L].cnt-tr[tr[u].L].cnt; int rightcnttr[tr[v].R].cnt-tr[tr[u].R].cnt; if(leftcntk) return query(tr[u].L,tr[v].L,le,mid,k); if(rightcntk) return query(tr[u].R,tr[v].R,mid1,ri,k); return 0; } int main() { ios::sync_with_stdio(0); cin.tie(0); int n,m; cinnm; for(int i1; in; i) { cina[i]; v.push_back(a[i]); } sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end()); int lenv.size(); root[0]build(1,len); for(int i1; in; i) { root[i]update(root[i-1],1,len,getid(a[i])); } while(m--) { int le,ri; cinleri; int k(ri-le1)/2; int idquery(root[le-1],root[ri],1,len,k); if(id) coutv[id-1]\n; else cout0\n; } return 0; } /* in: 7 5 1 1 3 2 3 4 3 1 3 1 4 3 7 1 7 6 6 out: 1 0 3 0 4 */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/169217793