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

query

• 
  
  
  

  #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]);
  }

• 
  
  
  

  #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]);
  }