[POI 21st Stage 1] Couriers

原題連結

code的作法可以參考這篇。
也有一個直覺的作法是利用持久化權值線段樹，可以參考這篇。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000000;
vector<int> show[maxn];
int n,m,a[maxn],pre[20][maxn];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",a+i);
        for(int j=0;(1<<j)<=n;j++) pre[j][i]=pre[j][i-1]+(a[i]&(1<<j)?1:0);
        show[a[i]].push_back(i);
    }
    int L,R;
    while(m--)
    {
        scanf("%d%d",&L,&R);
        int tar=(R-L+1)/2+1,ans=0;
        for(int i=0;(1<<i)<=n;i++)
        {
            int cnt=pre[i][R]-pre[i][L-1];
            if(cnt>=tar) ans|=(1<<i);
        }
        int tmpR=upper_bound(show[ans].begin(),show[ans].end(),R)-show[ans].begin();
        int tmpL=lower_bound(show[ans].begin(),show[ans].end(),L)-show[ans].begin();
        if(tmpR-tmpL>=tar) printf("%d\n",ans);
        else printf("0\n");
    }
}