yukicoder No.1300 - Sum of Inversions

Source

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

問題概要

省略

解法

省略

cLay（version 20201206-1）のコード

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

#define MD 998244353
int N, A[2d5];
int val[2d5], ind[2d5];
fenwick<int> t1, t2;
fenwick<Modint> f1, f2;
{
  int i, j, k;
  ll tmp1, tmp2;
  Modint res = 0;
  rd(N,A(N));
  t1.walloc(N,1); t2.walloc(N,1); f1.walloc(N,1); f2.walloc(N,1);
  rep(i,N) (val[i], ind[i]) = (A[i], i);
  sortA(N, A, ind);

  rep(i,N) t1.add(i,1);
  rep(i,N) f1.add(ind[i],A[i]);
  i = 0;
  rep(k,N){
    j = i;
    while(i < N && A[i]==A[k]){
      t1.add(ind[i],-1);
      f1.add(ind[i],-A[i]);
      i++;
    }
    i = j;
    while(i < N && A[i]==A[k]){
      tmp1 = t1.get(ind[i]-1);
      tmp2 = t2.range(ind[i]+1,N-1);
      res += Modint(A[i]) * tmp1 * tmp2;
      res += f1.get(ind[i]-1) * tmp2;
      res += f2.range(ind[i]+1,N-1) * tmp1;
      i++;
    }
    i = j;
    while(i < N && A[i]==A[k]){
      t2.add(ind[i],1);
      f2.add(ind[i],A[i]);
      i++;
    }
  }
  wt(res);
}

Current time: 2024年04月19日00時34分35秒
Last modified: 2020年12月06日15時51分44秒 (by laycrs)
Tags: Competitive_Programming_Incomplete yukicoder
トップページに戻る

Logged in as: unknown user (not login)