教主的魔法

区间第k大问题

#include<set>
#include<queue>
#include<vector>
#include<string>
#include<math.h>
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 1000050
#define SQ 1005
#define ll long long
int mark[SQ],size[SQ];
int n,m,a[maxn],sq;
int st[SQ],ed[SQ],bel[maxn];
vector<int> arr[SQ];
int read()                       //读取输入的数值
{
  int ans = 0;
  char c = getchar();
  while (!isdigit(c))            //判断字符是否为数字
    c = getchar();
  while (isdigit(c))
  {
    ans = ans * 10 + c - '0';   //进位
    c = getchar();
  }
  return ans;
}
void init(int n){              //初始化
  sq=sqrt(n);                  //块大小
  for(int i=1;i<=sq;i++){      //遍历块
    st[i]=n/sq*(i-1)+1;        //块的第一个元素位置
    ed[i]=n/sq*i;              //块的最后一个元素位置
  }
  ed[sq]=n;                    //最后不够凑成一块的余数融入到最后一块里
  for(int i=1;i<=sq;i++){      //遍历所有元素位置
    for(int j=st[i];j<=ed[i];j++)
      bel[j]=i;               //标记序列的所属块
    size[i]=ed[i]-st[i]+1;    //标记每块的大小
  }
}
void update(int index){      //数据
  for(int i=0;i<size[index];i++) 
    arr[index][i]=a[st[index]+i];                 //更新arr数据
  sort(arr[index].begin(),arr[index].end());      //更新数值，重新排序
}
int main(void){
  int x,y,z;
  n=read();
  m=read();
  init(n);
  for(int i=1;i<=n;i++)     //读取序列
    a[i]=read();
  for(int i=1;i<=sq;i++)    //放入序列
    for(int j=st[i];j<=ed[i];j++)
      arr[i].push_back(a[j]);
  for(int i=1;i<=sq;i++)    //块内排序
    sort(arr[i].begin(),arr[i].end());
  while(m--){               //执行操作
    char c;
    scanf(" %c",&c);
    x=read(); y=read(); z=read();
    if(c=='M'){            //查询序列
      if(bel[x]==bel[y]){  //左右区间在同一块
        for(int i=x;i<=y;i++)                     //遍历
          a[i]+=z;         //加z
        update(bel[x]);
        continue;         //跳过之后的操作
      }
      for(int i=x;i<=ed[bel[x]];i++)             //左区间所属的的块内遍历
        a[i]+=z;
      for(int i=st[bel[y]];i<=y;i++)             //右区间所属的块内遍历
        a[i]+=z;
      update(bel[x]);
      update(bel[y]);
      for(int i=bel[x]+1;i<bel[y];i++)           //整块维护
        mark[i]+=z;
    }
    else{               //修改序列
      int tot=0;        //小于等于的个数
      if(bel[x]==bel[y]){                       //左右区间在同一个块内
        for(int i=x;i<=y;i++){
          if(a[i]+mark[bel[x]]>=z)              //块内序列加上块的懒标记
            tot++;
        }
        printf("%d\n",tot);
        continue;      //跳过之后的操作
      }
      for(int i=x;i<=ed[bel[x]];i++)           //左区间所属的的块内遍历
        if(a[i]+mark[bel[x]]>=z)
          tot++;
      for(int i=st[bel[y]];i<=y;i++)           //右区间所属的块内遍历
        if(a[i]+mark[bel[y]]>=z)
          tot++;
      for(int i=bel[x]+1;i<bel[y];i++)         //区间内的整装块
        tot+=arr[i].end()-lower_bound(arr[i].begin(),arr[i].end(),z-mark[i]); //arr排序好的块内筛选，找到下标与块内的结束下标相减
      printf("%d\n",tot);
    }
  }
  return 0;
}

笔记：分块算法的思想可以概括为 “ 整块打包维护，碎片逐个枚举” 。树状数组和线段树都是二分思想的，分块就是在小范围里使用暴力算法。平时维护是整体维护，提高了效率。