Boyer–Moore majority vote algorithm通常不會用到，只有這裡用到，而且運算速度跟暴力解差不多，唯一好的是空間複雜度大大縮小

主要想法:

是利用投票的方式，自己人會支持，別人會反對。

演算流程:

維護兩個數字，一個是num，代表目前候選數字，另一個是票數t，代表目前支持與反對的結果，演算法虛擬碼如下

• 初始化候選數字num並給票數賦初值t = 0
• 對於每一個元素x：
  • 若i = 0, 那麼 num = x and t = 1 //換人
  • 否則若num = x, 那麼 t = t + 1 //支持
  • 否則 t = t − 1 // 反對
• 返回 num

小心:

這個演算法無法得知是否有絕對多數，若沒有，其仍會給出一個數字，因此需在遍歷一次，檢測此數是否為絕對多數

應用:

這一題只要照做就可以了，數入資料後用Boyer–Moore majority vote algorithm暴力破解就行了，不需要想太多。我想太多想到線段樹之類的結果死了半小時

程式碼:
#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    while(cin>>n){
        if(n==0)break;
        vector<vector<int>> a(n,vector<int> (n));
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                cin>>a[i][j];
            }
        }
        int t;
        cin>>t;
        while(t--){
            int x0,x1,y0,y1;
            cin>>x0>>x1>>y0>>y1;
            int num=-1;
            int t=0;
            for(int i=x0;i<=x1;i++){
                for(int j=y0;j<=y1;j++){
                    if(t==0){
                        num=a[i][j];
                        t++;
                    }else if(num==a[i][j])t++;
                    else t--;
                }
            }
            int real=0;
            for(int i=x0;i<=x1;i++){
                for(int j=y0;j<=y1;j++){
                    if(a[i][j]==num)real++;
                }
            }
            if(real>(x1-x0+1)*(y1-y0+1)/2)cout<< num<<'\n';
            else cout<<-1<<'\n';
        }
    }
}