結果
問題 | No.878 Range High-Element Query |
ユーザー |
![]() |
提出日時 | 2019-09-06 22:56:28 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 389 ms / 2,000 ms |
コード長 | 1,535 bytes |
コンパイル時間 | 1,310 ms |
コンパイル使用メモリ | 81,800 KB |
最終ジャッジ日時 | 2025-01-07 16:56:08 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 18 |
ソースコード
#include <iostream> #include <algorithm> #include <vector> #include <utility> using namespace std; using ll = long long; ll n,t[200010],mx = 100000000000000; void built(){ for(int i = n-1;i>0;i--){ t[i] = t[i<<1] + t[i<<1|1]; } } void update(ll p,ll a){ for(t[p+=n] = a;p>1;p >>= 1){ t[p>>1] = t[p] + t[p^1]; } } ll query(int l, int r){ ll mn = 0; for(l += n, r += n; l<r; l >>= 1,r >>= 1){ if(l&1) mn += t[l++]; if(r&1) mn += t[--r]; } return mn; } ll s[200010]; void built2(){ for(int i = n-1;i>0;i--){ s[i] = max(s[i<<1],s[i<<1|1]); } } ll query2(int l, int r){ ll mn = -1; for(l += n, r += n; l<r; l >>= 1,r >>= 1){ if(l&1) mn = max(mn,s[l++]); if(r&1) mn = max(mn,s[--r]); } return mn; } int a[100010],le[100010],ans[100010]; pair<int,int> p[100010]; pair<pair<int,int>,int> qu[100010]; int main(){ int i,q; cin >> n >> q; for(i=0;i<n;i++){ cin >> a[i]; s[i + n] = a[i]; } built2(); for(i=0;i<n;i++){ int l = 0,r = i; if(query2(0,i)<a[i]){ le[i] = 0; continue; } while(r - l>1){ int mid = (l + r)/2; if(query2(mid,i)<a[i]) r = mid; else l = mid; } le[i] = r; } for(i=0;i<n;i++){ p[i] = {le[i],i}; } sort(p,p + n); for(i=0;i<q;i++){ int x,l,r; cin >> x >> l >> r; l--; qu[i] = {{l,r},i}; } sort(qu,qu + q); int j = 0; for(i=0;i<q;i++){ int l = qu[i].first.first,r = qu[i].first.second; while(j<n && p[j].first<=l){ update(p[j].second,1); j++; } ans[qu[i].second] = query(l,r); } for(i=0;i<q;i++){ cout << ans[i] << endl; } }