普段の2000ptよりは簡単かも。
http://codeforces.com/contest/1037/problem/F
問題
N要素の整数列Aと、パラメータKが与えられる。
整数列に対し以下を繰り返し行う。
- 長さがK以上であれば、長さKの連続部分列を総当たりし、その順で連続部分列の最大値を並べた数列に置き換える。
処理を行うたびに生成される数列の値の総和を求めよ。
解法
処理を行うたびに数列の値がどうなるかを考えよう。
B(n,m) := Aにm回処理を行ったものの第n要素(0-origin) とする。
するとB(n,m) = max(A[n..(n+m*(K-1))]) となる。
ここで、B(n,m) = max(B(n+(K-1),m-1),max(A[n...(n+K-1)]) となる。また、B(n,*)は単調増加となる。
よって、B(n+(K-1),*)がわかっている場合、max(A[n...(n+K-1)])>B(n+(K-1),m)となる範囲でB(n+(K-1),m)を置き換えれば、そのままB(n,m)の列が求められる。
よって、nをmod (K-1)の値で分類し、それぞれB(n+(K-1),*)からB(n,*)およびその総和を求めるということを順次行っていけばよい。
B(n+(K-1),*)は同じ値を複数持つので、map等で持っておけばmax(A[n...(n+K-1)])>B(n+(K-1),m)の場合の値の置き換え回数も均しでO(N)回に押さえられる。
template<class V,int NV> class SegTree_1 { public: vector<V> val; static V const def=0; V comp(V l,V r){ return max(l,r);}; SegTree_1(){val=vector<V>(NV*2,def);}; V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y if(r<=x || y<=l) return def; if(x<=l && r<=y) return val[k]; return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1)); } void update(int entry, V v) { entry += NV; val[entry]=comp(v,val[entry]); while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]); } }; SegTree_1<ll,1<<21> st; int N,K; int A[1010101]; vector<int> C[1010101]; ll mo=1000000007; void solve() { int i,j,k,l,r,x,y; string s; scanf("%d%d",&N,&K); FOR(i,N) { scanf("%d",&A[i]); st.update(i,A[i]); if(i+K<=N) C[i%(K-1)].push_back(i); } ll ret=0; FOR(i,K) { reverse(ALL(C[i])); map<ll,ll> M; ll tot=0; FORR(c,C[i]) { ll ma=st.getval(c,c+K); (tot+=ma)%=mo; M[ma]++; while(M.begin()->first<ma) { (tot+=(ma-M.begin()->first)*M.begin()->second)%=mo; M[ma]+=M.begin()->second; M.erase(M.begin()); } (ret+=tot)%=mo; } } cout<<ret<<endl; }
まとめ
A[i]が何回答えに加算されるか、を考える解法もあるようだ。