結果
問題 | No.924 紲星 |
ユーザー |
![]() |
提出日時 | 2019-11-08 22:28:48 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,684 ms / 4,000 ms |
コード長 | 5,381 bytes |
コンパイル時間 | 1,603 ms |
コンパイル使用メモリ | 124,160 KB |
実行使用メモリ | 109,264 KB |
最終ジャッジ日時 | 2024-09-15 01:40:55 |
合計ジャッジ時間 | 15,847 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 16 |
ソースコード
#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <unordered_set> #include <random> #include <cassert> #include <fstream> #include <utility> #include <functional> #include <time.h> #include <stack> #include <array> #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair<ll, ll> P; int sz, n; vector<ll> seg[1<<19]; vector<ll> sum[1<<19]; vector<ll> a; void build(){ sz=1; while(sz<n) sz<<=1; for(int i=0; i<n; i++){ seg[i+sz].push_back(a[i]); sum[i+sz].push_back(0); sum[i+sz].push_back(a[i]); } for(int i=sz-1; i>=1; i--){ for(auto x:seg[2*i]) seg[i].push_back(x); for(auto x:seg[2*i+1]) seg[i].push_back(x); sort(seg[i].begin(), seg[i].end()); sum[i].resize(seg[i].size()+1); for(int j=0; j<seg[i].size(); j++) sum[i][j+1]=sum[i][j]+seg[i][j]; } } ll query(int a, int b, ll x){ a+=sz, b+=sz; ll ret=0; for(; a<b; a>>=1, b>>=1){ if(b&1){ b--; if(!seg[b].empty()){ int k=lower_bound(seg[b].begin(), seg[b].end(), x)-seg[b].begin(); int k2=upper_bound(seg[b].begin(), seg[b].end(), x)-seg[b].begin(); ret+=x*k-sum[b][k]; ret+=sum[b].back()-sum[b][k2]-x*(seg[b].size()-k2); } } if(a&1){ if(!seg[a].empty()){ int k=lower_bound(seg[a].begin(), seg[a].end(), x)-seg[a].begin(); int k2=upper_bound(seg[a].begin(), seg[a].end(), x)-seg[a].begin(); ret+=x*k-sum[a][k]; ret+=sum[a].back()-sum[a][k2]-x*(seg[a].size()-k2); } a++; } } return ret; } struct FullyIndexableDictionary{ int len, blk; vector<unsigned> bit; vector<int> sum; FullyIndexableDictionary(){} FullyIndexableDictionary(int len):len(len), blk((len+31)>>5), bit(blk), sum(blk){} void set(int k){ bit[k>>5]|=1u<<(k&31); } void build(){ for(int i=1; i<blk; i++){ sum[i]=sum[i-1]+__builtin_popcount(bit[i-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)); } }; template<typename T, int MAXLOG> struct WaveletMatrix{ int len; FullyIndexableDictionary mat[MAXLOG]; int zs[MAXLOG]; WaveletMatrix(vector<T> data){ len=data.size(); vector<T> ls(len), rs(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){ rs[q++]=data[i]; mat[dep].set(i); }else{ ls[p++]=data[i]; } } zs[dep]=p; mat[dep].build(); swap(ls, data); for(int i=0; i<q; i++) data[i+p]=rs[i]; } } int rank(T v, int l, int r){ for(int dep=0; dep<MAXLOG; dep++){ 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; } int rank(T v, int k){ return rank(v, 0, k); } T rangemin(int l, int r){ T ret=0; for(int dep=0; dep<MAXLOG; dep++){ int cntr=mat[dep].rank(0, r), cntl=mat[dep].rank(0, l); if(cntl==cntr){ l=l-cntl+zs[dep]; r=r-cntr+zs[dep]; ret=((ret<<1)|1); }else{ l=cntl; r=cntr; ret<<=1; } } return ret; } T rangemax(int l, int r){ T ret=0; for(int dep=0; dep<MAXLOG; dep++){ int cntr=mat[dep].rank(r), cntl=mat[dep].rank(l); if(cntl==cntr){ l=l-cntl; r=r-cntr; ret<<=1; }else{ l=cntl+zs[dep]; r=cntr+zs[dep]; ret=((ret<<1)|1); } } return ret; } T quantile(int l, int r, int k){ // return k-th largest value in [l,r) T ret=0; for(int dep=0; dep<MAXLOG; dep++){ int cntr=mat[dep].rank(r), cntl=mat[dep].rank(l); if(cntr-cntl>=k){ l=cntl+zs[dep]; r=cntr+zs[dep]; ret=((ret<<1)|1); }else{ l=l-cntl; r=r-cntr; ret<<=1; k-=(cntr-cntl); } } return ret; } int freq_dfs(int dep, int l, int r, T val, T a, T b){ if(l==r) return 0; if(dep==MAXLOG) return ((a<=val && val<b) ? r-l : 0); T mid=(T(1)<<(MAXLOG-dep-1)|val); T right=(((T(1)<<(MAXLOG-dep-1))-1)|mid); if(right<a || b<=val) return 0; if(a<=val && mid<b) return r-l; int cntl=mat[dep].rank(l), cntr=mat[dep].rank(r); return freq_dfs(dep+1, l-cntl, r-cntr, val, a, b)+freq_dfs(dep+1, cntl+zs[dep], cntr+zs[dep], mid, a, b); } int rangefreq(int l, int r, T d, T u){ return freq_dfs(0, l, r, 0, d, u); } void list_dfs(int dep, int l, int r, T val, T a, T b, vector<pair<T, int>> &vs){ if(l==r || b<=val) return; if(dep==MAXLOG){ if(a<=val && val<b) vs.push_back({val, r-l}); return; } T mid=(T(1)<<(MAXLOG-dep-1)|val); T right=(((T(1)<<(MAXLOG-dep-1))-1)|mid); if(right<a) return; int cntl=mat[dep].rank(l), cntr=mat[dep].rank(r); list_dfs(dep+1, l-cntl, r-cntr, val, a, b, vs); list_dfs(dep+1, cntl+zs[dep], cntr+zs[dep], mid, a, b, vs); } vector<pair<T, int>> freqlist(int l, int r, T d, T u){ vector<pair<T, int>> ret; list_dfs(0, l, r, 0, d, u, ret); return ret; } }; int main() { int q; cin>>n>>q; a.resize(n); const ll MAX=1e9; for(int i=0; i<n; i++){ cin>>a[i]; a[i]+=MAX; } WaveletMatrix<ll, 31> wm(a); build(); for(int i=0; i<q; i++){ int l, r; cin>>l>>r; l--; ll med=wm.quantile(l, r, (r-l)/2+1); printf("%lld\n", query(l, r, med)); } return 0; }