[COCI2009-2010#3] PATULJCI

题目描述

思路

由于我特别喜欢暴力数据结构，于是我就用分块 AC 了这道题。

显然我们可以按照 $\sqrt n$ 为一块，将颜色分块，对每一块统计出每种颜色的数量，对于每一次询问，我们对完整块 $O(c)$ 累加，块外元素暴力累加。最后扫一遍结果得出答案。时间复杂度 $O(cm\sqrt n)$

但是按照 $\sqrt n$ 分块实测会 TLE，所以我们使用分块的黑科技，以 $\frac{n}{\log_2n}$ 分块，实测吸氧后跑得飞快，时间复杂度 $O(cm\log n)$ 。

代码

#include <bits/stdc++.h>
using namespace std;

struct Color {
    int ToT[30010];
};

Color Mp[650];
int ToT[30010];
int N , C , K , M , l , r;
int Num[300010];

void Query(int l , int r) {
    memset(ToT , 0 , sizeof ToT);
    for(int i = l; i <= r; ) {
        if(i % K == 1 && i + K <= r) {
            for(int p = 1; p <= C; p++) {
                ToT[p] += Mp[i / K + 1].ToT[p];
            }
            i += K;
        }
        else if(i % K == 1) {
            for(int j = i; j <= r; j++) {
                ToT[Num[j]]++;
            }
            break;
        }
        else if(i % K != 1) {
            while(i % K != 1) {
                ToT[Num[i]]++;
                i++;
                if(i > r) break;
            }
        }
    }
    for(int i = 1; i <= C; i++) {
        if(ToT[i] > ((double)(r - l + 1) / (double)2)) {
            cout << "yes " << i << endl;
            return;
        }
    }
    cout << "no" << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> N >> C;
    for(int i = 1; i <= N; i++) cin >> Num[i];
    K = N / log2(N);
    for(int i = 1 , tot = 1; i + K <= N; i += K , tot++) {
        for(int l = i; l <= N && l <= i + K - 1; l++) {
            Mp[tot].ToT[Num[l]]++;
        }
    }
    cin >> M;
    for(int i = 1; i <= M; i++) {
        cin >> l >> r;
        Query(l , r);
    }
    return 0;
}