这道题需要用主席树维护，基本上算是裸题。
题目传送门
简单介绍一下主席树：
就是线段树的可持久化，每次新建版本时，都新建一个根，递归新建所有值发生改变的节点。
与普通线段树不同的是，主席树需要记录节点的左右儿子编号。
具体到这道题，从1到n一个一个往主席树里加棒棒糖。
每加一个就建一个新版本。
然后需要把之前版本的信息整合（这道题直接相加就行）到当前版本上。
查询的时候，如果查询区间[l,r]，就在第r个版本和第l-1个版本的差里查询即可。
注意主席树需要很大空间。
除了原树（这道题没有原树）的4倍空间以外，每新建一个版本都需要额外的log n的空间。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 ?6 int n,m; 7 int root[50005],tot,v[850005]; 8 int ls[850005],rs[850005]; 9 10 void add(int &num,int lb,int rb,int c)11 {12 ????if(num==0)num=++tot;13 ????v[num]++;14 ????if(lb==rb)return;15 ????int mid=(lb+rb)>>1;16 ????if(c<=mid)add(ls[num],lb,mid,c);17 ????else add(rs[num],mid+1,rb,c);18 }19 20 void merge(int fr,int &to)21 {22 ????if(to==0){to=fr;return;}23 ????if(fr==0)return;24 ????v[to]+=v[fr];25 ????merge(ls[fr],ls[to]);26 ????merge(rs[fr],rs[to]);27 }28 29 int ask(int px,int py,int lb,int rb,int mv)30 {31 ????if(v[py]-v[px]<=mv)return 0;32 ????if(lb==rb)return lb;33 ????int mid=(lb+rb)>>1;34 ????if(v[ls[py]]-v[ls[px]]>=v[rs[py]]-v[rs[px]])35 ????????return ask(ls[px],ls[py],lb,mid,mv);36 ????else 37 ????????return ask(rs[px],rs[py],mid+1,rb,mv);38 }39 40 int main()41 {42 ????scanf("%d%d",&n,&m);43 ????for(int i=1;i<=n;i++)44 ????{45 ????????int t;46 ????????scanf("%d",&t);47 ????????add(root[i],1,50000,t);48 ????????merge(root[i-1],root[i]);49 ????}50 ????for(int i=1;i<=m;i++)51 ????{52 ????????int l,r;53 ????????scanf("%d%d",&l,&r);54 ????????printf("%d\n",ask(root[l-1],root[r],1,50000,(r-l+1)/2));55 ????}56 ????return 0;57 }代码还算简单，跟线段树差不多。
这里还有一道一模一样的题：[bzoj3524] [POI2014] KUR-Couriers
bzoj3524传送门（ tu hao 题，这个门就是开玩笑的）
洛谷P3567传送门（这个是正经能用的）
这道题的数据范围是棒棒糖的十倍。
把棒棒糖那道题的数组大小改一下就行了。
其他的真的一模一样，不上代码了。
[bzoj5178] [Jsoi2011] 棒棒糖
原文地址：https://www.cnblogs.com/eternhope/p/9606588.html