yukicoder No.1270 - Range Arrange Query

Source

ニコニコミュニティ
問題文

問題概要

省略

解法

省略

cLay（version 20201018-2）のコード

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

int N, Q, A[2d4], L, R;
fenwick<int> f;
{
  rd(N,Q,(A--)(N));
  Arr1d<ll> x(N), y(N), h1(N), h2(N);
  f.malloc(N);

  f.init(N);
  rep(i,N) x[i] = f.range(A[i]+1, N-1), f.add(A[i], 1);
  f.init(N);
  rrep(i,N) y[i] = f.get(A[i]-1), f.add(A[i], 1);

  rep(Q){
    ll res = ll_inf;
    rd(L--, R--);
    rep(i,N) h1[i] = h2[i] = 0;
    h1.reset(); h2.reset();
    rep(i,L) h1[A[i]]++;
    rep(i,R+1,N) h2[A[i]]++;
    rep(i,N) res <?= (h1.getSum(i+1,N-1) + h2.getSum(0,i-1)) * (R - L + 1);
    rep(i,L) res += h2.getSum(0, A[i]-1);
    res += x.getSum(0,L-1) + y.getSum(R+1,N-1);
    wt(res);
  }
}

Current time: 2024年04月19日11時35分51秒
Last modified: 2020年10月24日18時43分06秒 (by laycrs)
Tags: Competitive_Programming_Incomplete yukicoder
トップページに戻る

Logged in as: unknown user (not login)

ログイン：