[四校联考P3] 区间颜色众数 (主席树)

主席树

---

Description

给定一个长度为 N 颜色序列A，有M个询问：每次询问一个区间里是否有一种颜色的数量超过了区间的一半，并指出是哪种颜色。

Input

输入文件第一行有两个整数：N和C

输入文件第二行有N个1到C之间的整数，表示颜色序列A

输入文件第三行一个整数M，表示询问个数；接下来M行每行两个整数A和B，表示询问的区间是[A, B]。

Output

输出M行。对于第i个询问，如果存在一个颜色超过区间长度的一半，那么输出 “yes x”，x表示颜色编号；否则输出一行 “no”。

Sample Input

10 3
1 2 1 2 1 2 3 2 3 3
8
1 2
1 3
1 4
1 5
2 5
2 6
6 9
7 10

对于30%的数据，M <= 10
对于另外30%的数据，C <= 10.
对于100%的数据：3 ≤ N ≤ 300 000, 1 ≤ C ≤ 10 000, 1 ≤ M ≤ 10 000,1 ≤ A ≤ B ≤ N.

Sample Output

no
yes 1
no
yes 1
no
yes 2
no
yes 3

---

这道题算是我学习主席树的契机了吧，虽然之前NOIP没考过主席树，但NOIP2015之前，树链剖分不也没考过吗。多学习点只是总是没错的。

题解

题目已经说的很明显了，这就是一道主席树的裸题。树中每个节点存颜色信息，第 i 棵树存前 i 个点的信息。查询时用 r 减去 l-1 就好了。

代码

#include <cstdio> #include <iostream> using namespace std;const int maxc = 10000 + 5, maxn = 300000 + 5; int n,c; int rt[maxn],cnt;struct node {int sum,ls,rs; }nod[maxn * 25];void update(int l,int r,int &x,int y,int k){nod[++cnt] = nod[y];nod[cnt].sum++;x = cnt;if(l == r)return;int mid = (l + r) >> 1;if(k <= mid)update(l,mid,nod[x].ls,nod[y].ls,k);else update(mid + 1,r,nod[x].rs,nod[y].rs,k); }int query(int l,int r,int x,int y,int k){if(l == r)return l;int mid = (l + r) >> 1;if((nod[nod[y].ls].sum - nod[nod[x].ls].sum) * 2 > k)return query(l,mid,nod[x].ls,nod[y].ls,k);if((nod[nod[y].rs].sum - nod[nod[x].rs].sum) * 2 > k)return query(mid+1,r,nod[x].rs,nod[y].rs,k);return 0; }int main(){scanf("%d%d",&n,&c);for(int i = 1;i <= n;i++){int x;scanf("%d",&x);update(1,c,rt[i],rt[i-1],x);}int m;scanf("%d",&m);for(int i = 1;i <= m;i++){int x,y;scanf("%d%d",&x,&y);int ans = query(1,c,rt[x-1],rt[y],y-x+1);printf(ans == 0 ? "no\n" : "yes %d\n",ans);}return 0; }

转载于:https://www.cnblogs.com/ZegWe/p/5968744.html

总结

以上是生活随笔为你收集整理的[四校联考P3] 区间颜色众数 (主席树)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。