COCI 2009/2010 #3 p5

標題好長XD


簡單的說

第一行有兩個數字N, C

接下來給你一條數列S  ，長度是N(<=300,000)，裡面的數字範圍是1~C(<=10,000)

第三行是一個數字M(<=10,000)表示有幾組詢問

接下來M組詢問，每組有L, R(1<=L<=R<=N)

問你閉區間[L, R]中有沒有哪個數字出現超過一半？有的話問是哪個數字？

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

Sample output:
no
yes 1
no
yes 1
no
yes 2
no
yes 3


全國賽那天晚上戰的COCI的題目(轉

小鬼當時說他會做了不知道跟官方solution一不一樣(欸

shik表示：蒙地卡羅應該會過


不過官方solution好好玩(打滾











========================solution===================


先不要考慮原題目，來想另一個遊戲：

給你一個序列S，每次可以把S裡面相異兩個數字抹掉。

直到全部都剩下同一個數字時遊戲結束

例如 12312323->312323->1323->33m 時結束。

這時紀錄兩個數 candi表示剩下的數字是什麼  count表示結束狀態多長

例如上述例子   candi=3 count=2




引理：如果有個數字出現超過length/2次，那他一定會是candi，無論過程

那麼，我們只要維護一棵seg tree就可以作到區間查詢candi了ˇ

就是分L.candi==R.candi以及L.candi!=R.candi時比兩個count大小

然後求出這個區間的candi，再去用另一棵seg tree計算他出現幾次

如果出現>length/2次就是yes  否則則是no