强大的莫队算法！虽然复杂度有点高。
#include <cmath>
#include <stack>
#include <cstdio>
#include <iostream>
#include <algorithm>
#define  lson(idx) (idx << 1)
#define  rson(idx) ((idx << 1) ^ 1)
using namespace std;

const int N = (1 << 18);
int num[N], n, nq, ans[N];
struct Modui{
    int l, r, idx, block;
}q[N];
struct segTree{
    int lc, rc, maxv;
}arr[N * 4];
inline bool cmp(Modui a, Modui b){
    if(a.block != b.block)
        return a.block < b.block;
    return a.r < b.r;
}

void build(int l, int r, int idx){
    arr[idx].lc = l, arr[idx].rc = r;
    arr[idx].maxv = 0;
    if(l == r)
        return ;
    int mid = l + r >> 1;
    build(l, mid, lson(idx));
    build(mid + 1, r, rson(idx));
}

void modify(int idx, int loc, int x){
    if(loc > arr[idx].rc || arr[idx].lc > loc)
        return ;
    if(arr[idx].lc == arr[idx].rc && arr[idx].lc == loc){
        arr[idx].maxv += x;
        return ;
    }
    modify(lson(idx), loc, x);
    modify(rson(idx), loc, x);
    arr[idx].maxv = max(arr[lson(idx)].maxv, arr[rson(idx)].maxv);
}

int main(){
    while(cin >> n, n){
        int i, L, R, BLOCK = (int)sqrt((double)n);
        cin >> nq;
        build(1, 200002, 1);
        for(i = 1;i <= n;i++){
            scanf("%d", &num[i]);
            num[i] += 100001;
        }
        //莫队算法
        for(i = 1;i <= nq;i++){
            scanf("%d%d", &q[i].l, &q[i].r);
            q[i].idx = i, q[i].block = q[i].l / BLOCK;
        }
        sort(q + 1, q + nq + 1, cmp);
        for(i = q[1].l;i <= q[1].r;i++)
            modify(1, num[i], 1);
        ans[q[1].idx] = arr[1].maxv;
        L = q[1].l, R = q[1].r;

        for(i = 2;i <= nq;i++){
            for(int j = L;j <= q[i].l - 1;j++)
                modify(1, num[j], -1);
            for(int j = L - 1;j >= q[i].l;j--)
                modify(1, num[j], 1);
            for(int j = R + 1;j <= q[i].r;j++)
                modify(1, num[j], 1);
            for(int j = R;j >= q[i].r + 1;j--)
                modify(1, num[j], -1);
            L = q[i].l, R = q[i].r;
            ans[q[i].idx] = arr[1].maxv;
        }
        for(i = 1;i <= nq;i++)
            printf("%d\n", ans[i]);
    }
    return 0;
}

• Re:莫队算法+线段树！复杂度(n + q)sqrt(n)*log(n)，可以是无序序列，可惜TLE。。 (182) test_solution 2014-07-31 16:27:24
  • Re:莫队算法+线段树！复杂度(n + q)sqrt(n)*log(n)，可以是无序序列，可惜TLE。。 (507) test_solution 2014-07-31 16:50:01
    • Re:莫队算法+线段树！复杂度(n + q)sqrt(n)*log(n)，可以是无序序列，可惜TLE。。 (535) test_solution 2014-07-31 16:59:11