結果

問題 No.878 Range High-Element Query
ユーザー どらら
提出日時 2019-09-07 14:00:28
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 263 ms / 2,000 ms
コード長 2,459 bytes
コンパイル時間 1,843 ms
コンパイル使用メモリ 178,740 KB
実行使用メモリ 8,892 KB
最終ジャッジ日時 2024-06-26 09:39:57
合計ジャッジ時間 4,727 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

struct ST {
  ll x;
  ST():x(0){}
  ST(ll x):x(x){}
};
ST combine(const ST& lhs, const ST& rhs){
  ST st;
  st.x = lhs.x + rhs.x;
  return st;
}
template<class S>
class SegmentTree {
  int N;
  vector<S> t;
  void build(){
    for(int i=N-1; i>0; i--){
      t[i] = combine(t[i<<1], t[i<<1|1]);
    }
  }
public:
  SegmentTree(int n_){
    N = 1;
    while(N < n_) N *= 2;
    t.resize(2*N);
    for(int i=N; i<2*N; i++){
      t[i] = S();
    }
    build();
  }
  SegmentTree(const vector<S>& v){
    N = 1;
    while(N < v.size()) N *= 2;
    t.resize(2*N);
    for(int i=0; i<v.size(); i++){
      t[i+N] = v[i];
    }
    build();
  }
  void modify(int p, S val){
    for(t[p+=N] = val; p>>=1;){
      t[p] = combine(t[p<<1], t[p<<1|1]);
    }
  }
  S query(int l, int r){
    S resl, resr;
    for(l+=N, r+=N; l<r; l>>=1, r>>=1){
      if(l&1) resl = combine(resl, t[l++]);
      if(r&1) resr = combine(t[--r], resr);
    }
    return combine(resl, resr);
  }
};


void dfs(int l, int r, const vector<int>& v, vector<int>& w){
  int base = -1;
  int x = -1;
  REP(i,l,r){
    if(base <= v[i]){
      if(x != -1){
        dfs(x,i,v,w);
        x = -1;
      }
      w[i] = l;
      base = v[i];
    }else{
      if(x == -1) x = i;
    }
  }
  if(x != -1){
    dfs(x,r,v,w);
  }
}


struct X {
  int i, l, r;
};
bool operator<(const X& a, const X& b){
  return a.l < b.l;
}

int main(){
  int N, Q;
  cin >> N >> Q;
  vector<int> v;
  rep(i,N){
    int a;
    cin >> a;
    v.push_back(a);
  }

  vector<int> w(N,-1);
  dfs(0,N,v,w);
  vector<X> vw;
  rep(i,w.size()){
    vw.push_back((X){i,w[i],0});
  }
  sort(ALLOF(vw));
  
  vector<X> vx;
  rep(i,Q){
    int t, l, r;
    cin >> t >> l >> r;
    l--;
    r--;
    vx.push_back((X){i,l,r});
  }
  sort(ALLOF(vx));

  vector<int> ret(Q,-1);

  SegmentTree<ST> segtree(N);
  int ii = 0;
  rep(i,vx.size()){
    int l = vx[i].l;

    while(ii<vw.size()){
      if(vw[ii].l <= l){
        segtree.modify(vw[ii].i,(ST){1LL});
      }else{
        break;
      }
      ii++;
    }

    ret[vx[i].i] = segtree.query(l, vx[i].r+1).x;
  }

  rep(i,ret.size()){
    cout << ret[i] << endl;
  }
  
  return 0;
}
0