CCPC-Wannafly Camp #2 J Princess Principal 【离线+栈】

分析：这个题目，我们离线处理所有的查询区间，将所有区间按照右端点排序，然后通过栈去匹配括号，左括号直接入栈，右括号的话，如果匹配上了，就出栈，如果没有匹配上了，就留在栈中，当我们扫描到第i个的时候，对于右端点为i的询问，我们判断它的左区间是否比栈顶元素要小，如果小的话，就不能够匹配上了，如果大的话 我们会发现，我们通过这样处理可以保证查询的右端点在右区间，但不能保证询问的左端点，所以我们预处理一个数组，来保存区间内左右括号的个数，如果括号个数相等，并且我们通过栈判断了这个区间内是可以匹配成功的，由于一个左括号固定匹配一个右括号，所以这样必定能够判断是否成立。

代码

#include <bits/stdc++.h>

using namespace std;
typedef pair<double,int> P;

const int maxn = 1e6+100;
const int INF = 0x3f3f3f3f;
#define PI 3.1415926
#define sc(a) scanf("%d",&a)
#define pfs(a) printf("%d ",a)
#define pfn(a) printf("%d\n",a);
#define pfln(a) printf("%lld\n",a);
#define rep(n) for(int i = 0; i < n; i++)
#define per(n) for(int i = n-1; i >= 0; i--)
#define mem(a,x) memset(a,x,sizeof(a))


struct Node
{
   int l,r,i;
   bool t;
   Node(int l = 0,int r = 0, int i =0,bool t = false) : l(l), r(r), i(i), t(t) {}
};

bool cmp1(Node a, Node b)
{
  if(a.r == b.r)  return a.l < b.l;
                  return a.r < b.r;
}

bool cmp2(Node a, Node b)
{
    return a.i < b.i;
}

int n,m,q;
stack<int> s;
int x[maxn];
int y[maxn];
Node p[maxn];

int main()
{
  sc(n),sc(m),sc(q);
  mem(y,0);
  rep(n) sc(x[i+1]);
  for(int i = 1; i <= n; i++)
  {
      y[i] = y[i-1];
      if(x[i] % 2 == 0) y[i] ++;
      else              y[i] --;
  }
  rep(q) {
     int l,r;
     sc(l),sc(r);
     p[i] = Node(l,r,i,false);
  }
  sort(p,p+q,cmp1);
  int j = 0;
  for(int i = 1; i <= n; i++)
  {
    int t = -1;
    if(s.empty() || x[i] % 2 == 0) s.push(i);
    else  {
        t = s.top();
        if(x[i]/2 == x[t]/2 && x[t] % 2 == 0) s.pop();
        else     s.push(i);
    }
    while(p[j].r == i && j < q)
    {
      if(t < p[j].l || y[p[j].r] - y[p[j].l-1] != 0) {p[j].t = false;j++;continue;}
      if((p[j].r - p[j].l + 1)%2 == 0 && (x[p[j].l] % 2 == 0 && x[p[j].r] % 2 == 1) && (s.empty() || s.top() < p[j].l)) p[j].t = true;
      else  p[j].t = false;
        j++;
    }
  }
  sort(p,p+q,cmp2);
  rep(q) if(p[i].t) printf("Yes\n");else printf("No\n");
   return 0;
}