HDU 5172 RMQ：区间和 + 前驱最大值判断排列

题目大意

数组 a[1..n]（1≤a[i]≤n），m 次询问 [l,r]：区间内元素是否恰为 1..len 的一个排列（len=r-l+1）。

判断条件

1. 区间和 = len*(len+1)/2
2. 区间内无重复元素

条件 2 等价于：区间内每个元素的「上一次出现位置」均 < l。

预处理

• sum[i]：前缀和
• pre[i]：a[i] 上一次出现的索引（首次为 -1）

线段树 RMQ 维护 pre 最大值

const int N = 1e6+100;
int dat[2*N], nn;

void init(int n) {
    nn = 1; while (nn < n) nn <<= 1;
    fill(dat, dat+2*nn, -INF);
}
void update(int k, int v) {
    k += nn-1; dat[k] = v;
    while (k) { k = (k-1)/2; dat[k] = max(dat[k*2+1], dat[k*2+2]); }
}
int query(int L, int R, int k, int l, int r) {
    if (R<=l || r<=L) return -INF;
    if (L<=l && r<=R) return dat[k];
    return max(query(L,R,k*2+1,l,(l+r)/2), query(L,R,k*2+2,(l+r)/2,r));
}

查询处理

while (m--) {
    int l, r; scanf("%d%d", &l, &r);
    int len = r-l+1;
    ll need = 1LL*len*(len+1)/2;
    if (sum[r]-sum[l-1] != need) { puts("NO"); continue; }
    if (query(l-1, r, 0, 0, nn) < l) puts("YES");
    else puts("NO");
}

复杂度

• 预处理：O(n log n)
• 每查询：O(log n)
• 总计：O((n+m) log n)

关键技巧

1. 排列判定双条件：和正确 + 无重复
2. 前驱最大值：max(pre[l..r]) < l ⇔ 无重复
3. 线段树 RMQ：标准区间最大值查询