牛客国庆集训派对Day1(Princess Principal)

链接：https://www.nowcoder.com/acm/contest/201/J
思路：好像又学到了一些新姿势，首先匹配括号的时候可以从左向右扫一遍把右括号先全部匹配掉，再从右往左扫一遍把左括号匹配掉（可以证明如果能匹配左右括号是对应匹配的，如果不能都为-1），然后建立RMQ（好久没有用过都快忘了这是个什么东西了），求区间的最大最小值，如果最小值为-1或者小于l或者最大值大于r，则这个区间无解。
代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e6+100;
int s[maxn];
int head = 0;

int a[maxn];
int b[maxn];
int dmin[maxn][100];
int dmax[maxn][100];
int n,m,q;

void RMQ_init(){
    for(int i=0;i<n;i++){
        dmin[i][0] = b[i];
        dmax[i][0] = b[i];
    }
        for(int j=1;(1<<j)<=n;j++)
            for(int i=0;i+(1<<j)-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]);
            }
}

int RMQ_MAX(int L,int R){
    int k =  0;
    while(1<<(k+1)<=R-L+1)k++;
        return max(dmax[L][k],dmax[R-(1<<k)+1][k]);
}

int RMQ_MIN(int L,int R){
    int k =  0;
    while(1<<(k+1)<=R-L+1)k++;
        return min(dmin[L][k],dmin[R-(1<<k)+1][k]);
}

int main(){
    scanf("%d%d%d",&n,&m,&q);
    for(int i=0;i<n;i++)scanf("%d",&a[i]);
    for(int i=0;i<n;i++){
        if(a[i]%2==0){
            s[head++] = i;
        }
        else{
            int now = -1;
            if(head)now = s[--head];
            if(now==-1)b[i] = -1;
            else{
                if(a[now]/2==a[i]/2)b[i] = now;
                else b[i] = -1;
            }
        }
    }
    head = 0;
    for(int i=n-1;i>=0;i--){
        if(a[i]&1){
            s[head++] = i;
        }
        else{
            int now = -1;
            if(head)now = s[--head];
            if(now==-1)b[i] = -1;
            else{
                if(a[now]/2==a[i]/2)b[i] = now;
                else b[i] = -1;
            }
        }
    }
    RMQ_init();
    for(int i=0;i<q;i++){
        int l,r;
        scanf("%d%d",&l,&r);
        l--;
        r--;
        int minv = RMQ_MIN(l,r);
        int maxv = RMQ_MAX(l,r);
        if(minv==-1||minv<l||maxv>r)printf("No\n");
        else printf("Yes\n");
    }
    return 0;
}