AtCoder Library Practice Contest L問題 - Lazy Segment Tree

Source

AtCoder Library Practice Contest
問題文

問題概要

省略

解法

省略

cLay（version 20201018-1）のコード

C++に変換後のコードはこちら

struct segval{
  int zero, one;
  ll inv;
};

segval segtree_rh_apply(int f, segval a){
  if(f){
    swap(a.zero, a.one);
    a.inv = (ll) a.one * a.zero - a.inv;
  }
  return a;
}

segval segtree_rh_merge(segval a, segval b){
  segval res;
  res.zero = a.zero + b.zero;
  res.one = a.one + b.one;
  res.inv = a.inv + b.inv + (ll) a.one * b.zero;
  return res;
}

int segtree_rh_compose(int f, int g){
  return f^g;
}

int N, Q, A[2d5], T, L, R;
segtree_rh<segval, int> t;
{
  segval v;

  rd(N,Q,A(N));
  t.malloc(N);
  t.setN(N, 0, 0);
  rep(i,N){
    t[i].zero = 1 - A[i];
    t[i].one = A[i];
    t[i].inv = 0;
  }
  t.build();
  rep(Q){
    rd(T, L--, R);
    if(T==1){
      t.change(L, R, 1);
    } else {
      wt(t.get(L, R).inv);
    }
  }
}

cLay（version 20200916-1）のコード

C++に変換後のコードはこちら

struct segval{
  int zero, one;
  ll inv;
};

struct segfun{
  int r;
};

void segtree_rg_id(segfun &res){
  res.r = 0;
}

void segtree_rg_func(segval &res, segfun f, segval a){
  if(f.r){
    res.zero = a.one;
    res.one = a.zero;
    res.inv = (ll) a.one * a.zero - a.inv;
  } else {
    res = a;
  }
}

void segtree_rg_func(segval &res, segval a, segval b){
  res.zero = a.zero + b.zero;
  res.one = a.one + b.one;
  res.inv = a.inv + b.inv + (ll) a.one * b.zero;
}

void segtree_rg_func(segfun &res, segfun f, segfun g){
  res.r = f.r ^ g.r;
}

int N, Q, A[2d5], T, L, R;
segtree_rg<segval, segfun> t;
{
  segval v;
  segfun f; f.r = 1;

  rd(N,Q,A(N));
  t.malloc(N);
  t.setN(N, 0, 0);
  rep(i,N){
    t[i].zero = 1 - A[i];
    t[i].one = A[i];
    t[i].inv = 0;
  }
  t.build();
  rep(Q){
    rd(T, L--, R);
    if(T==1){
      t.change(L, R, f);
    } else {
      v = t.get(L, R);
      wt(v.inv);
    }
  }
}

Current time: 2024年04月19日11時29分29秒
Last modified: 2020年10月18日05時46分08秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder
トップページに戻る

Logged in as: unknown user (not login)