#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair P; int sz, n; vector seg[1<<19]; vector sum[1<<19]; vector a; void build(){ sz=1; while(sz=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>=1, b>>=1){ if(b&1){ b--; if(!seg[b].empty()){ int k=upper_bound(seg[b].begin(), seg[b].end(), x)-seg[b].begin(); ret+=sum[b][k]; tot+=sum[b].back(); } } if(a&1){ if(!seg[a].empty()){ int k=upper_bound(seg[a].begin(), seg[a].end(), x)-seg[a].begin(); ret+=sum[a][k]; tot+=sum[a].back(); } a++; } } return P(tot, ret); } struct FullyIndexableDictionary{ int len, blk; vector bit; vector 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>5]+__builtin_popcount(bit[k>>5]&((1u<<(k&31))-1)); } int rank(bool v, int k){ return (v ? rank(k) : k-rank(k)); } }; template struct WaveletMatrix{ int len; FullyIndexableDictionary mat[MAXLOG]; int zs[MAXLOG]; WaveletMatrix(vector data){ len=data.size(); vector ls(len), rs(len); for(int dep=0; dep>(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>(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=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> &vs){ if(l==r || b<=val) return; if(dep==MAXLOG){ if(a<=val && val> freqlist(int l, int r, T d, T u){ vector> 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>a[i]; a[i]+=MAX; } WaveletMatrix wm(a); build(); for(int i=0; i>l>>r; l--; ll med=wm.quantile(l, r, (r-l)/2+1); P p=query(l, r, med); ll ans=p.first-2*p.second; if((r-l)%2) ans+=med; printf("%lld\n", ans); } return 0; }