Language: C++

#include <bits/stdc++.h>
using namespace std;

#define int long long
template <typename T>
struct SegmentTree{
  using F = function<T(T,T)>;
  int n;  //セグ木の幅
  F f;  //モノイドの作用
  T ti;  //初期値
  vector<T> dat;  //セグ木で使う配列 一番上に使われるのがdat[1] 一番下の段の左端がdat[n]
  SegmentTree(){};
  SegmentTree(F f,T ti):f(f),ti(ti){}  //fがモノイドとしての作用、tiが単位元
  SegmentTree(F f,T ti,int n_):f(f),ti(ti){
    n=1;
    while(n<n_) n<<=1;
    dat.assign(n<<1,ti);
  }
  SegmentTree(F f,T ti,const vector<T> &v):f(f),ti(ti){
    int n_=v.size();
    n=1;
    while(n<n_) n<<=1;
    dat.assign(n<<1,ti);
    for(int i=0;i<n_;i++)dat[n+i]=v[i];
    for(int i=n-1;i;i--)
      dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]);
  }

  T get(int x){
    return dat[x+n];
  }

  void init(int n_){  //ただの初期化
    n=1;
    while(n<n_) n<<=1;  //nが実際にとる２べきの幅
    dat.assign(n<<1,ti);  //dat配列は幅の２倍あってその全てにtiを代入
  }

  void build(const vector<T> &v){  //vector vに合わせた初期化
    int n_=v.size();
    init(n_);
    for(int i=0;i<n_;i++) dat[n+i]=v[i];  //v[i]を一番子の所に代入
    for(int i=n-1;i;i--)
      dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]);  //iの子供は2*i、2*i+1
  }

  void set_val(int k,T x){  //（0-indexedで）kにxを代入
    dat[k+=n]=x;
    while(k>>=1)  //kがどんどん自分の親になっていく、0になったらおしまい
      dat[k]=f(dat[(k<<1)|0],dat[(k<<1)|1]);
  }

  T query(int a,int b){  //[a,b)の範囲のモノイドの作用を返す
    T vl=ti,vr=ti;
    for(int l=a+n,r=b+n;l<r;l>>=1,r>>=1) {
      if(l&1) vl=f(vl,dat[l++]);  //左端を使いたくなるのはブロックが奇数の時
      if(r&1) vr=f(dat[--r],vr);  //右端〃偶数の時（開区間なのでr:奇数で反応）
    }
    return f(vl,vr);
  }

  template<typename C>
  int find(int st,C &check,T &acc,int k,int l,int r){  //dat[k]:[l,r)の間にいるenを返す
    //下のfind用なので先にそっち読むべき
    //accはst~lとかで確定している値
    if(l+1==r){  //答えがちゃんと存在するならこのlが答え
      acc=f(acc,dat[k]);
      return check(acc)?k-n:-1; //入るならk-n(==l)を、入らないなら-1を返す
    }
    int m=(l+r)>>1;  //にぶたんのそれ
    if(m<=st) return find(st,check,acc,(k<<1)|1,m,r);  //mがstより後ろなら明らかにl=m;
    if(st<=l&&!check(f(acc,dat[k]))){  //今見てるk全部でもダメ(mだと足りないのでl=mにする）
      acc=f(acc,dat[k]);  //kは全部accに加えた上で-1を返す
      return -1;
    }
    int vl=find(st,check,acc,(k<<1)|0,l,m);  //まず[l,m)の中にenがいるか探す
    if(~vl) return vl;  //いたならそれを返す(if(~vl)は-1以外にのみ反応する)
    return find(st,check,acc,(k<<1)|1,m,r);  //いなかったら[m,r)の中にenがいるのでそれを返す
    //acc=f(acc,dat[k]);がここで効いてる
  }

  template<typename C>
  int find(int st,C &check){
    //check(f(dat[st]~dat[en-1]))=false,check(f(dat[st]~dat[en]))＝trueとなるenを返す
    T acc=ti;
    return find(st,check,acc,1,0,n);
  }
};
/*
a.右から間が奇数かつ奇数の場所のを見つけたら取る
b.間が奇数かつ偶数の場所もメモはしておく
c.取ったらメモを右から攻める
d.全部とったら一番左の偶数を取る
e.右から奇数を取る
f.偶数を取る
g.残りを計算

スコアの算出方法は？
奇数を取るたびに1上がるはず
左右にある奇数の1と偶数の1の個数を覚えておく

総合でいくつかを覚える
自分より右に1がそれぞれ何個ずつあるかを持っておいて、自分より左で何回消えたかを覚えておくことで、変化量が分かって総合を変えられる
*/
int memoO[223456],memoE[223456];
int U[223456];

signed main(){
  string s;cin>>s;
  int n=s.size();
  int OD=0,EV=0;
  for(int i=0;i<n;i++)if(s[i]=='1')(i&1?EV:OD)++;
  SegmentTree<int> seg(f,0,n);

  queue<int> que;

  int cnt=0;
  int ROD=0,REV=0;
  for(int i=n-1;i>=0;i--){
    if(s[i]=='1'){
      cnt++;
      (i&1?REV:ROD)++;
    }
    else{
      if(cnt&1){
        if(i&1){
          ans+=OD;
          OD+=REV-ROD;
          EV+=EOD-REV;
          seg.set_val(i,1);
          U[i]=1;
          cnt=0;
          while(que.size()){
            P p=que.front();que.pop();
            int idx=p.idx,rod=p.ROD,rev=p.rev;
            ans+=OD;
            OD+=rod-rev;
            EV+=rev-rod;
            seg.set_val(idx,1);
            U[idx]=1;
          }
        }
        else{
          que.push({i,ROD,REV});
          U[i]=1;
        }
      }
    }
  }
  ROD=REV=cnt=0;
  for(int i=n-1;i>=0;i--){
    if(s[i]=='1'){
      int A=seg.query(0,i);
      if((A+i)&1)REV++;
      else ROD++;
      cnt++;
    }
    if(s[i]=='0'&&!U[i]){
      ans+=OD;
      OD+=REV-ROD;
    }
  }
  ans+=(cnt/2)*((cnt/2)+1);
  if(cnt&1)ans+=cnt/2+1;
  cout<<ans<<endl;
}


Compiler output:
a.cc: In function 'int main()':
a.cc:113:24: error: 'f' was not declared in this scope
  113 |   SegmentTree<int> seg(f,0,n);
      |                        ^
a.cc:127:11: error: 'ans' was not declared in this scope; did you mean 'abs'?
  127 |           ans+=OD;
      |           ^~~
      |           abs
a.cc:129:15: error: 'EOD' was not declared in this scope; did you mean 'ROD'?
  129 |           EV+=EOD-REV;
      |               ^~~
      |               ROD
a.cc:134:13: error: 'P' was not declared in this scope
  134 |             P p=que.front();que.pop();
      |             ^
a.cc:135:21: error: 'p' was not declared in this scope
  135 |             int idx=p.idx,rod=p.ROD,rev=p.rev;
      |                     ^
a.cc:137:17: error: 'rod' was not declared in this scope
  137 |             OD+=rod-rev;
      |                 ^~~
a.cc:137:21: error: 'rev' was not declared in this scope
  137 |             OD+=rod-rev;
      |                     ^~~
a.cc:144:19: error: no matching function for call to 'std::queue<long long int>::push(<brace-enclosed initializer list>)'
  144 |           que.push({i,ROD,REV});
      |           ~~~~~~~~^~~~~~~~~~~~~
In file included from /usr/include/c++/14/queue:66,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:157,
                 from a.cc:1:
/usr/include/c++/14/bits/stl_queue.h:283:7: note: candidate: 'void std::queue<_Tp, _Sequence>::push(const value_type&) [with _Tp = long long int; _Sequence = std::deque<long long int, std::allocator<long long int> >; value_type = long long int]'
  283 |       push(const value_type& __x)
      |       ^~~~
/usr/include/c++/14/bits/stl_queue.h:283:30: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const std::queue<long long int>::value_type&' {aka 'const long long int&'}
  283 |       push(const value_type& __x)
      |            ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/14/bits/stl_queue.h:288:7: note: candidate: 'void std::queue<_Tp, _Sequence>::push(value_type&&) [with _Tp = long long int; _Sequence = std::deque<long long int, std::allocator<long long int> >; value_type = long long int]'
  288 |       push(value_type&& __x)
      |       ^~~~
/usr/include/c++/14/bits/stl_queue.h:288:25: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::queue<long long int>::value_type&&' {aka 'long long int&&'}
  288 |       push(value_type&& __x)
      |            ~~~~~~~~~~~~~^~~
a.cc:159:7: error: 'ans' was not declared in this scope; did you mean 'abs'?
  159 |       ans+=OD;
      |       ^~~
      |       abs
a.cc:163:3: error: 'ans' was not declared in this scope; did you mean 'abs'?
  163 |   ans+=(cnt/2)*((cnt/2)+1);
      |   ^~~
      |   abs