#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;
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 = 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:135:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
135 | freopen(NAME".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
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".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
25 ms |
7260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
25 ms |
4864 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
19 ms |
4700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
41 ms |
7256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
25 ms |
7260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
31 ms |
7380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
76 ms |
7508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
26 ms |
7428 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
53 ms |
8016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
