2019徐州网络赛 I-query(树状数组)

$Description$
图片说明

$Solution$

$idea \; 1$
$预处理出所有合法区间之后,考虑离线查询,对合法区间和查询区间的r排序,对于查询区间[L,R]$
$将合法区间(l_i,r_i),r_i \leq R的区间l_i加到树状数组中,查询有多少个l_i \geq L即可$
$Code$

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5;
int n,m=0,q,ans[N],pos[N];
struct node{
  int x,y,id;
  bool friend operator<(node l,node r){
      return l.y<r.y;
  }
}qx[N],qy[N];
int sum[N]={0};
void up(int x){for(int i=x;i<=n;i+=i&-i)sum[i]++;}
int Q(int x){
  int res=0;
  for(int i=x;i;i&=i-1)res+=sum[i];
  return res;
}
int main(){
  scanf("%d%d",&n,&q);
  for(int i=1,x;i<=n;i++)scanf("%d",&x),pos[x]=i;
  for(int i=1;i<=n;i++)
  for(int j=2*i;j<=n;j+=i){
      if(pos[j]>pos[i])qx[++m]={pos[i],pos[j],0};
      else qx[++m]={pos[j],pos[i],0};
  }
  for(int i=1;i<=q;i++){
      scanf("%d%d",&qy[i].x,&qy[i].y);
      qy[i].id=i;
  }
  sort(qx+1,qx+1+m);sort(qy+1,qy+1+q);
  int cnt=1;
  for(int i=1;i<=q;i++){
      while(cnt<=m&&qx[cnt].y<=qy[i].y){
          up(qx[cnt].x);
          cnt++;
      }
      ans[qy[i].id]=Q(qy[i].y)-Q(qy[i].x-1);
  }
  for(int i=1;i<=q;i++)printf("%d\n",ans[i]);
}

$idea \; 2$
$预处理出合法区间后,将每个(l_i,r_i)看作二维平面的点,查询[L,R]区间时$
$相当于查找以左上角坐标(L,L),右下角坐标(R,R)的矩阵内的点的个数,就是一个二维前缀和的模型了.$
$Code$

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5;
int n,m=0,q;
int pos[N],ans[N];
struct qin_peng{
  int id,x,y,val,flag;
  bool friend operator<(qin_peng a,qin_peng b){
      return a.x<b.x;
  }
}QR[N],QP[N];
int sum[N]={0};
void up(int x,int val){for(int i=x;i<N;i+=i&(-i))sum[i]+=val;}
int Q(int x){
  int ans=0;
  for(int i=x;i;i&=i-1)ans+=sum[i];
  return ans;
}
int main(){
  scanf("%d%d",&n,&q);
  for(int i=1,x;i<=n;i++){
      scanf("%d",&x);
      pos[x]=i;
  }
  for(int i=1;i<=n;i++){
      for(int j=2*i;j<=n;j+=i){
          if(pos[j]>pos[i]){
              QP[++m]={m,pos[i],pos[j],1,0};
          }
          else QP[++m]={m,pos[j],pos[i],1,0};
      }
  }
  int cnt=0;
  for(int i=1;i<=q;i++){
      int l,r;
      scanf("%d%d",&l,&r);
      int x1=l,y1=l,x2=r,y2=r;
      QR[++cnt]={i,x2,y2,0,1};
      QR[++cnt]={i,x1-1,y2,0,-1};
      QR[++cnt]={i,x2,y1-1,0,-1};
      QR[++cnt]={i,x1-1,y1-1,0,1};
  }
  sort(QP+1,QP+1+m);sort(QR+1,QR+1+cnt);
  int ptr=1;
  for(int i=1;i<=cnt;i++){
      while(ptr<=m&&QP[ptr].x<=QR[i].x){
          up(QP[ptr].y,QP[ptr].val);
          ++ptr;
      }
      ans[QR[i].id]+=QR[i].flag*Q(QR[i].y);
  }
  for(int i=1;i<=q;i++)printf("%d\n",ans[i]);
}