#include<bits/stdc++.h>
#define ii pair<int, int>
#define ll pair<long long, long long>
#define fi first
#define se second
#define pb push_back
using namespace std;
const int mod[2] = {1000000007, 998244353};
const int N = 1e5 + 1;
const string NAME = "";
const int lim = 2147483647;
//const long long lim = 9223372036854775807;
const double pi = acos(-1);
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int n, m, a[N], tree[4 * N], bonus[4 * N];
#ifdef i128
ostream & operator << (ostream &out, const __int128 &x){
__int128 i = x;
vector<int> digits;
while(i > 0){
digits.pb(i % 10);
i /= 10;
}
reverse(digits.begin(), digits.end());
for(auto x : digits)
out << x;
return out;
}
#endif
void down(int s){
int t = bonus[s];
bonus[2 * s] += t;
tree[2 * s] += t;
bonus[2 * s + 1] += t;
tree[2 * s + 1] += t;
bonus[s] = 0;
}
void build(int s, int l, int r){
if(l == r){
tree[s] = a[l];
return;
}
int mid = (l + r) / 2;
build(2 * s, l, mid);
build(2 * s + 1, mid + 1, r);
tree[s] = max(tree[2 * s], tree[2 * s + 1]);
}
void update(int s, int l, int r, int u, int v, int val){
if(v < l || u > r)
return;
if(u <= l && r <= v){
tree[s] += val;
bonus[s] += val;
return;
}
int mid = (l + r) / 2;
down(s);
update(2 * s, l, mid, u, v, val);
update(2 * s + 1, mid + 1, r, u, v, val);
tree[s] = max(tree[2 * s], tree[2 * s + 1]);
}
int get(int s, int l, int r, int u, int v){
if(v < l || u > r)
return 0;
if(u <= l && r <= v)
return tree[s];
int mid = (l + r) / 2;
down(s);
return max(get(2 * s, l, mid, u, v), get(2 * s + 1, mid + 1, r, u, v));
}
void inp(){
cin >> n >> m;
for(int i = 1; i <= n; ++i){
cin >> a[i];
}
}
void solve(){
sort(a + 1, a + n + 1);
build(1, 1, n);
while(m--){
char c;
int x, y;
cin >> c >> x >> y;
if(c == 'F'){
int l = 1, r = n;
int idx = 1;
while(l <= r){
int mid = (l + r) / 2;
if(get(1, 1, n, mid, mid) >= y){
idx = mid;
r = mid - 1;
}
else l = mid + 1;
}
// cout << idx << "\n";
if(idx + x - 1 > n){
update(1, 1, n, idx, n, 1);
}
else{
int tmp = get(1, 1, n, idx + x - 1, idx + x - 1) + 1;
if(tmp <= get(1, 1, n, idx + x, idx + x)){
update(1, 1, n, idx, idx + x - 1, 1);
}
else{
int tmp2 = tmp - 1;
int L = idx, R = n;
l = 1, r = n;
while(l <= r){
int mid = (l + r) / 2;
if(get(1, 1, n, mid, mid) >= tmp2){
L = mid;
r = mid - 1;
}
else l = mid + 1;
}
l = 1, r = n;
while(l <= r){
int mid = (l + r) / 2;
if(get(1, 1, n, mid, mid) <= tmp2){
R = mid;
l = mid + 1;
}
else r = mid - 1;
}
update(1, 1, n, idx, idx + x - 1, 1);
update(1, 1, n, L, idx + x - 1, -tmp);
update(1, 1, n, L, idx + x - 1, tmp2);
update(1, 1, n, idx + x, R, -tmp2);
update(1, 1, n, idx + x, R, tmp);
}
}
}
else{
int l = 1, r = n;
int L = 1, R = n;
while(l <= r){
int mid = (l + r) / 2;
if(get(1, 1, n, mid, mid) >= x){
L = mid;
r = mid - 1;
}
else l = mid + 1;
}
l = 1, r = n;
while(l <= r){
int mid = (l + r) / 2;
if(get(1, 1, n, mid, mid) <= y){
R = mid;
l = mid + 1;
}
else r = mid - 1;
}
if(get(1, 1, n, L, L) > y || get(1, 1, n, R, R) < x){
cout << "0\n";
}
else{
// cout << L << " " << R << "\n";
cout << R - L + 1 << "\n";
}
}
// for(int i = 1; i <= n; ++i){
// cout << get(1, 1, n, i, i) << " ";
// }
// cout << "\n";
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifdef TimeCalculation
auto starttime = chrono::high_resolution_clock::now();
#endif
if(fopen((NAME + ".inp").c_str(), "r")){
freopen((NAME + ".inp").c_str(), "r", stdin);
freopen((NAME + ".out").c_str(), "w", stdout);
}
inp();
solve();
#ifdef TimeCalculation
auto endtime = chrono::high_resolution_clock::now();
auto duration = chrono::duration_cast<chrono::milliseconds>(endtime - starttime).count();
cout << "\n=====" << "\nTime elapsed: " << duration << " ms\n";
#endif
}
/*
5 7
1 3 2 5 2
F 2 1
C 3 6
F 2 3
C 6 8
F 2 1
F 2 2
C 3 5
*/
Compilation message
grow.cpp: In function 'int main()':
grow.cpp:184:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
184 | freopen((NAME + ".inp").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
grow.cpp:185:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
185 | freopen((NAME + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
417 ms |
3660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
239 ms |
2652 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
243 ms |
2984 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
384 ms |
3000 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
451 ms |
3408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
448 ms |
3392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
468 ms |
3756 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
504 ms |
3668 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
503 ms |
3744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
