#define PROBLEM "https://yukicoder.me/problems/1732" #include using namespace std; #define call_from_test #ifndef call_from_test #include using namespace std; #endif //BEGIN CUT HERE struct FastIO{ FastIO(){ cin.tie(0); ios::sync_with_stdio(0); } }fastio_beet; //END CUT HERE #ifndef call_from_test signed main(){ return 0; } #endif #ifndef call_from_test #include using namespace std; #endif //BEGIN CUT HERE template V compress(V v){ sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end()); return v; } template map dict(const vector &v){ map res; for(int i=0;i<(int)v.size();i++) res[v[i]]=i; return res; } map dict(const string &v){ return dict(vector(v.begin(),v.end())); } //END CUT HERE #ifndef call_from_test //INSERT ABOVE HERE signed main(){ return 0; } #endif #ifndef call_from_test #include using namespace std; #endif //BEGIN CUT HERE template inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template inline void chmax(T1 &a,T2 b){if(a using namespace std; #endif //BEGIN CUT HERE struct FullyIndexableDictionary{ int len,blk; vector bit; vector 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>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>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 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 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; } // 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;depk){ 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 ll(int l,int r,T v){ int res=0; for(int dep=0;dep>(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; } }; //END CUT HERE #ifndef call_from_test //INSERT ABOVE HERE // test rquantile signed SPOJ_MKTHNUM(){ int n,q; scanf("%d %d",&n,&q); vector vs(n); for(int i=0;i wm(vs); for(int i=0;i using namespace std; #endif //BEGIN CUT HERE template struct BIT{ int n; vector bit; //1-indexed BIT(int n_):n(n_+1),bit(n+1,0){} T sum(int i){ T s(0); for(int x=i;x>0;x-=(x&-x)) s+=bit[x]; return s; } void add(int i,T a){ if(i==0) return; for(int x=i;x<=n;x+=(x&-x)) bit[x]+=a; } int lower_bound(int w){ if(w<=0) return 0; int x=0,r=1; while(r0;k>>=1){ if(x+k<=n&&bit[x+k]>q; BIT bit(2e5); while(q--){ int t,x; cin>>t>>x; if(t==1) bit.add(x,1); if(t==2){ int k=bit.lower_bound(x); bit.add(k,-1); cout<>n>>k; vector as(n); for(int i=0;i>as[i]; auto vx=compress(as); auto mx=dict(vx); BIT bit1(n+10),bit2(n+10); ll ans=1e18,sum=0; for(int i=0;i wm(as); for(int i=0;i+k<=n;i++){ int j=i+k; int x=wm.quantile(i,j,k>>1); int p=bit1.sum0(mx[x]),q=k-p; int s=bit2.sum0(mx[x]); chmin(ans,p*x-s+(sum-s)-q*x); bit1.add0(mx[as[i]],-1); bit2.add0(mx[as[i]],-as[i]); sum-=as[i]; if(j==n) continue; bit1.add0(mx[as[j]],1); bit2.add0(mx[as[j]],as[j]); sum+=as[j]; } cout<