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)可持久化线段树