[POI 21 Stage 1] Couriers

這題是在 IOICamp 的時候有講解了，然後就很無恥的(?)寫了一下XD。

作法：

如果這個區間裡面有答案的話，如果這個區間裡奇數比偶數多，那麼答案一定是奇數，否則答案一定是偶數。同理考慮二進位下的右邊數來第 2 個 bit ，如果這個區間裡 1 比較多，那答案的這個 bit 一定是 1 ，否則就是 0 。而要判斷這件事只要預處理每個 bit 的前綴和就可以了，所以這樣就可以找到一個最有可能是答案的人。至於要怎麼確認他就是答案，等於是要知道某個數字在某個區間裡有幾個，而這只要對每個數字都用一個 vector 紀錄他出現的位置，然後二分搜一下就可以了。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=500000+10 ;
 
vector<int> v[maxn] ;
int sum[20][maxn],a[maxn] ;
 
bool check(int x,int l,int r)
{
    int id1=upper_bound(v[x].begin(),v[x].end(),r)-v[x].begin() ;
    int id2=lower_bound(v[x].begin(),v[x].end(),l)-v[x].begin() ;
    return ( 2*(id1-id2) > (r-l+1) ) ;
}
 
main()
{
    int n,Q ; scanf("%d%d",&n,&Q) ;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]) , v[a[i]].push_back(i) ;
    for(int i=0;(1<<i)<=n;i++) for(int j=1;j<=n;j++)
        sum[i][j]=sum[i][j-1]+  ( (a[j]&(1<<i)) ? 1 : 0 ) ;
    while(Q--)
    {
        int l,r ; scanf("%d%d",&l,&r) ;
        int x=0 ;
        for(int i=0;(1<<i)<=n;i++)
        {
            int num= sum[i][r]-sum[i][l-1] ;
            if(2*num > (r-l+1)) x|=(1<<i) ;
        }
        if(check(x,l,r)) printf("%d\n",x) ;
        else printf("0\n") ;
    }
}