主席樹

---

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] 区间颜色众数 (主席树)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。