参考自官方的博客：https://blog.nowcoder.net/n/699c671bf3e24676a6df403f68686d73
题目
题面
有一个 n 个数的数组，代表 n 栋建筑，有如下两种操作：
- 修改：区间 l 到 r 内的建筑增高 k（正整数）
- 查询：对于某个位置 x，求 y 的数目（ y \gt xy>x ，且对于位置 y ，位置 x 到位置 y 的这段区间的最小值是位置 y 的值）
Input
第一行两个数字 n 和 m ， 表示数字个数和操作个数
第二行 n 个数字，表示建筑高度
后面 m 行指令：c l r k
或者：q x
数据范围： 1≤n,m≤2×10^5,1≤l,r≤n
1≤x≤n,1≤k≤10^4
Output
对于每个查询，输出答案，每个答案一行
Examples
Input
5 5
1 2 3 4 3
q 3
c 1 3 3
q 2
c 5 5 4
q 5Output
1
2
0思路
思路就是线段树，但是要对val，在l与r区间内能组成下降数列的数不断进行更新（感觉有点像dp了。。。）直接用线段树的话就会超时（还是太菜了）题目中y的数量实际上就是从x开始到最后的递减数列中数的数量（每次遇到小的数就放在后面，不能自己选择），我是看的官方的代码打的注释（把结构体当类用，看起来是真的吃力。。。。还是太菜了）
代码
#include<iostream>
#include<algorithm>
#include<time.h>
using namespace std;
#define mid ((l+r)>>1)
#define MAX 200005
struct node {
node() {
minn = value = add = 0;
}
void init() {
minn = value = add = 0;
}
int minn;
int value;// value为在l - r中前半部分的最小值与后半部分区间内能组成下降数列的数（即以前半部分的最小值min为首，在m - r之间取最多的数与min组成递减数列）
int add;//其子节点的所有数字加add
};
struct Segt {
int arr[MAX];
node tree[MAX << 2];
void push_down(int p) {
if (tree[p].add != 0) {
tree[(p << 1)].add += tree[p].add;
tree[((p << 1) | 1)].add += tree[p].add;
tree[(p << 1)].minn += tree[p].add;
tree[((p << 1) | 1)].minn += tree[p].add;
tree[p].add = 0;
}
}
void push_up(int l, int r, int p) {//向上跟新父节点的值
//bool flag = true;
tree[p].minn = min(tree[(p << 1)].minn, tree[((p << 1) | 1)].minn);
int m = mid;
int val = tree[(p << 1)].minn;
tree[p].value = que(m + 1, val, m + 1, r, ((p << 1) | 1));
}
void build(int l, int r, int p) {//建立线段树
tree[p].init();
if (l == r) {
tree[p].minn = arr[l];
tree[p].value = 0;
return;
}
int m = mid;
build(l, m, (p << 1)); build(m + 1, r, ((p << 1) | 1));
push_up(l, r, p);
}
void update(int a, int b, int k, int l, int r, int p) {//区间修改
if (l >= a && r <= b) {
tree[p].minn += k;
tree[p].add += k;
return;
}
push_down(p);
int m = mid;
if (a <= m) update(a, b, k, l, m, (p << 1));
if (b > m) update(a, b, k, m + 1, r, ((p << 1) | 1));
push_up(l, r, p);
}
int get_val(int pos, int l, int r, int p) {//取得pos点的值（单点查询）
if (l == r) return tree[p].minn;
push_down(p);
int m = mid;
if (pos <= m) return get_val(pos, l, m, (p << 1));
else return get_val(pos, m + 1, r, ((p << 1) | 1));
// push_up(p);
}
int que(int a, int& val, int l, int r, int p) {//返回 在a点之前的最小值为val，在l与r区间内能组成下降数列的数（即以val为首，在l-r之间取最多的数与val组成递减数列）
if (a > r) return 0;//如果a位置在r之后，那么在区间l-r内就没有可以没做条件的数
int m = mid;
//cout << l << ' ' << r << endl;
if (l != r) push_down(p);//更新子节点数值
if (l >= a) {
if (tree[p].minn <= val) {//只有后面数值的最小值比val小才能组成
if (l == r) {
//cout << "#" << a<<" "<< val << ' ' << l << ' ' << tree[p].minn << endl;
val = tree[p].minn;//之后的数要小于val
return 1;//minn是一个可以接在val后面的数
}
if (tree[(p << 1)].minn <= val) {//如果r-l的前半部分的最小值比val小
int an = que(a, val, l, m, (p << 1));//求l-mid与val构成的递减数组
val = tree[p].minn;//更新最小值
// cout << "@" << val << ' ' << l << ' ' << r << ' ' << an << ' ' << tree[p].value << endl;
return an + tree[p].value;//因为value为在l-r中前半部分的最小值与后半部分区间内能组成下降数列的数（即以前半部分的最小值min为首，在m-r之间取最多的数与min组成递减数列）
}
else {
return que(a, val, m + 1, r, ((p << 1) | 1));//如果前半部分的最小值比val大，则比较后半部分与其可以构成的数的数量
}
}
else {
return 0;
}
}
//当a不在l之前时
if (a <= m) {//a在前半部分则搜索前半部分，看a在前半部分可以构成含有多少数的递减数组
int an = que(a, val, l, m, (p << 1));
if (val == tree[(p << 1)].minn) {//如果val等于前半部分的最小值，那么说明可以与前半部分进行组合，之后就加上value（前半部分的最小值与后半部分区间内能组成下降数列的数）
val = tree[p].minn;
return an + tree[p].value;
}
else {
return an + que(a, val, m + 1, r, ((p << 1) | 1));//不等于的话，即前半部分没有可以配对的数，则an==0，看之后的数与其配对的数量
}
}
else {
return que(a, val, m + 1, r, ((p << 1) | 1));//如果m在后半部分则搜索后半部分
}
}
};
Segt segt;
void make_ans(istream& in, ostream& out) {//输入，输出流
int n, m;
in >> n >> m;//等价于 cin>>
for (int i = 1; i <= n; i++) {
in >> segt.arr[i];
}
segt.build(1, n, 1);
while (m--) {
char ch;
//cout << "------" << endl;
//for(int i = 1; i <= n; i++) cout << segt.get_val(i,1,n,1) << ' '; cout << endl;
//cout << "------" << endl;
in >> ch;
if (ch == 'c') {
int l, r, k;
in >> l >> r >> k;
segt.update(l, r, k, 1, n, 1);
}
else {
int x;
in >> x;
int val = segt.get_val(x, 1, n, 1);//取得x点的值
// cout << val << endl;
out << segt.que(x + 1, val, 1, n, 1) << endl;//输出最小值为val时，在x+1之后有多少数字与其构成递减数列
}
}
}
int main(void) {
freopen("F:/y.txt","r",stdin);
make_ans(cin, cout);
return 0;
}
