c_Comp-Prog CF-ECR69-D Yet Another Subarray Problem
セグ木で殴る
問題
長さ$ nの配列$ aが与えられるので、値が最大となる連続部分列を求める。
ただし、この値は連続部分列に含まれる要素の個数を$ xとしたとき、$ k \times \lceil\frac{x}{m}\rceilだけ減算が入った値になることを考慮せよ。
制約
$ 1 \le n \le 3 \cdot 10^5
$ 1 \le m \le 10
$ 1 \le k \le 10^9
$ -10^9 \le a_i \le 10^9
考察
連続部分列$ \displaystyle\sum_{i=l}^{r}a_iは、$ \displaystyle\sum_{i=1}^{n}a_i - \sum_{i=1}^{l-1}a_i - \sum_{i=r+1}^{n}a_iで求められる。
そのため、配列両側からの累積和を取ることで、任意の連続部分列の値を$ O(1)で求められることができる。 これは後で使用するので、$ B_i = \sum_{j=1}^{i-1}a_j , $ C_i = \sum_{j=i}^{n}a_j とおいておく。
ただし、このまま愚直に実装すると減算の処理も相まって$ O(n^2)となり、間に合わない。
ここで、$ mの最大値が10であることに注目すると、それぞれの剰余に対して配列を作ってもメモリ制約を満たしそうなことがわかる。
なので、配列$ Cを基準とした$ m個の底辺の長さが$ nのSegmentTree(Range Minimum Query)$ Zを作る。 $ i (1 \le i \le m)個目のSegmentTreeの底辺 $ z_j (1 \le j \le n) は
- $ j < iのとき
$ z_j = C_j
- $ i \le jのとき
$ z_j = C_j + k\lceil \frac{i-j}{m} \rceil
とする。
この問題においては、連続部分列を決めたときの減算する値は連続部分列の長さに依存する。
そのため、ここで代入しているのは$ nの長さの数列に入る減算の値から、$ iから$ j番目の連続部分列を選んだときの値を引いたものである。
よって、$ vから始まる連続部分列の最大値を求めるには、
$ u = (v \bmod m)+1として、
$ \mathrm{ans}_v = \displaystyle\sum_{i=1}^{n}a_i - B_v - Z_{u_{v\cdots n}} + k\lfloor \frac{v-1}{m} \rfloor
となり、これをすべての$ vに対して行う。
$ Z_{u_{v\cdots n}}を求めるのに$ O(\log{n})かかるため、計算量は$ O(n\log{n})。
実装
考察パートでは1-indexedでしたが、実装パートは0-indexedです。
code:solve.cpp
int main(){
long long n,k,m;cin>>n>>m>>k;
vector<long long> A(n),B(n+1),C(n+1);
long long sm = 0;
for(long long i = 0; n > i; i++){
}
for(int i = n-1; 0 <= i; i--){
}
auto Z = get_segment_trees(m,n+1,[](long long a,long long b){return min(a,b);},600000000000000LL);
for(long long i = 0; m > i; i++){
for(long long j = 0; n >= j; j++){
if(j > i){
Zi.update(j,Cj+((j-i-1+m)/m*k)); }else{
}
}
}
long long ans = 0;
for(int i = 0; B.size() > i; i++){
long long v = i%m;
long long offset = (i/m)*k;
ans = max(ans,sm-Bi-Zv.getf(i,n)+offset); }
cout << ans << endl;
}
振り返り
ちなみに掛けた時間のうち60%程度は複数本のセグ木の作り方、30%は数値のチューニングでした
vectorに乗せればいいのはわかったんだけど値渡しでセグ木を作ってるからなんかバグってた いいverify問題教えてください
Editorialみたらもちろん非想定でした、はい