#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
const int mxN=1e5+1;
ll bit[mxN+1], a[mxN+1];
int n, m;
void upd(int pos, ll val) {
for(; pos<=mxN; pos+=pos&-pos) {
bit[pos]+=val;
}
}
ll qry(int pos) {
ll res=0;
for(; pos; pos-=pos&-pos) {
res+=bit[pos];
}
return res;
}
int f(ll val) {
int l=1, r=n;
while(l<=r) {
int mid=(l+r)/2;
if(qry(mid)>=val) {
r=mid-1;
} else {
l=mid+1;
}
}
return l;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin>>n>>m;
for(int i=1; i<=n; i++) {
cin>>a[i];
}
sort(a+1, a+n+1);
for(int i=1; i<=n; i++) {
upd(i, a[i]);
upd(i+1, -a[i]);
}
for(int i=0; i<m; i++) {
char ty; cin>>ty;
if(ty=='F') {
int c, h; cin>>c>>h;
int left=f(h), right=left+c-1;
if(left==n+1) continue;
if(right>n) {
upd(left, 1);
upd(n+1, -1);
} else if(qry(right)!=qry(right+1)) {
upd(left, 1);
upd(right+1, -1);
} else {
ll val=qry(right);
int newl=f(val);
upd(left, 1);
upd(newl, -1);
int newr=f(val+1);//[newr-1-count+1 ,newr-1] count is equal to newl-left
upd(newr-(newl-left), 1);
upd(newr, -1);
}
} else {
ll x, y; cin>>x>>y;
int l=f(x), r=f(y+1);
if(l==n+1) {
cout<<0<<"\n";
} else {
r--;
cout<<r-l+1<<"\n";
}
}
}
return 0;
}
//rating below 2400 must be solved orzorzorz
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |