high记录原始身高

HIGH记录每块排序之后的身高

不满一块的直接对high操作，重排之后再赋值给HIGH

块内直接打标记

查询时，不满一块的直接查，一整块的在HIGH内二分块内第一个>=C-标记的点

 

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;#define N 1000001int bl[N];int high[N],HIGH[N],tmp[N];int L[1001],R[1001],tag[1001];void read(int &x){    x=0; char c=getchar();    while(!isdigit(c)) c=getchar();    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }}void modify(int l,int r,int w){    if(bl[l]==bl[r])    {        for(int i=l;i<=r;++i) high[i]+=w;        for(int i=L[bl[l]];i<=R[bl[l]];++i) tmp[i]=high[i];        sort(tmp+L[bl[l]],tmp+R[bl[l]]+1);        for(int i=L[bl[l]];i<=R[bl[l]];++i) HIGH[i]=tmp[i];        return;    }    for(int i=l;i<=R[bl[l]];++i) high[i]+=w;    for(int i=L[bl[l]];i<=R[bl[l]];++i) tmp[i]=high[i];    sort(tmp+L[bl[l]],tmp+R[bl[l]]+1);    for(int i=L[bl[l]];i<=R[bl[l]];++i) HIGH[i]=tmp[i];    for(int i=L[bl[r]];i<=r;++i) high[i]+=w;    for(int i=L[bl[r]];i<=R[bl[r]];++i) tmp[i]=high[i];    sort(tmp+L[bl[r]],tmp+R[bl[r]]+1);    for(int i=L[bl[r]];i<=R[bl[r]];++i) HIGH[i]=tmp[i];    for(int i=bl[l]+1;i
         
          >1;        if(HIGH[mid]>=w) ok=mid,r=mid-1;        else l=mid+1;    }    return y-ok+1;}void ask(int l,int r,int w){    int ans=0;    if(bl[l]==bl[r])    {        for(int i=l;i<=r;++i)             if(high[i]+tag[bl[l]]>=w) ans++;        cout<
          
           <<'\n'; return; } for(int i=l;i<=R[bl[l]];++i) if(high[i]+tag[bl[l]]>=w) ans++; for(int i=L[bl[r]];i<=r;++i) if(high[i]+tag[bl[r]]>=w) ans++; for(int i=bl[l]+1;i