Super Mario

区间内小于或等于 k 的数字有多少个

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn=200106;
int a[maxn];
int id[maxn];
int root[maxn];
int tot;
int n,m;
const int inf=0x3f3f3f3f;

struct sgt{
  int lc,rc;
  int dat;
}t[maxn*21];

int build(int l,int r){
  int p=++tot;
  t[p].dat=0;
  if(l==r){
    return p;
  }
  int mid=(l+r)/2;
  t[p].lc=build(l,mid);
  t[p].rc=build(mid+1,r);
  return p;
}

int insert(int now,int l,int r,int x){            //建立新线段树
  int p=++tot;                                    //新节点
  t[p]=t[now];                                    //新节点的左右儿子初始化前一棵树的数据

  if(l==r) {                                      //更新叶节点
    t[p].dat++;                                   //权值+1
    return p;
  }
  int mid=(l+r)/2;
  if(x<=mid) t[p].lc=insert(t[now].lc,l,mid,x);  //x出现在左子树，修改左子树
  else t[p].rc=insert(t[now].rc,mid+1,r,x);      //x出现在右子树，修改右子树
  t[p].dat=t[t[p].lc].dat+t[t[p].rc].dat;        //更新父节点
  return p;
}

int query(int pl,int pr,int l,int r,int k){      //查询[pl,pr]区间的线段树，输入k在排序好的序列中的下标
  if(l==r) return t[pr].dat-t[pl].dat;
  int mid=(l+r)/2;
  int tem=t[t[pr].lc].dat-t[t[pl].lc].dat;
  if(k<=mid) return query(t[pl].lc,t[pr].lc,l,mid,k);
  else return tem+query(t[pl].rc,t[pr].rc,mid+1,r,k);         //查找右边累计上tem
}

int main(){
  int ca;
  scanf("%d",&ca);                               //实例个数
  int ct=1;
  while(ca--){
    printf("Case %d:\n",ct++);                   //输出实例次数
    tot=0;
    scanf("%d%d",&n,&m);                         //序列长度、测试次数
    for(int i=1;i<=n;i++){
      scanf("%d",&a[i]);                         //原数组
      id[i+1]=a[i];                              //排序数组
    }
    id[1]=-inf;
    id[n+2]=inf;
    sort(id+1,id+n+3);                           //排序
    int len=unique(id+1,id+3+n)-(id+1);          //整个数组去重
    root[0]=build(1,len);                        //建立空树，可以注释掉
    for(int i=1;i<=n;i++){
      int p=lower_bound(id+1,id+1+len,a[i])-id;               //离散化：返回数组中第一个大于或等于被查数的值
      root[i]=insert(root[i-1],1,len,p);                      //记录第i棵树的根节点
    }
    for(int i=1;i<=m;i++){
      int tl,tr,k;
      scanf("%d%d%d",&tl,&tr,&k); tl++; tr++;
      printf("%d\n",query(root[tl-1],root[tr],1,len,upper_bound(id+1,id+len+1,k)-(id+1)));
    }
  }
  return 0;
}

笔记：先建立原始空树，之后的 i 树都是在空树 + i-1 的基础上修改的，在逻辑上需要空树，但是在运行程序上这个空树可以不建立，也没问题。这是区间统计需要累积在范围内节点上的权值。