保存されている過去のバージョンの一覧

2015年06月28日03時17分02秒

HDOJ 5273 - Dylans loves sequence

Source

BestCoder Round #45 2問目
HDOJ 5273

問題概要

$N$ 要素からなる整数列 $A_1,A_2,\ldots,A_N$ が与えられる．
$Q$ 個のクエリが与えられるので，そのクエリに答える問題．
各クエリでは $L,R$ が与えられるので，数列 $A_L, A_{L+1}, \ldots, A_R$ に対する転倒数を求める．
数列 $X_1,X_2,\ldots,X_k$ に対する転倒数とは，$1 \leq i < j \leq k$ かつ $X_i > X_j$ を満たすペア $(i,j)$ の個数である．

解法

各 $i$ に対して，数列 $A_{i+1}, \ldots, A_j$ の中で $A_i$より大きい物がいくつあるかを任意の $j$ に対して最初に求めておく．
この値を $S_{i,j}$ とすれば，$S_{i,j}$ は $S_{i,j-1}$ から簡単に計算できるので，全ての $S_{i,j}$ を $O(N^2)$ で求めることができる．
数列 $A_i, A_{i+1}, \ldots, A_j$ に対する転倒数を $T_{i,j}$ とすると，これは $A_{i+1}, A_{i+2}, \ldots, A_j$ に対する転倒数を用いて $T_{i,j} = S_{i,j} + T_{i+1,j}$ と計算できる．
よって，任意の $T_{i,j}$ が $O(N^2)$ で求まる．
時間計算量は $O(N^2 + Q)$．

C++によるスパゲッティなソースコード

#include<cstdio>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar()
#define mypc(c) putchar(c)

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
template <class T, class S> void reader(T *x, S *y){reader(x);reader(y);}

void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}

int N, Q;
int A[1010];

int dp[1010][1010];
int cnt[1010][1010];

int main(){
  int i, j, k;
  int L, R;

  reader(&N,&Q);
  rep(i,N) reader(A+i);

  rep(i,N){
    cnt[i][i] = 0;
    REP(j,i+1,N){
      cnt[i][j] = cnt[i][j-1];
      if(A[i] > A[j]) cnt[i][j]++;
    }
  }

  REP(k,1,N){
    rep(i,N-k){
      j = i+k;
      dp[i][j] = dp[i+1][j] + cnt[i][j];
    }
  }

  while(Q--){
    reader(&L,&R);
    writerLn(dp[L-1][R-1]);
  }

  return 0;
}

Current time: 2024年04月25日21時29分54秒
Last modified: 2015年06月28日03時17分02秒 (by laycrs)
Tags: Competitive_Programming Hangzhou_Dianzi_University_Online_Judge BestCoder_45 BestCoder_B
トップページに戻る

Logged in as: unknown user (not login)

ログイン：