#define PROBLEM "https://yukicoder.me/problems/3227" #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 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>n; vector as(n); for(int i=0;i>as[i]; const int OFS = 1e9; for(int &a:as) a+=OFS; WaveletMatrix wm(as); ll ans=0; for(ll k=1;k<=n;k++){ int p=(k-1)/2; vector ls,rs; for(int i=0;i+k<=n;i+=k) ls.emplace_back((wm.rquantile(i,i+k,p)-OFS)*k); for(int i=n;i-k>=0;i-=k) rs.emplace_back((wm.rquantile(i-k,i,p)-OFS)*k); int sz=ls.size(); vector dp(sz+1,0),pd(sz+1,0); for(int i=0,sum=0;i0;i--){ sum+=rs[sz-i]; chmax(pd[i-1],pd[i]); chmax(pd[i-1],sum); } for(int i=0;i<=sz;i++) chmax(ans,dp[i]+pd[i]); } cout<