#include <bits/stdc++.h>
using namespace std;
const long long N = 2e5 + 5 ;
#define ll long long
#define endl '\n'
struct segmentTree {
int n;
vector<ll> sum, lz, sumB , maxi , mini;
void init(int _n, int b[]) {
n = _n;
sum.assign(4 * n + 6, 0);
lz.assign(4 * n + 6, 0);
sumB.assign(4 * n + 6, 0);
maxi.assign(4 * n + 6, 0);
mini.assign(4 * n + 6, 0);
build(b, 1, 1, n);
}
void build(int b[], int i, int l, int r) {
if (l == r) {
sumB[i] = b[l];
return;
}
int m = (l + r) >> 1;
build(b, i << 1, l, m); build(b, i << 1 | 1, m + 1, r);
sumB[i] = sumB[i << 1] + sumB[i << 1 | 1];
maxi[i] = max(maxi[i<<1] , maxi[i<<1 | 1]) ;
mini[i] = min(mini[i<<1] , mini[i<<1 | 1]) ;
}
void pushdown(int i) {
for(int j=i<<1; j<=(i<<1|1); ++j) {
sum[j] += lz[i] * sumB[j];
maxi[j] += lz[i] ;
mini[j] += lz[i] ;
lz[j] += lz[i];
}
lz[i] = 0;
}
void upd(int i, int l, int r, int u, int v, ll delta) {
if (l > r || u > v || l > v || r < u) return;
if (l >= u && r <= v) {
sum[i] += delta * sumB[i];
maxi[i] += delta ;
mini[i] += delta ;
lz[i] += delta;
return;
}
pushdown(i);
int m = (l + r) >> 1;
upd(i << 1, l, m, u, v, delta); upd(i << 1 | 1, m + 1, r, u, v, delta);
sum[i] = sum[i << 1] + sum[i << 1 | 1];
maxi[i] = max(maxi[i<<1] , maxi[i<<1 | 1]) ;
mini[i] = min(mini[i<<1] , mini[i<<1 | 1]) ;
}
void upd(int u, int v, ll delta) {
upd(1, 1, n, u, v, delta);
}
ll get(int i, int l, int r, int u, int v) {
if (l > r || u > v || l > v || r < u) return 0;
if (l >= u && r <= v) return sum[i];
pushdown(i);
int m = (l + r) >> 1;
return get(i << 1, l, m, u, v) + get(i << 1 | 1, m + 1, r, u, v);
}
ll get(int u, int v) {
return get(1, 1, n, u, v);
}
};
int a[N] , b[N] ;
segmentTree st ;
int n , q ;
int getlast(int node , int l , int r , int x)
{
if(st.mini[node]>x) return l-1 ;
if(l==r) return l ;
int md = (l+r)/2 ;
if(x>=st.mini[2*node+1]) return getlast(2*node+1 , md+1 , r , x) ;
else return getlast(2*node , l , md , x) ;
}
int getlast(int x)
{
return getlast(1 , 1 , n , x) ;
}
int getfirst(int node , int l , int r , int x)
{
if(st.maxi[node]<x) return r+1 ;
if(l==r) return l ;
int md = (l+r)/2 ;
if(st.maxi[2*node]>=x) return getfirst(2*node , l , md , x) ;
else return getfirst(2*node+1 , md+1 , r , x) ;
}
int getfirst(int x)
{
return getfirst(1 , 1 , n , x) ;
}
int main()
{
// ios::sync_with_stdio(0), cin.tie(0),cout.tie(0) ;
cin>>n>>q ;
for(int i = 1 ; i<=n ; i++){
cin>>a[i] ;
b[i] = 1 ;
}
st.init(n , b) ;
sort(a+1 , a+n+1) ;
for(int i = 1 ; i<=n ; i++){
st.upd(i , i ,a[i]) ;
}
// for(int i = 1 ; i<=n ; i++){
// cout<<st.get(i , i)<<' ';
// }
// cout<<endl;
// int m ; cin>>m ;
// while(m--){
// int a, b ; cin>>a>>b ;
// cout<<getfirst(a)<<' '<<getlast(b)<<endl;
// }
while(q--){
char c ; cin>>c ;
if(c=='F'){
int c , h ; cin>>c>>h ;
int l = getfirst(h) ;
c = min(c , n - l+1) ;
int r = min(n , l+c-1) ;
int x = st.get(r , r) ;
int lr = getlast(x-1) ;
int rr = getlast(x) ;
int lefties = max(0 , lr - l+1) ;
int rl = (rr - (c - lefties) +1) ;
// upd [l , lr] , upd[rl , rr]
if(l<=lr){
st.upd(l , lr , 1) ;
}
if(rl<=rr){
st.upd(rl , rr , 1) ;
}
}
else{
int a , b ; cin>>a>>b ;
cout<<getlast(b) - getfirst(a)+1<<endl;
}
// for(int i = 1 ; i<=n ; i++){
// cout<<st.get(i , i)<<' ';
// }
// cout<<endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
196 ms |
14944 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
165 ms |
1632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
198 ms |
1748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
184 ms |
11100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
181 ms |
12652 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
189 ms |
13632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
303 ms |
14692 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
214 ms |
14324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
279 ms |
16852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
