Description

Solution

乱搞能A的题,毁我青春

记忆化一下扩展过程

只要不是从 \(1\) 枚举到 \(n\) 去扩展都可以 \(AC\)

于是 \(random\_shuffle\) 一下扩展顺序就过了

复杂度应该是启发式合并的复杂度

#include
    
     using namespace std;const int N=1e6+10;int n,a[N],L[N],R[N],m,Q,p[N];inline void solve(int x){    int l=x,r=x;    while(1){        if(l>1 && ((l<=a[l-1] && a[l-1]<=r) || !a[l-1])){            l--;            l=min(l,L[l]);r=max(r,R[l]);            continue;        }        if(r
     
      >n>>m>>Q;  for(int i=1;i<=m;i++)      scanf("%d%d",&x,&y),a[x]=y;  for(int i=1;i<=n;i++)L[i]=n+1;  for(int i=1;i<=n;i++)p[i]=i;  for(int i=1;i<=5;i++)random_shuffle(p+1,p+n+1);  for(int i=1;i<=n;i++)solve(p[i]);  while(Q--){      scanf("%d%d",&x,&y);      if(L[x]<=y && y<=R[x])puts("YES");      else puts("NO");  }  return 0;}