結果

問題 No.924 紲星
コンテスト
ユーザー tekihei2317
提出日時 2019-11-08 23:26:46
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,503 ms / 4,000 ms
コード長 4,106 bytes
コンパイル時間 2,666 ms
コンパイル使用メモリ 191,976 KB
実行使用メモリ 160,564 KB
最終ジャッジ日時 2024-09-15 02:31:45
合計ジャッジ時間 15,930 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
#define int long long
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

template<class T> struct wavelet_matrix {
  vector<int> dat;
  vector<vector<int>> cnt;
  vector<T> dic;
  
  wavelet_matrix(const vector<T> &a) : dat(a) {
    const int n = dat.size();
    dic.assign(a.begin(), a.end());
    sort(dic.begin(), dic.end());
    dic.erase(unique(dic.begin(), dic.end()), dic.end());
    for (int i = 0; i < n; i++) {
      dat[i] = lower_bound(dic.begin(), dic.end(), a[i]) - dic.begin();
    }
    int H = 1;
    while ((1 << H) < dic.size()) H++;
    cnt.resize(H, vector<int>(n + 1));
    auto dfs = [&](auto dfs, int l, int r, int h) -> void {
      if (r - l == 0) return;
      if (h == H) return;
      for (int i = l; i < r; i++) {
        cnt[h][i + 1] = cnt[h][i] + (~dat[i] >> (H - 1 - h) & 1);
      }
      int m = stable_partition(dat.begin() + l, dat.begin() + r, [&](T x) {
        return ~x >> (H - 1 - h) & 1;
      }) - dat.begin();
      dfs(dfs, l, m, h + 1);
      dfs(dfs, m, r, h + 1);
    };
    dfs(dfs, 0, n, 0);
  }
 
  T quantile(int l, int r, int k) {
    const int n = cnt[0].size() - 1;
    int a = 0;
    int b = n;
    for (int i = 0; i < cnt.size(); i++) {
      int cnt0 = cnt[i][b] - cnt[i][a];
      int c = cnt[i][r] - cnt[i][l];
      if (k < c) {
        l = a + cnt[i][l] - cnt[i][a];
        r = a + cnt[i][r] - cnt[i][a];
        b = a + cnt0;
      } else {
        l += cnt[i][b] - cnt[i][l];
        r += cnt[i][b] - cnt[i][r];
        k -= c;
        a += cnt0;
      }
    }
    return dic[dat[l]];
  }
};

vector<int> merge(vector<int> &a,vector<int> &b)
{
    int N=a.size(),M=b.size();
    int i=0,j=0;
    vector<int> res;
    while(i<N or j<M){
        if(i==N) res.push_back(b[j++]);
        else if(j==M) res.push_back(a[i++]);
        else{
            if(a[i]<=b[j]) res.push_back(a[i++]);
            else res.push_back(b[j++]);
        }
    }
    return res;
}

class SegmentTree
{
 private:
    int n;
    vector<vector<int>> data;
    vector<vector<int>> sum;
 public:
    SegmentTree(vector<int> a){
        n=1;
        while(n<a.size()) n*=2;
        data.resize(2*n-1);
        sum.resize(2*n-1);
        for(int i=0;i<n;i++){
            if(i<a.size()) data[i+n-1].push_back(a[i]);
            else data[i+n-1].push_back(0);
        }
        for(int i=n-2;i>=0;i--){
            data[i]=merge(data[2*i+1],data[2*i+2]);
        }
        build();
    }
    void build(){
        for(int i=0;i<2*n-1;i++){
            sum[i].resize(data[i].size()+1);
            for(int j=0;j<data[i].size();j++){
                sum[i][j+1]=sum[i][j]+data[i][j];
            }
        }
    }
    pair<int,int> get(int a,int b,int x,int k,int l,int r)
    {
        // cout<<k<<' '<<l<<' '<<r<<endl;
        pair<int,int> res={0,0};
        if(r<=a or b<=l) return res;
        if(a<=l and r<=b){
            int i=upper_bound(data[k].begin(),data[k].end(),x)-data[k].begin();
            res.first=sum[k][i]; res.second=i;
            return res;
        }else{
            pair<int,int> L=get(a,b,x,2*k+1,l,(l+r)/2);
            pair<int,int> R=get(a,b,x,2*k+2,(l+r)/2,r);
            L.first+=R.first; L.second+=R.second;
            return L;
        }
    }
    pair<int,int> get(int a,int b,int x){ return get(a,b,x,0,0,n); }
};

signed main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int N,Q; cin>>N>>Q;
    vector<int> a(N);
    for(int i=0;i<N;i++) cin>>a[i];
    wavelet_matrix<int> wm(a);
    SegmentTree seg(a);

    vector<int> sum(N+1);
    for(int i=0;i<N;i++) sum[i+1]=sum[i]+a[i];

    while(Q--){
        int l,r; cin>>l>>r;
        l--;
        int med=wm.quantile(l,r,(r-l)/2);

        pair<int,int> p=seg.get(l,r,med);
        int less=p.first,cnt=p.second;
        int more=(sum[r]-sum[l])-less;
        int ans=med*cnt-less+more-med*(r-l-cnt);
        // cout<<med<<' '<<less<<' '<<more<<endl;
        cout<<ans<<endl;
    }
    return 0;
}
0