526互联

Luogu P2801 教主的魔法(Loj 数列分块入门 2)

发布时间 2023-05-22 19:48:31作者: 觉清风

教主的魔法

题目描述

教主最近学会了一种神奇的魔法，能够使人长高。于是他准备演示给 XMYZ 信息组每个英雄看。于是 \(N\) 个英雄们又一次聚集在了一起，这次他们排成了一列，被编号为 \(1, 2, \ldots, N\)。

每个人的身高一开始都是不超过 \(1000\) 的正整数。教主的魔法每次可以把闭区间 \([L, R]\)（\(1≤L≤R≤N\)）内的英雄的身高全部加上一个整数 \(W\)。（虽然 \(L=R\) 时并不符合区间的书写规范，但我们可以认为是单独增加第 \(L(R)\) 个英雄的身高）

CYZ、光哥和 ZJQ 等人不信教主的邪，于是他们有时候会问 WD 闭区间 \([L, R]\) 内有多少英雄身高大于等于 \(C\)，以验证教主的魔法是否真的有效。

WD 巨懒，于是他把这个回答的任务交给了你。

输入格式

第 \(1\) 行为两个整数 \(N, Q\)。\(Q\) 为问题数与教主的施法数总和。

第 \(2\) 行有 \(N\) 个正整数，第 \(i\) 个数代表第 \(i\) 个英雄的身高。

第 \(3\) 到第 \(Q+2\) 行每行有一个操作：

  1. 若第一个字母为 M，则紧接着有三个数字 \(L, R, W\)。表示对闭区间 \([L, R]\) 内所有英雄的身高加上 \(W\)。

  2. 若第一个字母为 A，则紧接着有三个数字 \(L, R, C\)。询问闭区间 \([L, R]\) 内有多少英雄的身高大于等于 \(C\)。

输出格式

对每个 A 询问输出一行，仅含一个整数，表示闭区间 \([L, R]\) 内身高大于等于 \(C\) 的英雄数。

样例 #1

样例输入 #1

5 3
1 2 3 4 5
A 1 5 4
M 3 5 1
A 1 5 4

样例输出 #1

2
3

提示

【输入输出样例说明】

原先 \(5\) 个英雄身高为 \(1, 2, 3, 4, 5\)，此时 \([1, 5]\) 间有 \(2\) 个英雄的身高大于等于 \(4\)。教主施法后变为 \(1, 2, 4, 5, 6\)，此时 \([1, 5]\) 间有 \(3\) 个英雄的身高大于等于 \(4\)。

【数据范围】

对于 \(30\%\) 的数据，\(N≤1000\)，\(Q≤1000\)。

对于 \(100\%\) 的数据，\(N≤10^6\)，\(Q≤3000\)，\(1≤W≤1000\)，\(1≤C≤10^9\)。

\(\text{upd 2022.8.18}\)：新增加一组 Hack 数据。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>

using namespace std;

int block, n, q;
//add[i]表示第i个块整个块要加的值 pos[i]表示第i个数所处的块
int add[5211314], a[5211314], pos[5211314];
vector<int> b[5210];//b[i]表示第i个块快速排序完后的顺序
string str;

inline void Add(int lift, int right, int val) {
	int l = pos[lift], r = pos[right];
	if (l == r) {
        //在一个块内直接暴力区间加
		b[l].clear();
		for (int i = lift; i <= right; ++ i) 
			a[i] += val;
		for (int i = (l - 1) * block + 1; i <= min(l * block, n); ++ i) 
			b[l].push_back(a[i]);
		sort(b[l].begin(), b[l].end());
	}
	else {
		b[l].clear();
		b[r].clear();
        //对每个块的值加val
		for (int i = l + 1; i <= r - 1; ++ i) {
			add[i] += val; 
		}
        //暴力修改左右未完全覆盖块的值
		for (int i = lift; i <= l * block; ++ i) {
			a[i] += val;
		}
		for (int i = (r - 1) * block + 1; i <= right; ++ i) {
			a[i] += val;
		}
        //将修改完的左右未完全覆盖块的值重新插入b里并排序
		for (int i = (l - 1) * block + 1; i <= min(l * block, n); ++ i) {
			b[l].push_back(a[i]);
		}
		for (int i = (r - 1) * block + 1; i <= min(r * block, n); ++ i) {
			b[r].push_back(a[i]);
		}
		sort(b[l].begin(), b[l].end());
		sort(b[r].begin(), b[r].end());
	}
	return;
}

inline int Ask(int lift, int right, int val) {
	int l = pos[lift], r = pos[right], ans = 0;
	if (l == r) {
        //左右端点在同一个块内直接暴力
		for (int i = lift; i <= right; ++ i) {
			if (a[i] + add[l] >= val) ans ++;
		}
		return ans;
	}
	else {
        //不在同一个块内则二分寻找每个块内第一个大于等于val的值的位置
		for (int i = l + 1, subscript; i <= r - 1; ++ i) {
			subscript = lower_bound(b[i].begin(), b[i].end(), val - add[i]) - b[i].begin();
            //防止没找到第一个大于等于val而返回最后一个值的下标
			if (b[i][subscript] >= val - add[i]) {
				ans += (block - subscript);
			}
		}
        //暴力左右两个未完全覆盖的块
		for (int i = lift; i <= l * block; ++ i) {
			if (a[i] + add[l] >= val) ans ++;
		}
		for (int i = (r - 1) * block + 1; i <= right; ++ i) {
			if (a[i] + add[r] >= val) ans ++;
		}
		return ans;
	}
}

int main() {
	cin >> n >> q;
	block = sqrt(n);//块长
	for (int i = 1; i <= n; ++ i) {
		cin >> a[i];
		pos[i] = (i - 1) / block + 1;
		b[pos[i]].push_back(a[i]);
	}
	for (int i = 1; i <= pos[n]; ++ i) { 
		sort(b[i].begin(), b[i].end());
	}
	for (int i = 1, l, r, w; i <= q; ++ i) {
		cin >> str;
		cin >> l >> r >> w;
		if (str == "A") cout << Ask(l, r, w) << endl;
		else Add(l, r, w);
	}
    return 0;
}