2018 黑龙江省赛A Sequence Game 莫队+ST表

A Sequence Game
大意：求区间内的最大值与最小值中的数是否都出现过
看max-min+1是否等于区间数字种类数即可
前者预处理ST表
后者可用两种方法求出
1）莫队

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int>pii;
typedef pair<LL,LL>pll;
const int maxn=1e5;
const int mod=1e9+7;
const int oo=1e9;
int n,m,a[maxn+5],pos[maxn+5],len,L,R,Ans,num[maxn+5],ans[maxn+5];
int ma[maxn+5][30],mi[maxn+5][30],c[maxn+5];

struct node
{
    int l,r,id;
}b[maxn+5];
bool cmp(node a,node b)
{
    return pos[a.l]^pos[b.l]?pos[a.l]<pos[b.l]:((pos[a.l]&1)?a.r<b.r:a.r>b.r);
}
inline int read()
{
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9'){if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9'){x = x * 10 + (c - '0'); c = getchar();}
    return x * f;
}
void init()
{
    for(int i=0;i<=n;i++) ma[i][0]=mi[i][0]=a[i],num[i]=0;

    for(int j=1;(1<<j)<=n;j++){
        for(int i=1;i<=n-(1<<j)+1;i++){
            ma[i][j]=max(ma[i][j-1],ma[i+(1<<(j-1))][j-1]);
            mi[i][j]=min(mi[i][j-1],mi[i+(1<<(j-1))][j-1]);
        }
    }
}
int calu(int x,int y)
{
    int k=log(y-x+1)/log(2);
    int A=max(ma[x][k],ma[y-(1<<k)+1][k]);
    int B=min(mi[x][k],mi[y-(1<<k)+1][k]);
    return A-B+1;
}
void del(int x)
{
    //num[x]--;
    if(--num[x]==0) Ans--;
}
void add(int x)
{
    if(num[x]++==0) Ans++;
    //num[x]++;
}
int main()
{
    int _;_=read();
    while(_--){
        n=read();m=read();
        len=sqrt(n);
        for(int i=1;i<=n;i++) a[i]=read(),c[i]=a[i],pos[i]=i/len;
        init();
        sort(c+1,c+1+n);
        int k=unique(c+1,c+1+n)-c-1;
        for(int i=1;i<=n;i++) a[i]=lower_bound(c+1,c+k+1,a[i])-c;

        for(int i=1;i<=m;i++){
            b[i].l=read();b[i].r=read();
            b[i].id=i;
        }
        sort(b+1,b+1+m,cmp);

        L=1,R=0;Ans=0;
        for(int i=1;i<=m;i++){
            while(L<b[i].l){
                del(a[L++]);
            }
            while(L>b[i].l){
                //L--;
                add(a[--L]);
            }
            while(R<b[i].r){
                //R++;
                add(a[++R]);
            }
            while(R>b[i].r){
                del(a[R--]);
                //R--;
            }
            ans[b[i].id] = Ans==calu(b[i].l,b[i].r)?1:0;

        }

        for(int i=1;i<=m;i++){
            puts(ans[i]?"YES":"NO");

        }
    }
}

2）可持久化线段树