#include <bits/stdc++.h>
using namespace std;
const long long N = 2e5 + 5 ;
#define ll long long
#define endl '\n'
struct segmentTree {
ll n;
vector<ll> sum, lz, sumB , maxi , mini;
void init(ll _n, ll 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, -2e9);
mini.assign(4 * n + 6, 2e9);
build(b, 1, 1, n);
}
void build(ll b[], ll i, ll l, ll r) {
if (l == r) {
sumB[i] = b[l];
mini[i] = 0 ;
maxi[i] = 0 ;
return;
}
ll 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];
}
void pushdown(ll i) {
for(ll 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(ll i, ll l, ll r, ll u, ll 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);
ll 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(ll u, ll v, ll delta) {
upd(1, 1, n, u, v, delta);
}
ll f(ll x , ll y , ll tp)
{
if(tp==1) return x+y ;
if(tp==2) return min(x , y) ;
return max(x , y) ;
}
ll id(ll tp)
{
if(tp==1) return 0 ;
if(tp==2) return 2e9 ;
return -2e9 ;
}
ll get(ll i, ll l, ll r, ll u, ll v , ll tp) {
if (l > r || u > v || l > v || r < u) return id(tp);
if (l >= u && r <= v) return(tp == 1 ? sum[i] : tp==2 ? mini[i] : maxi[i]);
pushdown(i);
ll m = (l + r) >> 1;
return f(get(i << 1, l, m, u, v , tp) , get(i << 1 | 1, m + 1, r, u, v , tp) , tp);
}
ll get2(ll node , ll l , ll r , ll idx){
if(l==r) return sum[node];
pushdown(node) ;
ll md = (l+r)/2;
if(idx<=md) return get2(2*node,l,md,idx);
return get2(2*node+1,md+1,r,idx);
}
ll get(ll u, ll v , ll tp = 1) {
return get(1, 1, n, u, v , tp);
}
};
ll a[N] , b[N] ;
segmentTree st ;
ll n , q ;
ll getlast(ll x)
{
ll l = 1 , r = n , p = 0 ;
while(l<=r){
ll md = (l+r)/2 ;
ll y = st.get2(1 , 1 , n , md) ;
if(y<=x){
p = md ;
l = md+1 ;
}
else r = md-1 ;
}
return p ;
}
ll getfirst(ll x)
{
ll l = 1 , r = n , p = n+1 ;
while(l<=r){
ll md = (l+r)/2 ;
ll y = st.get2(1 , 1 , n , md) ;
if(y>=x){
p = md ;
r = md-1 ;
}
else l = md+1 ;
}
return p ;
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0),cout.tie(0) ;
cin>>n>>q ;
for(ll i = 1 ; i<=n ; i++){
cin>>a[i] ;
b[i] = 1 ;
}
st.init(n , b) ;
sort(a+1 , a+n+1) ;
for(ll i = 1 ; i<=n ; i++){
st.upd(i , i ,a[i]) ;
}
// ll m ; cin>>m ;
// while(m--){
// ll a, b ; cin>>a>>b ;
// cout<<getfirst(a)<<' '<<getlast(b)<<endl;
// }
while(q--){
char c ; cin>>c ;
if(c=='F'){
ll c , h ; cin>>c>>h ;
ll l = getfirst(h) ;
if(l==n+1) continue ;
c = min(c , n - l+1) ;
ll r = min(n , l+c-1) ;
if(r==n){
st.upd(l , r , 1) ;
continue ;
}
ll x = st.get(r , r) ;
ll lr = getlast(x-1) ;
ll rr = getlast(x) ;
ll lefties = max(0LL , lr - l+1) ;
ll 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{
ll a , b ; cin>>a>>b ;
cout<<getlast(b) - getfirst(a)+1<<endl;
}
// for(ll i = 1 ; i<=n ; i++){
// cout<<st.get(i , i)<<' ';
// }
// cout<<endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
605 ms |
15952 KB |
Output is correct |
| 2 |
Correct |
632 ms |
15304 KB |
Output is correct |
| 3 |
Correct |
452 ms |
14456 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
596 KB |
Output is correct |
| 2 |
Correct |
7 ms |
596 KB |
Output is correct |
| 3 |
Correct |
6 ms |
596 KB |
Output is correct |
| 4 |
Correct |
4 ms |
724 KB |
Output is correct |
| 5 |
Correct |
175 ms |
1380 KB |
Output is correct |
| 6 |
Correct |
217 ms |
1536 KB |
Output is correct |
| 7 |
Correct |
17 ms |
1208 KB |
Output is correct |
| 8 |
Correct |
175 ms |
1376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
196 ms |
1828 KB |
Output is correct |
| 2 |
Correct |
224 ms |
1904 KB |
Output is correct |
| 3 |
Correct |
5 ms |
1492 KB |
Output is correct |
| 4 |
Correct |
182 ms |
1740 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
220 ms |
2144 KB |
Output is correct |
| 2 |
Correct |
251 ms |
1824 KB |
Output is correct |
| 3 |
Correct |
27 ms |
1492 KB |
Output is correct |
| 4 |
Correct |
212 ms |
1880 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
391 ms |
11724 KB |
Output is correct |
| 2 |
Correct |
583 ms |
12776 KB |
Output is correct |
| 3 |
Correct |
66 ms |
3404 KB |
Output is correct |
| 4 |
Correct |
376 ms |
12612 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
548 ms |
13304 KB |
Output is correct |
| 2 |
Correct |
592 ms |
13952 KB |
Output is correct |
| 3 |
Correct |
447 ms |
12372 KB |
Output is correct |
| 4 |
Correct |
68 ms |
3392 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
630 ms |
14356 KB |
Output is correct |
| 2 |
Correct |
615 ms |
15592 KB |
Output is correct |
| 3 |
Correct |
447 ms |
14104 KB |
Output is correct |
| 4 |
Correct |
64 ms |
3428 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
638 ms |
15264 KB |
Output is correct |
| 2 |
Correct |
617 ms |
13600 KB |
Output is correct |
| 3 |
Correct |
116 ms |
17532 KB |
Output is correct |
| 4 |
Correct |
972 ms |
15980 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
596 ms |
15288 KB |
Output is correct |
| 2 |
Correct |
620 ms |
15580 KB |
Output is correct |
| 3 |
Correct |
790 ms |
17364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
562 ms |
17740 KB |
Output is correct |
