1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
| #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;
}
|
