7218: A Sequence Game

时间限制: 1 Sec  内存限制: 128 MB

提交: 128  解决: 32

[] [] [] [命题人:]

题目描述

One day, WNJXYK found a very hard problem on an Online Judge. This problem is so hard that he had been thinking about the solutions for a couple of days. And then he had a surprise that he misunderstood that problem and easily figured out a solution using segment tree. Now he still wonders that solution for the misread problem.

There is a sequence with N positive integers A1,A2,…,An and M queries. Each query will give you an interval [L,R] and require an answer with YES / NO indicates that whether the numbers in this interval are continuous in its integer range. 

Let us assume that the maximal number in an interval is mx and the minimal   number is mi. The numbers in this interval are continuous in its integer range means that each number from mi to mx appears at least once in this interval.

 

输入

The input starts with one line contains exactly one positive integer T which is the number of test cases. And then there are T cases follow.

The first line contains two positive integers n,m which has been explained above.

The second line contains n positive integers A1,A2,…,An.

Then there will be m lines followed. Each line contains to positive numbers Li,Ri indicating that the i th query’s interval is [Li,Ri].

 

输出

For each test case, output m line.

Each of following m lines contains a single string “YES”/ “NO” which is the answer you have got.

 

样例输入

23 33 1 2 2 31 31 25 31 2 2 4 5 1 51 33 3

 

样例输出

YESYESNONOYESYES

 

提示

T=5

1≤n≤100000

1≤Ai≤10^9

1≤m≤100000

The input file is very large, so you are recommend to use scanf() and printf() for IO.

 

来源/分类

 

这道题，比赛时写到头秃

一开始用主席树+st表，结果开大了MLE，开小了RE，几番试探没结果

然后换算法，另一个队友用莫队+st表写，我用主席树+线段树写，然后在比赛结束之前

我一直wa，找不到bug，她先wa再TLE，不知道怎么优化

然后，令人欣zhi喜xi的地方来了，比赛结束不久，她加了离散化就A了，我有个最小值初值赋错了，然后也A了

自闭

题意：给一个长度为n的序列，m次询问，每次求 [ l , r ] 内是否是连续的一串数，最大值到最小值之间的数最少出现一次

思路：解决的公式为 最大值 - 最小值 + 1 是否等于 不同数的个数 

           判断区间内不同数的个数，想到了主席树还有莫队，然后最大最小用st表，后来又想到再建一个线段树维护最大最小

我的代码：

#include 
    
     #include 
     
      #include 
      
     
    

队友莫队的代码：

#include 
    
     const int N=1e5+10;using namespace std;typedef long long ll; int n,m,block;int lg2[N];int a[N],b[N],dmax[N][35],dmin[N][35];int cur=0,cnt[N];struct node{    int l,r,id;}q[N];bool ans[N]; bool cmp(node x,node y){    return x.l/block==y.l/block?x.r
     
      inline void read(T &x){    x=0;    char c=getchar();    T 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();}    x*=f;}inline void log2(){    lg2[0]=-1;    for(int i=1;i
      
       >1]+1;}void get_st(){    for(int j=1;(1<
       
        <=n;j++){        for(int i=1;i-1+(1<
        
         <=n;i++){            dmax[i][j]=max(dmax[i][j-1],dmax[i+(1<<(j-1))][j-1]);            dmin[i][j]=min(dmin[i][j-1],dmin[i+(1<<(j-1))][j-1]);        }    }}inline int rmq(int l,int r,bool f){    int k=lg2[r+1-l];    if(f) return max(dmax[l][k],dmax[r+1-(1<
         
          q[i].l) add(a[--l]); while(r
          
           q[i].r) del(a[r--]); int maxx=rmq(l,r,1); int minx=rmq(l,r,0); if(maxx+1-minx==cur) ans[q[i].id]=1; else ans[q[i].id]=0; } for(int i=1;i<=m;i++){ if(ans[i]) puts("YES"); else puts("NO"); } } return 0;}