HDU 6483

￡神魔★判官ぃ 2022-01-31 13:51 26阅读 0赞

## 题意：有长度为nn的数组，对于一个子区间\[l,r\]\[l,r\]内，存在最大值mxmx与最小值mimi，有qq的询问，每个询问要求判断在某个子区间\[l,r\]\[l,r\]内\[mi,mx\]\[mi,mx\]的值是否连续存在，即mi,mi+1,....,mxmi,mi+1,....,mx每个数都出现过至少一次。T=5，1<=n<=10000，1<=ai<=109，1<=m<=100000。 ##

## 思路：ST表（RMQ）/线段树求区间最值+莫队/主席树求区间不同数的个数。 ##

## 代码一（ST表+莫队）： ##

#include<bits/stdc++.h>
    using namespace std;
    const int maxn=1e5+10;
    struct node
    {
        int l,r,id,block,mx,mi;
    } q[maxn];
    int a[maxn],b[maxn],maxPoint[maxn][30],minPoint[maxn][30],num[maxn];
    bool ans[maxn];
    int cnt=0,n,m,block,ll,rr;
    bool cmp(node p,node q)
    {
        return p.block<q.block || p.block==q.block && p.r<q.r;
    }
    void add(int x)
    {
        int tmp=a[x];
        if (num[tmp]==0) cnt++;
        num[tmp]++;
    }
    void del(int x)
    {
        int tmp=a[x];
        if (num[tmp]==1) cnt--;
        num[tmp]--;
    }
    void init()
    {
        for (int i = 1; i <= n; i++)
        {
            minPoint[i][0] = maxPoint[i][0] = a[i];
        }
        for (int j = 1; (1 << j) <= n; j++)
        {
            for (int i = 1; i + (1 << j) - 1 <= n; i++)
            {
                int p = (1 << (j - 1));
                minPoint[i][j] = min(minPoint[i][j - 1], minPoint[i + p][j - 1]);
                maxPoint[i][j] = max(maxPoint[i][j - 1], maxPoint[i + p][j - 1]);
            }
        }
    }
    int queryMin(int l, int r)
    {
        int k = log2((double)(r - l + 1));
        return min(minPoint[l][k], minPoint[r - (1 << k) + 1][k]);
    }
    
    int queryMax(int l, int r)
    {
        int k = log2((double)(r - l + 1));
        return max(maxPoint[l][k], maxPoint[r - (1 << k) + 1][k]);
    }
    bool calc(node tmp)
    {
        if (tmp.mx-tmp.mi+1==cnt) return true;
        return false;
    }
    void init2()
    {
        sort(b+1,b+1+n);
        int tmp=unique(b+1,b+1+n)-(b+1);
        for (int i=1; i<=n; i++)
        {
            a[i]=lower_bound(b+1,b+1+tmp,a[i])-b;
            num[i]=0;
        }
    }
    int main()
    {
        int t;
        scanf("%d",&t);
        while (t--)
        {
            scanf("%d%d",&n,&m);
            for (int i=1; i<=n; i++)
            {
                scanf("%d",&a[i]);
                b[i]=a[i];
            }
            init();
            //离散化
            block=sqrt(n);
            for (int i=0; i<m; i++)
            {
                scanf("%d%d",&q[i].l,&q[i].r);
                q[i].id=i;
                q[i].block=q[i].l/block;
                q[i].mx=queryMax(q[i].l,q[i].r);
                q[i].mi=queryMin(q[i].l,q[i].r);
            }
            init2();
            sort(q,q+m,cmp);
            ll=1,rr=0;
            cnt=0;
            for (int i=0; i<m; i++)
            {
                while (ll<q[i].l) del(ll++);
                while (ll>q[i].l) add(--ll);
                while (rr<q[i].r) add(++rr);
                while (rr>q[i].r) del(rr--);
                ans[q[i].id]=calc(q[i]);
            }
            for (int i=0; i<m; i++)
                if (ans[i]) printf("YES\n");
                else printf("NO\n");
        }
        return 0;
    }

## 代码二（线段树+主席树）： ##

#include <iostream>
    #include <stdio.h>
    #include <map>
    #include <cstring>
     
    #include <bits/stdc++.h>
    typedef long long ll;
    using namespace std;
    const int MAXN = 1e5 + 7;
    const int M = MAXN * 100;
    const int inf=1e9+100;
    int n, q, tot;
    int a[MAXN];
    int T[MAXN], lson[M], rson[M], c[M];
    int maxx[MAXN << 2], minn[MAXN << 2];
     
    void pushup(int rt)
    {
        maxx[rt] = max(maxx[rt << 1], maxx[rt << 1 | 1]);
        minn[rt] = min(minn[rt << 1], minn[rt << 1 | 1]);
    }
     
    void build1(int l, int r, int rt)
    {
        if (l == r)
        {
            maxx[rt] = a[l];
            minn[rt] = a[l];
            return;
        }
        int mid = (l + r) >> 1;
        build1(l, mid, rt << 1);
        build1(mid + 1, r, rt << 1 | 1);
        pushup(rt);
    }
     
    int querymaxn(int L, int R, int l, int r, int rt)
    {
        if (L <= l && R >= r) return maxx[rt];
        int mid = (l + r) >> 1;
        int ret = 0;
        if (L <= mid) ret = max(ret, querymaxn(L, R, l, mid, rt << 1));
        if (R > mid) ret = max(ret, querymaxn(L, R, mid + 1, r, rt << 1 | 1));
        return ret;
    }
     
    int queryminn(int L, int R, int l, int r, int rt)
    {
        if (L <= l && R >= r) return minn[rt];
        int mid = (l + r) >> 1;
        int ret = 0x3f3f3f3f;
        if (L <= mid) ret = min(ret, queryminn(L, R, l, mid, rt << 1));
        if (R > mid) ret = min(ret, queryminn(L, R, mid + 1, r, rt << 1 | 1));
        return ret;
    }
     
    int build(int l, int r) {
        int root = tot++;
        c[root] = 0;
        if (l != r) {
            int mid = (l + r) >> 1;
            lson[root] = build(l, mid);
            rson[root] = build(mid + 1, r);
        }
        return root;
    }
     
    int update(int root, int pos, int val) {
        int newroot = tot++, tmp = newroot;
        c[newroot] = c[root] + val;
        int l = 1, r = n;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (pos <= mid) {
                lson[newroot] = tot++;
                rson[newroot] = rson[root];
                newroot = lson[newroot];
                root = lson[root];
                r = mid;
            } else {
                rson[newroot] = tot++;
                lson[newroot] = lson[root];
                newroot = rson[newroot];
                root = rson[root];
                l = mid + 1;
            }
            c[newroot] = c[root] + val;
        }
        return tmp;
    }
     
    int query(int root, int pos) {
        int ret = 0;
        int l = 1, r = n;
        while (pos < r) {
            int mid = (l + r) >> 1;
            if (pos <= mid) {
                r = mid;
                root = lson[root];
            } else {
                ret += c[lson[root]];
                root = rson[root];
                l = mid + 1;
            }
        }
        return ret + c[root];
    }
     
    int main() {
        int t;
        scanf("%d", &t);
        while (t--) {
            memset(maxx, 0, sizeof(maxx));
            memset(T, 0, sizeof(T));
            memset(lson, 0, sizeof(lson));
            memset(rson, 0, sizeof(rson));
            memset(c, 0, sizeof(c));
            for(int i=0; i<(MAXN<<2); i++){
                minn[i]=0x3f3f3f3f;
            }
            scanf("%d%d", &n, &q);
            tot = 0;
            for (int i = 1; i <= n; i++) {
                scanf("%d", &a[i]);
            }
            build1(1, n, 1);
            T[n + 1] = build(1, n);
            map<int, int> mp;
            for (int i = n; i >= 1; i--) {
                if (mp.find(a[i]) == mp.end()) {
                    T[i] = update(T[i + 1], i, 1);
                } else {
                    int tmp = update(T[i + 1], mp[a[i]], -1);
                    T[i] = update(tmp, i, 1);
                }
                mp[a[i]] = i;
            }
            while (q--) {
                int l, r;
                scanf("%d%d", &l, &r);
                //cout << querymaxn(l, r, 1, n, 1) << endl;
                //cout << queryminn(l, r, 1, n, 1) << endl;
                if (querymaxn(l, r, 1, n, 1) - queryminn(l, r, 1, n, 1) + 1 == query(T[l], r)) puts("YES");
                else puts("NO");
            }
        }
        return 0;
    }