HDU 5172（线段树询问区间有无重复数字）

题目链接

题意：给定一个数组N，然后给定M个询问，问区间[L,R]是否构成1~（R-L+1）的全排列。
思路很巧妙，比赛时候没有想出来这个点
满足两个条件。
1.区间和等于len*(len+1)/2;
2.该段区间内没有重复数字。
第一个条件很好解决，用前缀和减一下就可以了。那第二个条件的话，先求出对于位置i的元素a[i]，a[i]上一次出现的位置，然后线段树维护下最大值就可以了。因为如果这段区间内的数字，他上一次出现的最大位置都比L小，那么这段区间也就不会有数字重复

//2021-08-08 10:22:18
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N = 1e6+10;
int n, m;
int a[N];
ll sum[N];
int last[N], pos[N];

int mx[N*4];

void change(int k1) {
    mx[k1] = max(mx[k1*2], mx[k1*2+1]);
    return;
}
void buildtree(int k1, int l, int r) {
    if(l == r) {
        mx[k1] = last[l];
        return;
    }
    int mid = l+r >> 1;
    buildtree(k1*2, l, mid);
    buildtree(k1*2+1, mid+1, r);
    change(k1);
}

int Find(int k1, int l, int r, int L, int R) {
    if(l > R || r < L) return 0;
    if(L <= l && r <= R) {
        return mx[k1];
    }
    int mid = l+r >> 1;
    return max(Find(k1*2, l, mid, L, R), Find(k1*2+1, mid+1, r, L, R));
}

int main() {
    while(scanf("%d%d", &n, &m) != EOF) {
        memset(pos, 0, sizeof(pos));
        memset(last, 0, sizeof(last));
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            sum[i] = sum[i-1] + a[i];
            last[i] = pos[a[i]];
            pos[a[i]] = i;
        }
        buildtree(1, 1, n);
        int l, r;
        while(m--) {
            scanf("%d%d", &l, &r);
            int len = r-l+1;
            if( (sum[r] - sum[l-1] == len*(len+1)/2) && (Find(1, 1, n, l, r) < l)) {
                printf("YES\n");
            } else printf("NO\n");
        }
    }
    return 0;
}