考察に結構手間取ったうえ、TLEを繰り返した。
http://codeforces.com/contest/601/problem/B
問題
数列H[1..n]に対し、リプシッツ定数L(H)は以下のように定義される。
- 1要素ならL(H)=0
- 2要素以上ならL(H)= max(ceil*1 (i>j)
ここでN要素の数列A[i]が与えられる。
また、この数列に対しQ個のクエリが与えられる。
各クエリは区間[L[j],R[j]]からなる。A[L[j]..R[j]]の全連続部分列に対し、リプシッツ定数の和を求めよ。
解法
L(H)の計算式に登場するi,jは、結局j=i+1しかありえない。
ceil内の値は結局数列内の2要素に関する傾きの絶対値を表すものなので、|H[i+1]-H[i]|が最大となるiが結局最大となる。
よってL(H) = max(|H[i+1]-H[i]|)となる。
A[x..y]の全連続部分列に対する、リプシッツ定数の和を考える。
A[x..y]において、L(A[x..y])=|A[i+1]-A[i]|、すなわち隣接2要素の差の絶対値が最大となる要素をi番とする。
A[x..y]の連続部分列のうち、A[i..(i+1)]を含む(i-x+1)*(y-i)通りはリプシッツ定数の値が|A[i+1]-A[i]|なる。
あとは同様にA[i..(i+1)]を含まない部分列、すなわちA[x..i]及びA[(i+1)..y]の連続部分列ごとに傾きが最大となる要素を求めていけば良い。
上記考え方を整理する。
まずクエリの事は忘れて、A[0..(N-1)]全体に対し、全連続部分列に対するリプシッツ定数の和を求めてみよう。
まず|A[i+1]-A[i]|を降順ソートし、対応するiごとに順に処理していく。
初期状態はA[0..(N-1)]を対象とし、上記のとおりA[i..(i+1)]を含む部分列A[x..y]に対して、上記(i-x+1)*(y-i)*|A[i+1]-A[i]|を答えに加算し、残った部分列をA[x..i]、A[(i+1)..y]に分解していく。
上記では初期状態をA[0..(N-1)]とし、iごとにそれを含むA[x..y]を求めていった。
クエリ毎の処理においては初期状態がA[L[i]..R[i]]なので、上記各部分列を分解していく過程で、A[L[i]..R[i]]にも含まれる部分だけを対象とすればよい。
A[i..(i+1)]を含む部分列を求める処理は、クエリ毎に毎回二分探索したりするとTLEするので1回だけ探索するようにしよう。
int N,Q; int A[101010]; pair<int,int> P[101010]; int L[101],R[101]; ll ret[101]; set<int> S; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>Q; FOR(i,N) cin>>A[i]; FOR(i,N-1) P[i]={abs(A[i+1]-A[i]),i}; sort(P,P+(N-1)); reverse(P,P+(N-1)); FOR(i,Q) { cin>>L[i]>>R[i]; L[i]--,R[i]--; } S.insert(-1); S.insert(N-1); FOR(i,N-1) { x=P[i].second; auto it=S.lower_bound(x); int RR=*it; it--; int LL=1+(*it); FOR(j,Q) { ll NR=min(RR,R[j]); ll NL=max(LL,L[j]); if(NL<=x && x+1<=NR) { ll num=(x-NL+1)*(NR-x); ret[j]+=num*P[i].first; } } S.insert(x); } FOR(j,Q) cout<<ret[j]<<endl; }
まとめ
考察ができればコードはそこまで難しくない。
*1:|H[j]-H[i]|)/(j-i