ferinの競プロ帳

競プロについてのメモ

JAG夏合宿2018 day2 J - AB Sort

競技プログラミング AtCoder

問題ページ

解法

解説にある通りAを+1, Bを-1に置き換えて累積和を取って標高図を書いてみる。操作を終えたあとの最終的な文字列はA…AB…Bとなる。標高図のminが最終的な標高図のminになるまでとそこから標高図のmaxが最終的な標高図のmaxになるまでの2つに分けて考える。1つ目の段階では標高図のmin、2つ目の段階では標高図のmaxが1stepにつき1ずつ上昇していく。2段階目に移ったときに標高図のmaxは最終的なmin+1になる。答えは (1段階目) + (2段階目) = (最終的なmin)-(標高図のmin) + (最終的なmax)-(最終的なmin+1) = (最終的なmax)-(標高図のmin)-1 となる。最終的なmaxはその文字列のAの数となる。もしAが存在しなければ-1がmaxになるが問題の条件からAは必ず1つは存在するため場合分けは必要ない。

つまり各クエリについて文字列のAの個数と標高図のminを求めることができれば答えが求められる。これは遅延セグメントツリーを用いることで実現できる。セグメントツリーの各頂点にはその区間のmin、max、sum、Aの数(cnt)、文字の数(sz)を乗せる。lazyにはその区間が反転する区間かどうかを0/1で持っておく。セグ木のマージをする関数fと遅延評価する関数gと遅延伝播する関数hを以下のように定義する。fで頂点lとrのマージを行うとするとret.min=min(l.min, l.sum+r.min), ret.max=max(l.max, l.sum+r.max), ret.sum=l.sum+r.sum, ret.cnt=l.cnt+r.cnt, ret.sz=l.cnt+r.cntとなる。gで頂点lの反転を行うときはl.min=-l.max, l.max=-l.min, l.sum=-l.sum, l.cnt=l.sz-l.cntとなる。hで頂点lに頂点rの情報を伝播するときはlrとなる。swap操作なのでl=r=1で2回swapするのであればswapしないのと同義である。これらの関数を定義したセグメントツリーを用いることで各クエリに対してO(logn)で必要な情報を求めることができる。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using PII = pair<int, int>;
template <typename T> using V = vector<T>;
template <typename T> using VV = vector<V<T>>;
template <typename T> using VVV = vector<VV<T>>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll INF = (1LL<<60);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

/**
* @brief セグメント木
* @details 抽象化した遅延セグメント木\n
* 区間更新区間max d1=d0=INT_MAX f=max(a,b) g=h=(b==INT_MAX?a:b)\n
* 区間加算区間和  d1=d0=0 f=g=h=a+b p=a*b\n
* 区間加算区間min d1=d0=0 f=min(a,b) g=h=a+b\n
* 区間更新区間和  d1=d0=0 f=a+b g=h=(b==0?a:b) p=a*b\n
* 区間xor区間和   d1=d0=0 f=a+b g=(b>=1?b-a:a) h=a^b p=a*b
*/
template <typename T, typename E>
struct lazySegTree {
  using F = function<T(T,T)>;
  using G = function<T(T,E)>;
  using H = function<E(E,E)>;
  using P = function<E(E,int)>;
  F f; G g; H h; P p; T d1; E d0;
  int n;
  vector<T> dat;
  vector<E> lazy;

  lazySegTree(){}
  lazySegTree(int n_, F f_, G g_, H h_, 
    T d1_, E d0_, P p_=[](E a, int b){return a;})
    : f(f_), g(g_), h(h_), p(p_), d1(d1_), d0(d0_) 
  {
    n = 1; while(n < n_) n *= 2;
    dat.assign(n*2-1, d1);
    lazy.assign(n*2-1, d0);
  }
  void build(vector<T> v) {
    REP(i, v.size()) dat[i+n-1] = v[i];
    for(int i=n-2; i>=0; --i) dat[i] = f(dat[i*2+1], dat[i*2+2]);
  }

  // 区間の幅がlenの節点kについて遅延評価
  inline void eval(int len, int k) {
    if(lazy[k] == d0) return;
    if(k*2+1 < n*2-1) {
      lazy[2*k+1] = h(lazy[k*2+1], lazy[k]);
      lazy[2*k+2] = h(lazy[k*2+2], lazy[k]);
    }
    dat[k] = g(dat[k],p(lazy[k],len));
    lazy[k] = d0;
  }
  // [a, b)
  T update(int a, int b, E x, int k, int l, int r) {
    eval(r-l, k);
    if(b <= l || r <= a) return dat[k];
    if(a <= l && r <= b) {
      lazy[k] = h(lazy[k], x);
      return g(dat[k], p(lazy[k],r-l));
    }
    return dat[k] = f(update(a, b, x, 2*k+1, l, (l+r)/2),
                      update(a, b, x, 2*k+2, (l+r)/2, r));
  }
  T update(int a, int b, E x) { return update(a, b, x, 0, 0, n); }
  // [a, b)
  T query(int a, int b, int k, int l, int r) {
    eval(r-l, k);
    if(a <= l && r <= b) return dat[k];
    bool left = !((l+r)/2 <= a || b <= l), right = !(r <= 1 || b <= (l+r)/2);
    if(left&&right) return f(query(a, b, 2*k+1, l, (l+r)/2), query(a, b, 2*k+2, (l+r)/2, r));
    if(left) return query(a, b, 2*k+1, l, (l+r)/2);
    return query(a, b, 2*k+2, (l+r)/2, r);
  }
  T query(int a, int b) { return query(a, b, 0, 0, n); }
  // デバッグ出力
  void debug() {
    cout << "---------------------" << endl;
    int cnt = 0;
    for(int i=1; i<=n; i*=2) {
      REP(j, i) {
        cout << "((" << dat[cnt].min << "," << dat[cnt].max << "," << dat[cnt].sum << ","
              << dat[cnt].cnt << ")," << lazy[cnt] << ") "; 
        cnt++;
      }
      cout << endl;
    }
    cout << "---------------------" << endl;
  }
};

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n;
  string s;
  cin >> n >> s;
  s = 'B' + s + 'A';
  n += 2;

  // セグ木の定義
  struct node {
    int min, max, sum, cnt, sz;
    node() {}
    node(int a, int b, int c, int d, int e) : min(a),max(b),sum(c),cnt(d),sz(e) {}
  };

  auto f = [&](node a, node b) {
    node ret;
    ret.min = min(a.min, a.sum+b.min);
    ret.max = max(a.max, a.sum+b.max);
    ret.sum = a.sum + b.sum;
    ret.cnt = a.cnt + b.cnt;
    ret.sz = a.sz + b.sz;
    return ret;
  };
  auto g = [&](node a, int b) {
    if(b == 0) return a;
    a.min *= -1;
    a.max *= -1;
    swap(a.min, a.max);
    a.sum *= -1;
    a.cnt = a.sz - a.cnt;
    return a; 
  };
  auto h = [&](int a, int b) {
    return a ^ b;
  };
  lazySegTree<node, int> seg(n, f, g, h, node(0, 0, 0, 0, 0), 0);

  // セグ木の初期化
  vector<node> v(n);
  REP(i, n) {
    if(s[i] == 'A') {
      v[i].min = 1;
      v[i].max = 1;
      v[i].sum = 1;
      v[i].cnt = 1;
    } else {
      v[i].min = -1;
      v[i].max = -1;
      v[i].sum = -1;
      v[i].cnt = 0;
    }
    v[i].sz = 1;
  }
  seg.build(v);

  int q;
  cin >> q;
  REP(i, q) {
    int l, r;
    cin >> l >> r;
    // 先頭に付け加えるBの分indexは+1される
    l++, r++;
    
    seg.update(l, r+1, 1);
    node ret = seg.query(0, n);
    cout << ret.cnt - ret.min - 1 << endl;
  }

  return 0;
}