(POI) XXI OI Round I Task Couriers

https://szkopul.edu.pl/problemset/problem/Cs38m8lWFnOfDskXf43HR3lN/site/?key=statement

總共有三種作法，我實作了兩種

作法一：random sampling
靈感是來自2015年的全國賽啦。
那年的pF就是random sampling，所以，我想說，這題也應該可以用。

我最終的最法是：隨便挑27個數字，去看那個數字在區間的個數。

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <algorithm>
using namespace std;

const int N = 500006;

vector<int> v[N];
int a[N];

int myRnd()
{
    return abs((rand()<<15)^rand());
}

int myRnd(int L,int R)
{
    return myRnd()%(R-L+1)+L;
}

const int K1 = 50;
const int K2 = 27;
const int K3 = 1;

int cnt[N];

int main ()
{
    srand(time(NULL));
    int n,q;
    scanf("%d %d",&n,&q);
    for (int i=1;n>=i;i++)
    {
        scanf("%d",&a[i]);
        v[a[i]].push_back(i);
    }
    while (q--)
    {
        int l,r;
        scanf("%d %d",&l,&r);
        if (r-l <= K1)
        {
            for (int i=l;r>=i;i++)
            {
                cnt[a[i]]++;
            }
            int half = (r-l+1);
            half = (half)/2 + 1;
            int ans = 0;
            for (int i=l;r>=i;i++)
            {
                if (cnt[a[i]] >= half)
                {
                    ans = a[i];
                }
                cnt[a[i]]=0;
            }
            printf("%d\n",ans);
        }
        else
        {
            vector<int> vv;
            for (int i=0;K2>i;i++)
            {
                vv.push_back(myRnd(l,r));
            }
            for (int i:vv)
            {
                cnt[a[i]]++;
            }
            int half = (r-l+1);
            half >>= 1;
            half++;
            int ans = 0;
            for (int i:vv)
            {
                if (cnt[a[i]] >= K3)
                {
                    if (upper_bound(v[a[i]].begin(),v[a[i]].end(),r) - lower_bound(v[a[i]].begin(),v[a[i]].end(),l) >= half)
                    {
                        ans = a[i];
                    }
                }
                cnt[a[i]]=0;
            }
            printf("%d\n",ans);
        }
    }
}

作法二

用可持久化線段樹維護值域，每次query的時候都走size比較大的那邊。

作法三

每個統計bit出現的次數，把那些bit組合起來，看看那個數字有沒有符合條件。

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 500006;
const int M = 20;

int sum[N][M];

int a[N];

vector<int> v[N];

int query(int l,int r,int ask)
{
    if (ask >= N) return 0;
    return upper_bound(v[ask].begin(),v[ask].end(),r) - lower_bound(v[ask].begin(),v[ask].end(),l);
}

int main ()
{
    int n,q;
    scanf("%d %d",&n,&q);
    for (int i=1;n>=i;i++)
    {
        scanf("%d",&a[i]);
        v[a[i]].push_back(i);
        for (int j=0;M>j;j++)
        {
            sum[i][j] = sum[i-1][j];
            sum[i][j] += (((1<<j)&a[i])!=0);
        }
    }
    while (q--)
    {
        int l,r;
        scanf("%d %d",&l,&r);
        int half = ((r-l+1)>>1)+1;
        int ask = 0;
        for (int i=0;M>i;i++)
        {
            if (sum[r][i] - sum[l-1][i] >= half) ask |= (1<<i);
        }
        if (query(l,r,ask) >= half) printf("%d\n",ask);
        else puts("0");
    }
}