#define COPYRIGHT CODE BY TRINH TUAN NGHIA
#include<bits/stdc++.h>
#define Boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("popcnt")
#define ll long long
#define endl "\n"
#define st first
#define nd second
#define ii pair <ll,ll>
#define iii pair <ll,ii>
#define iiii pair <ii,ii>
#define pb push_back
#define NAME "growingtrees"
#define int long long
using namespace std;
const ll N = 1e5 + 10;
ll a[N];
ll tree[4 * N];
ll lazy[4 * N];
ll n, m;
void buildTree(ll id, ll l, ll r){
if (l == r){
tree[id] = a[l];
return;
}
ll m = (l + r) >> 1;
buildTree(id * 2 , l, m);
buildTree(id * 2 + 1, m + 1, r);
tree[id] = max(tree[id * 2], tree[id * 2 + 1]);
}
void down(ll id, ll l, ll r){
ll m = (l + r) >> 1;
if (l < r){
tree[id * 2] += lazy[id];
tree[id * 2 + 1] += lazy[id];
lazy[id * 2] += lazy[id];
lazy[id * 2+ 1] += lazy[id];
}
lazy[id] = 0;
}
void update(ll id, ll l, ll r, ll u, ll v, ll val){
if (v < l or r < u)return ;
if (u <= l and r <= v){
tree[id] += val;
lazy[id] += val;
return;
}
down(id , l, r);
ll m = (l + r) >> 1;
update(id * 2, l, m, u, v, val);
update(id * 2 + 1, m + 1, r, u, v, val);
tree[id] = max(tree[id * 2], tree[id * 2 + 1]);
}
ll get(ll id, ll l, ll r, ll u){
if (u < l or u > r)return 0;
if (l == r)return tree[id];
ll m = (l + r) >> 1;
down(id, l ,r );
return max(get(id * 2, l, m,u), get(id * 2 + 1, m + 1, r, u));
}
ll tknp(ll id, ll l, ll r, ll x){
ll m = (l +r ) >> 1;
if (tree[id] < x)return n + 1;
if (l == r)return l;
down(id , l, r);
if (tree[id * 2] >= x)return tknp(id * 2, l ,m, x);
else return tknp(id * 2 + 1, m + 1, r,x);
}
void inp (){
cin >> n >> m;
for (int i = 1; i <= n; ++i){
cin >> a[i];
}
sort(a + 1, a + n + 1);
//a[n + 1] = 1e18;
}
void solve(){
buildTree(1,1,n);
while (m -- ){
char type;
ll c,h, can1, can2;
cin >> type;
if (type == 'F'){
cin >> c >> h;
ll chot1 = tknp(1,1,n,h);
if (chot1 == n + 1)continue;
ll chot2 = min(n,chot1 + c - 1);
ll daubuoi = get(1,1,n,chot2);
ll concac = tknp(1,1,n,daubuoi + 1) - 1;
ll concu = tknp(1,1,n,daubuoi);
update (1,1,n,chot1,concu - 1, 1);
ll conlai = c - (daubuoi - 1 - chot1 + 1);
update(1,1,n, concac - conlai + 1, concac, 1);
// cout << conlai << " " << concac << endl;
}
else {
cin >> can1 >> can2;
ll chot1 = tknp(1,1,n,can1);
ll chot2;
chot2 = tknp(1,1,n,can2 + 1);
// cout << "dcm " << endl;
// for (int i = 1; i <= n; ++i){
// cout << get(1,1,n,i) << " ";
// }
// cout << endl;
// cout << chot1 << " " << chot2 << " " << chot2 - chot1 + 1 << endl;
cout << chot2 - chot1 << endl;
}
}
// while(m--){
// char c;
// int x, y;
// cin >> c >> x >> y;
// if(c == 'F'){
// int tmp1 = tknp(1, 1, n, y);
// if(tmp1 == n + 1)
// continue;
// int tmp2 = min(tmp1 + x - 1, n);
// int v = get(1, 1, n, tmp2);
// int p = tknp(1, 1, n, v);
// int q = tknp(1, 1, n, v + 1) - 1;
// update(1, 1, n, tmp1, p - 1, 1);
// update(1, 1, n, q - tmp2 + p, q, 1);
// }
// else{
// cout << tknp(1, 1, n, y + 1) - tknp(1, 1, n, x) << "\n";
// }
// }
}
signed main (){
if (fopen(NAME".inp", "r")){
freopen(NAME".inp", "r", stdin);
freopen(NAME".out", "w", stdout);
}
Boost;
inp();
solve();
}
/*
input
*/
/*
output
*/
Compilation message
grow.cpp: In function 'void down(long long int, long long int, long long int)':
grow.cpp:34:8: warning: unused variable 'm' [-Wunused-variable]
34 | ll m = (l + r) >> 1;
| ^
grow.cpp: In function 'int main()':
grow.cpp:136:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
136 | freopen(NAME".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
grow.cpp:137:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
137 | freopen(NAME".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
7432 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
4696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
4696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
34 ms |
7256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
38 ms |
7256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
38 ms |
7256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
73 ms |
7508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
7452 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
52 ms |
7760 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
