记录编号	577831	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	3574.[USACO21Feb Platinum]No Time to Dry	最终得分	100
用户昵称	lihaoze	是否通过	通过
代码语言	C++	运行时间	4.314 s
提交时间	2022-11-23 00:14:56	内存使用	78.60 MiB

#include "bits/stdc++.h"

struct Seg { 
    int l, r, num; 
};

const int N = 2e5 + 10;
int n, q, cnt;
int a[N], L[N], root[N], st[N][30];
std::map<int, int> map;
Seg tree[N << 5];

#define l(x) tree[x].l
#define r(x) tree[x].r
#define num(x) tree[x].num

int update(int pre, int l, int r, int pos, int v) {
    int p = ++ cnt;
    tree[p] = tree[pre];

    if (l == r) 
        return num(p) += v, p;

    int mid = l + r >> 1;
    if (pos <= mid) 
        l(p) = update(l(pre), l, mid, pos, v);
    else 
        r(p) = update(r(pre), mid + 1, r, pos, v);
    num(p) = num(l(p)) + num(r(p));

    return p;
}

int query(int p, int l, int r, int L, int R) {
    if (L <= l && r <= R) 
        return num(p);

    int mid = l + r >> 1, res = 0;
    if (L <= mid) 
        res += query(l(p), l, mid, L, R);
    if (R > mid)
        res += query(r(p), mid + 1, r, L, R);

    return res;
}

void init() {
    int log = std::log2(n) + 1;
    for (int i = 1; i <= n; ++ i) 
        st[i][0] = a[i];
    for (int j = 1; j <= log; ++ j) 
        for (int i = 1; i + (1 << (j - 1)) - 1 <= n; ++ i) 
            st[i][j] = std::min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}

int query(int l, int r) {
    if (l == r) 
        return st[l][0];
    int len = r - l + 1, log = std::ceil(std::log2(len)) - 1;
    return std::min(st[l][log], st[r - (1 << log) + 1][log]); 
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    freopen("dry.in", "r", stdin); 
    freopen("dry.out", "w", stdout);

    std::cin >> n >> q;

    for (int i = 1; i <= n; ++ i) {
        std::cin >> a[i];
        L[i] = map[a[i]], map[a[i]] = i;
    }

    init();

    for (int i = 1; i <= n; ++ i) {
        if (L[i] && query(L[i], i) < a[i])
            L[i] = 0;
    }

    for (int i = 1; i <= n; ++ i) {
        root[i] = update(root[i - 1], 1, n, L[i] + 1, 1);
    }

    while (q --) {
        int l, r;
        std::cin >> l >> r;
        std::cout << query(root[r], 1, n, 1, l) - query(root[l - 1], 1, n, 1, l) << '\n';
    }
    return 0;
}