#include <bits/stdc++.h>
using namespace std;
#define int long long
struct segtree{
int l, r, i; double m, b; int cnt;
segtree* lc = 0, *rc = 0;
segtree* getmem();
segtree(int l, int r) : l(l), r(r), m(0), b(1e9), cnt(0){
i = (l + r) / 2;
if(l==r) return;
lc = getmem(); *lc = segtree(l, i);
rc = getmem(); *rc = segtree(i+1, r);
};
segtree() : segtree(-1, -1){};
void u(double qm, double qb, int qcnt){
if(qm * i + qb < m*i+b){
swap(m, qm); swap(b, qb); swap(cnt, qcnt);
}
if(l == r) return;
if(qm > m) lc->u(qm, qb, qcnt);
else rc->u(qm, qb, qcnt);
}
pair<double, int> q(int qi){
pair<double, int> cur = {m*qi+b, cnt};
if(i == qi) return cur;
if(qi < i) return min(cur, lc->q(qi));
else return min(cur, rc->q(qi));
}
void reset(){
m = 0; b= 1e9; cnt = 0;
if(l==r) return;
lc->reset(); rc->reset();
}
} mem[(int)1e7]; int memsz = 0;
segtree* segtree::getmem(){return &mem[memsz++];}
signed main(){
int n, k; cin >> n >> k;
string s; cin >> s;
double l = 0, r = 1e12;
double res = 0, m = 0;
int cnt = 0;
vector<int> b;
for(int i = 0; i < 2*n; i++){
if(s[i] == 'B') b.push_back(i);
}
segtree ac(0, n);
while(r - l > 1e-6){
m = (l+r)/2;
ac->reset();
double sl = 0;
ac.u(0, 0, 0);
int cnta = 0;
double cur = 0;
int funnynumber = 0;
int cntactive = 0;
for(int i = 0; i < 2 * n; i++){
if(s[i] == 'A'){
if(cntactive>0) funnynumber -= cntactive;
cntactive++;
if(cntactive>0) funnynumber += b[cnta] - i - cntactive;
cnta++;
cur += sl;
auto tmp = ac.q(cnta);
tmp.first += m; tmp.second++;
if(cnta == n) {
res = tmp.first + cur;
cnt = tmp.second;
}
ac.u(-cnta, tmp.first + (cnta)*cnta+funnynumber, tmp.second);
}
else{
cntactive--;
sl++;
}
}
if(cnt <= k) r = m;
else l = m;
}
cout<<(int)round(res-m*k)<<endl;
}
Compilation message
chorus.cpp: In function 'int main()':
chorus.cpp:54:11: error: base operand of '->' has non-pointer type 'segtree'
54 | ac->reset();
| ^~
