yukicoder No.878 - Range High-Element Query

Source

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

問題概要

省略

解法

省略

cLay（version 20190921-1）のコード

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

int N, Q, A[1d5], T, L, R;
int go[17][1d5];

{
  int i, j, k;
  
  rd(N,Q,A(N));
  rep(j,17) go[j][N-1] = N;
  for(i=N-2;i>=0;i--){
    if(A[i] < A[i+1]){
      go[0][i] = i+1;
    } else {
      k = i+1;
      for(;;){
        if(go[0][k]==N) go[0][i] = N, break;
        if(A[go[0][k]] > A[i]) go[0][i] = go[0][k], break;
        rep(j,1,17) if(go[j][k]==N || A[go[j][k]] > A[i]) break;
        k = go[j-1][k];
      }
    }

    rep(j,1,17){
      if(go[j-1][i]==N) go[j][i] = N;
      else              go[j][i] = go[j-1][go[j-1][i]];
    }
  }

  rep(Q){
    rd(T,L--,R--);
    k = 0;
    for(;;){
      if(go[0][L] > R) k++, break;
      rep(j,16) if(go[j+1][L] > R) break;
      k += (1<<j);
      L = go[j][L];
    }
    wt(k);
  }
  
}

Current time: 2024年04月26日09時29分22秒
Last modified: 2019年09月21日11時57分01秒 (by laycrs)
Tags: Competitive_Programming_Incomplete yukicoder
トップページに戻る

Logged in as: unknown user (not login)