P2801 教主的魔法

P2801 教主的魔法

洛谷题解

#include
#include
#include
#include
#include
#define long long int
using namespace std;
int a[1000005],d[1000005],block,n,q,x,y,z,lf[1000005],rg[1000005],num,belong[1000005],tag[1000005];
char op[3];
void build(){
  block = sqrt(n);
  num = n / block;
  if(n % block) num++;
  for(int i = 1; i <= num; i++){
    lf[i] = (i - 1) * block + 1, rg[i] = i * block;
  }//循环里写的sort
  rg[num] = n;
  for(int i = 1; i <= n; i++)
    belong[i] = (i - 1)/block + 1;
  for(int i = 1; i <= num; i++)
  	sort(d + lf[i], d + rg[i] + 1);//每一段都进行排序
}
void add(int l, int r, int val){
  int st = belong[l], ed = belong[r];
  if(st == ed){
    for(int i = l; i <= r; i++)
      a[i] += val;
    for(int i = lf[st]; i <= rg[st]; i++) d[i] = a[i];
    sort(d + lf[st], d + rg[st] + 1);
    return;
  }
  if(l != lf[st]){
    for(int i = l; i <= rg[st]; i++) a[i] += val;
    for(int i = lf[st]; i <= rg[st]; i++) d[i] = a[i];
    sort(d + lf[st], d + rg[st] + 1);
    st++;
  }
  if(r != rg[ed]){
    for(int i = lf[ed]; i <= r; i++) a[i] += val;
    for(int i = lf[ed]; i <= rg[ed]; i++) d[i] = a[i];
    sort(d + lf[ed], d + rg[ed] + 1);
    ed--;
  }
  for(int i = st; i <= ed; i++) tag[i] += val;//+=
}
int query(int l, int r, int c){
  int ans = 0, st = belong[l], ed = belong[r];
  if(st == ed){
    for(int i = l; i <= r; i++)
      if(a[i] + tag[st] >= c) ans++;
    return ans;
  }
  if(l != lf[st]){
    for(int i = l ; i <= rg[st]; i++)
      if(a[i] + tag[st] >= c) ans++;//error:without tag
    st++;
  }
  if(r != rg[ed]){
    for(int i = lf[ed] ; i <= r; i++)
      if(a[i] + tag[ed] >= c) ans++;//error:without tag
    ed--;
  }
  for(int i = st; i <= ed; i++){
  	if(c >  d[rg[i]] + tag[i] ) continue;//如果这一块最大的值都小于c，则continue
  	int id = lower_bound(d + lf[i], d + rg[i], c - tag[i]) - d;
    ans += rg[i] - id + 1;
  }
  return ans;
}
signed main(){
  scanf("%d%d",&n,&q);
  for(int i = 1; i <= n; i++){
    scanf("%d",&a[i]);//原数组
    d[i] = a[i];//排序数组
  }
  build();
  for(int i = 1; i <= q; i++){
	  scanf("%s%d%d%d",op,&x,&y,&z);
	  if(op[0] == 'M'){
	    add(x,y,z);
	  }else if(op[0] == 'A'){
	    printf("%d\n", query(x,y,z));
	  }
  }
  return 0;
}