結果
問題 | No.878 Range High-Element Query |
ユーザー | beet |
提出日時 | 2019-08-06 19:39:04 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 136 ms / 2,000 ms |
コード長 | 5,799 bytes |
コンパイル時間 | 2,695 ms |
コンパイル使用メモリ | 208,364 KB |
実行使用メモリ | 6,604 KB |
最終ジャッジ日時 | 2023-08-26 00:23:26 |
合計ジャッジ時間 | 6,244 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,376 KB |
testcase_01 | AC | 2 ms
4,376 KB |
testcase_02 | AC | 2 ms
4,380 KB |
testcase_03 | AC | 1 ms
4,380 KB |
testcase_04 | AC | 2 ms
4,376 KB |
testcase_05 | AC | 2 ms
4,380 KB |
testcase_06 | AC | 2 ms
4,380 KB |
testcase_07 | AC | 1 ms
4,376 KB |
testcase_08 | AC | 2 ms
4,380 KB |
testcase_09 | AC | 2 ms
4,376 KB |
testcase_10 | AC | 2 ms
4,380 KB |
testcase_11 | AC | 128 ms
6,088 KB |
testcase_12 | AC | 85 ms
6,136 KB |
testcase_13 | AC | 96 ms
5,144 KB |
testcase_14 | AC | 75 ms
4,892 KB |
testcase_15 | AC | 87 ms
6,096 KB |
testcase_16 | AC | 123 ms
6,372 KB |
testcase_17 | AC | 136 ms
6,496 KB |
testcase_18 | AC | 132 ms
6,604 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; using Int = long long; template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;} struct FastIO{ FastIO(){ cin.tie(0); ios::sync_with_stdio(0); } }fastio_beet; template <typename T> struct SegmentTree{ using F = function<T(T,T)>; int n; F f; T ti; vector<T> dat; SegmentTree(){}; SegmentTree(F f,T ti):f(f),ti(ti){} void init(int n_){ n=1; while(n<n_) n<<=1; dat.assign(n<<1,ti); } void build(const vector<T> &v){ int n_=v.size(); init(n_); for(int i=0;i<n_;i++) dat[n+i]=v[i]; for(int i=n-1;i;i--) dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]); } void set_val(int k,T x){ dat[k+=n]=x; while(k>>=1) dat[k]=f(dat[(k<<1)|0],dat[(k<<1)|1]); } T query(int a,int b){ T vl=ti,vr=ti; for(int l=a+n,r=b+n;l<r;l>>=1,r>>=1) { if(l&1) vl=f(vl,dat[l++]); if(r&1) vr=f(dat[--r],vr); } return f(vl,vr); } }; struct FullyIndexableDictionary{ int len,blk; vector<unsigned> bit; vector<int> sum; FullyIndexableDictionary(){} FullyIndexableDictionary(int len) :len(len),blk((len+31)>>5),bit(blk,0),sum(blk,0){} void set(int k){ bit[k>>5]|=1u<<(k&31); } void build(){ sum[0]=0; for(int i=1;i<blk;i++) sum[i]=sum[i-1]+__builtin_popcount(bit[i-1]); } bool operator[](int k) const{ return bool((bit[k>>5]>>(k&31))&1); } int rank(int k){ return sum[k>>5]+__builtin_popcount(bit[k>>5]&((1u<<(k&31))-1)); } int rank(bool v,int k){ return (v?rank(k):k-rank(k)); } int select(bool v,int k){ if(k<0||rank(v,len)<=k) return -1; int l=0,r=len; while(l+1<r){ int m=(l+r)>>1; if(rank(v,m)>=k+1) r=m; else l=m; } return r-1; } int select(bool v,int i,int l){ return select(v,i+rank(v,l)); } }; template<class T,int MAXLOG> struct WaveletMatrix{ int len; FullyIndexableDictionary mat[MAXLOG]; int zs[MAXLOG],buff1[MAXLOG],buff2[MAXLOG]; static const T npos=-1; int freq_dfs(int d,int l,int r,T val,T a,T b){ if(l==r) return 0; if(d==MAXLOG) return (a<=val&&val<b)?r-l:0; T nv=T(1)<<(MAXLOG-d-1)|val; T nnv=((T(1)<<(MAXLOG-d-1))-1)|nv; if(nnv<a||b<=val) return 0; if(a<=val&&nnv<b) return r-l; int lc=mat[d].rank(1,l),rc=mat[d].rank(1,r); return freq_dfs(d+1,l-lc,r-rc,val,a,b) +freq_dfs(d+1,lc+zs[d],rc+zs[d],nv,a,b); } WaveletMatrix(vector<T> data){ len=data.size(); vector<T> l(len),r(len); for(int dep=0;dep<MAXLOG;dep++){ mat[dep]=FullyIndexableDictionary(len+1); int p=0,q=0; for(int i=0;i<len;i++){ bool k=(data[i]>>(MAXLOG-(dep+1)))&1; if(k) r[q++]=data[i],mat[dep].set(i); else l[p++]=data[i]; } zs[dep]=p; mat[dep].build(); swap(l,data); for(int i=0;i<q;i++) data[p+i]=r[i]; } } T access(int k){ T res=0; for(int dep=0;dep<MAXLOG;dep++){ bool bit=mat[dep][k]; res=(res<<1)|bit; k=mat[dep].rank(bit,k)+zs[dep]*dep; } return res; } // return the number of v in [0,k) int rank(T v,int k){ int l=0,r=k; for(int dep=0;dep<MAXLOG;dep++){ buff1[dep]=l;buff2[dep]=r; bool bit=(v>>(MAXLOG-(dep+1)))&1; l=mat[dep].rank(bit,l)+zs[dep]*bit; r=mat[dep].rank(bit,r)+zs[dep]*bit; } return r-l; } // return the position of k-th v int select(T v,int k){ rank(v,len); for(int dep=MAXLOG-1;dep>=0;dep--){ bool bit=(v>>(MAXLOG-(dep+1)))&1; k=mat[dep].select(bit,k,buff1[dep]); if(k>=buff2[dep]||k<0) return -1; k-=buff1[dep]; } return k; } int select(T v,int k,int l){ return select(v,k+rank(v,l)); } // return k-th largest value in [l,r) T quantile(int l,int r,int k){ if(r-l<=k||k<0) return -1; T res=0; for(int dep=0;dep<MAXLOG;dep++){ int p=mat[dep].rank(1,l); int q=mat[dep].rank(1,r); if(q-p>k){ l=p+zs[dep]; r=q+zs[dep]; res|=T(1)<<(MAXLOG-(dep+1)); }else{ k-=(q-p); l-=p; r-=q; } } return res; } T rquantile(int l,int r,int k){ return quantile(l,r,r-l-k-1); } // return number of points in [left, right) * [lower, upper) int rangefreq(int left,int right,T lower,T upper){ return freq_dfs(0,left,right,0,lower,upper); } pair<int, int> ll(int l,int r,T v){ int res=0; for(int dep=0;dep<MAXLOG;dep++){ buff1[dep]=l;buff2[dep]=r; bool bit=(v>>(MAXLOG-(dep+1)))&1; if(bit) res+=r-l+mat[dep].rank(bit,l)-mat[dep].rank(bit,r); l=mat[dep].rank(bit,l)+zs[dep]*bit; r=mat[dep].rank(bit,r)+zs[dep]*bit; } return make_pair(res,r-l); } int lt(int l,int r,T v){ auto p=ll(l,r,v); return p.first; } int le(int l,int r,T v){ auto p=ll(l,r,v); return p.first+p.second; } T succ(int l,int r,T v){ int k=le(l,r,v); return k==r-l?npos:rquantile(l,r,k); } T pred(int l,int r,T v){ int k=lt(l,r,v); return k?rquantile(l,r,k-1):npos; } }; //INSERT ABOVE HERE signed main(){ int n,q; cin>>n>>q; vector<int> as(n); for(int i=0;i<n;i++) cin>>as[i],as[i]--; auto f=[](int a,int b){return max(a,b);}; SegmentTree<int> seg(f,-1); seg.build(vector<int>(n,-1)); vector<int> bs(n); for(int i=0;i<n;i++){ bs[i]=seg.query(as[i],n); if(bs[i]<0) bs[i]=n; seg.set_val(as[i],i); } WaveletMatrix<int, 20> wm(bs); for(int i=0;i<q;i++){ int t; cin>>t; assert(t==1); { int l,r; cin>>l>>r; l--; int num=r-l; num-=wm.rangefreq(l,r,l,r); cout<<num<<"\n"; } } cout<<flush; return 0; }