#6285. 数列分块入门 9

#include <bits/stdc++.h>
using namespace std;
int read() {
    char c = getchar();
    int x = 0, flag = 1;

    while (c < '0' || c > '9')
        flag = (c == '-') ? -1 : 1, c = getchar();

    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';

    return x * flag;
}
void write(int x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }

    if (x > 9)
        write(x / 10);

    putchar((x % 10) + '0');
}
#define MAX 500005
int n, t;
int a[MAX], pos[500], L[500], R[500];
int cnt[MAX];
int Min[500][500];
int c[MAX];
int LSH[MAX];
vector < int > Q [MAX];
void lsh() {
    sort(c + 1, c + n + 1);
    int l = unique(c + 1, c + n + 1) - c - 1;

    for (int i = 1; i <= n; i++)
        LSH[i] = lower_bound(c + 1, c + l + 1, a[i]) - c ;
}
void build() {
    t = sqrt(n);

    for (int i = 1; i <= t; i++) {
        L[i] = R[i - 1] + 1;
        R[i] = i * sqrt(n);
    }

    if (R[t] < n)
        t++, L[t] = R[t - 1] + 1, R[t] = n;

    for (int i = 1; i <= t; i++)
        for (int j = L[i]; j <= R[i]; j++)
            pos[j] = i , Q[LSH[j]].push_back(j);

  //  for (int i = 1; i <= n; i++) {
  //      Q[LSH[i]].push_back(i);
 //   }

    for (int i = 1; i <= t; i++) {
        int num = INT_MAX, times = -INT_MAX;
        memset(cnt, 0, sizeof cnt);

        for (int j = i; j <= t; j++) {
            for (int k = L[j]; k <= R[j]; k++) {
                cnt[LSH[k]]++;

                if (cnt[LSH[k]] > times)
                    num = LSH[k], times = cnt[LSH[k]];
                else if (cnt[LSH[k]] == times)
                    num = min(num, LSH[k]);
            }

            Min[i][j] = num;
        }
    }
}
int query(int l, int r, int x) {
    int m = upper_bound(Q[x].begin(), Q[x].end(), r) - Q[x].begin();
    int n = lower_bound(Q[x].begin(), Q[x].end(), l) - Q[x].begin();
    return m - n ;
}
int ask(int l, int r) {
    int p = pos[l], q = pos[r];
    int ans = 0;

    if (p == q) {
        int num = INT_MAX, times = -INT_MAX;
        memset(cnt, 0, sizeof cnt);

        for (int i = l; i <= r; i++) {
            cnt[LSH[i]]++;

            if (cnt[LSH[i]] > times)
                num = LSH[i], times = cnt[LSH[i]];
            else if (cnt[LSH[i]] == times)
                num = min(num, LSH[i]);

            //int now = query(l,r,LSH[i]);
            //if(now > times) num = LSH[i],times = now;
            //else if(now == times) num = min(num,LSH[i]);
        }

        ans = num;
    } else {
        int times = query(l, r, Min[p + 1][q - 1]);
        int num = Min[p + 1][q - 1];

        for (int i = l; i <= R[p]; i++) {
            int now = query(l, r, LSH[i]);

            if (now > times)
                num = LSH[i], times = now;
            else if (now == times)
                num = min(num, LSH[i]);
        }

        for (int i = L[q]; i <= r; i++) {
            int now = query(l, r, LSH[i]);

            if (now > times)
                num = LSH[i], times = now;
            else if (now == times)
                num = min(num, LSH[i]);
        }

        ans = num;
    }

    return c[ans];
}

int main() {
    n = read();

    for (int i = 1; i <= n; i++)
        c[i] = a[i] = read();

    lsh();
    build();

    while (n--) {
        int l = read(), r = read();

        if (l > r)
            swap(l, r);

        write(ask(l, r));
        puts("");
    }

    return 0;
}

洛谷有一个一样的题目蒲公英，使用该代码可以AC，但是在loj上最后一个点死活过不去，只有96。 求助我的分块有哪里没写好吗