この問題は平方分割により解くことができます。

問題の読み替え

\(A'_i=\sum_{i=l}^{l+K-1}A_i\)
\(C'_i=\sum_{i=l}^{l+K-1}C_i\)

と定めます。これは適当な実装により \(O(N)\) で求めることができます。この \(A',C'\) を用いることで、問題は次のように読み替えられます。

2 種類のクエリを処理せよ

• 更新クエリ：\(L,R,x\) が与えられる。\(A'_L,A'_{L+1},\ldots,A'_R\) に \(x\) を加える

• 質問クエリ：\(X\) が与えられる。\(C'_i\geq X\) を満たす \(i\) についての、\(A'_i\) の最小値を求めよ。

平方分割によるデータの持ち方

読み替えた問題を平方分割を用いて解きます。分割によって生まれる \(\Theta(\sqrt{N})\) 個の要素からなる区間をバケットと呼ぶことにします。バケットでは次の要素を持ちます。

• 更新クエリによりバケット全体の \(A'_i\) に加算されている値 lazy
• 各 \(k\) について「\(C'_i\geq k\) であるような \(i\) についての \(A'_i\) の最小値」 Amin[k]

注意として、バケットが持つ要素の個数は \(O(\sqrt{N})\) であることから、\(C'_i\) の種類数も \(O(\sqrt{N})\) であり、「\(C'_i\geq k\) であるような \(i\) についての \(A'_i\) の最小値」が意味のある情報を持つ \(k\) も \(O(\sqrt{N})\) 種類です。さらに、\(C_i\) は \(0\) か \(1\) であることから、それらは連続した値になります。よって、\(C'_i\) ことに \(A'_i\) の 最小値を求めたあと、累積 min を取ることで、\(O(\sqrt{N})\) で初期化を行うことができます。

質問クエリの処理

全てのバケットについての Amin[X] + lazy の最小値が答えです。各バケットのこの値は \(O(1)\) で取得できるので、 \(O(\sqrt{N})\) でこのクエリを処理することができます。

更新クエリの処理

更新範囲にバケット全体が含まれる場合は lazy の値のみを書き換えます。 \(O(\sqrt{N})\) 個のバケットを \(O(1)\) で更新するので全体で \(O(\sqrt{N})\) です。

そうでない場合は、 \(A'_i\) および Amin[k] を再計算します。高々 2 個のバケットを \(O(\sqrt{N})\) で更新するので全体で \(O(\sqrt{N})\) です。（lazy は作用させてしまっても、そのまま残しても構いません）

よってこのクエリを \(O(\sqrt{N})\) で処理することができました。

まとめ

以上より、質問クエリ・更新クエリをともに \(O(\sqrt{N})\) で処理することができるため、この問題を \(O(Q\sqrt{N})\) で解くことができました。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;
#define rep(i,l,r)for(int i=(l);i<(r);i++)
using ll = long long;
void chmin(ll&x,ll y){x = min(x,y);}
const ll INF = 1e18;
const int B = 300;

struct block{
  ll lazy;
  int cc_min;
  vector<ll> Amin;  // Amin[x]=min{asum[i] | csum[i]>=x+cc_min}
};

int main(){
  int n, k, q;
  cin >> n >> k >> q;
  vector<int> a(n), c(n);
  rep(i,0,n) cin >> a[i];
  rep(i,0,n) cin >> c[i];
  
  // sum(a[i:i+k]), sum(c[i:i+k]) の計算
  int N = n - (k - 1);
  vector<ll> asum(N);
  vector<int> csum(N);
  ll aa = 0;
  int cc = 0;
  rep(i,0,k-1){
    aa += a[i];
    cc += c[i];
  }
  rep(i,k-1,n){
    aa += a[i];
    asum[i-(k-1)] = aa;
    aa -= a[i-(k-1)];
    cc += c[i];
    csum[i-(k-1)] = cc;
    cc -= c[i-(k-1)];
  }

  int n_blocks = (N + B - 1) / B;
  vector<block> blocks(n_blocks);
  
  auto build_block = [&](int ii){
    int L = ii * B;
    int R = min(L + B, N);
    auto min_max_it = minmax_element(csum.begin() + L, csum.begin() + R);
    if(blocks[ii].Amin.size() == 0){
      // 初回
      blocks[ii].cc_min = *min_max_it.first;
      int cc_max = *min_max_it.second;
      blocks[ii].Amin = vector<ll>(cc_max - blocks[ii].cc_min + 1, INF);
    }else{
      // 2回目以降
      blocks[ii].Amin = vector<ll>(blocks[ii].Amin.size(), INF);
    }
    rep(i,L,R){
      int idx = csum[i] - blocks[ii].cc_min;
      chmin(blocks[ii].Amin[idx], asum[i]);
    }
    for(int i=blocks[ii].Amin.size()-1; i>0; i--){
      chmin(blocks[ii].Amin[i-1], blocks[ii].Amin[i]);
    }
  };
  
  
  auto update=[&](int l, int r, int v){
    // 更新クエリ
    if(l % B != 0){
      // 左の端数
      int L = l;
      int R = min(L / B * B + B, r);
      rep(i,L,R){
        asum[i] += v;
      }
      build_block(l / B);
      l = R;
    }
    if(l < r && r % B != 0){
      // 右の端数
      int L = r / B * B;
      int R = r;
      rep(i,L,R){
        asum[i] += v;
      }
      build_block(r / B);
      r = L;
    }
    if(l < r){
      // 真ん中
      int LL = l / B;
      int RR = r / B;
      rep(ii,LL,RR){
        blocks[ii].lazy += v;
      }
    }
  };
  
  auto query = [&](int x){
    // 質問クエリ
    ll ans = INF;
    for(auto&block: blocks){
      int p = max(0, x - block.cc_min);
      if(p < block.Amin.size()){
        chmin(ans, block.Amin[p] + block.lazy);
      }
    }
    return ans;
  };
  
  rep(ii,0,blocks.size()){
    build_block(ii);
  }

  rep(_,0,q){
    int t, x, y;
    cin >> t >> x >> y;
    if(t == 1){
      x--;
      int l = max(0, x - (k - 1));
      int r = min(N, x + k - (k - 1));
      update(l, r, y - a[x]);
      a[x] = y;
    }else{
      ll ans = query(x);
      if(ans == INF){
        cout << "IMPOSSIBLE" << endl;
      }else{
        cout << ans << endl;
      }
    }
  }
}

実装例 (Python)

INF = 10**18
B = 300

class Block:
  def __init__(self):
    self.lazy = 0
    self.cc_min = -1
    self.Amin = []  # Amin[x]=min{asum[i] | csum[i]>=x+cc_min}

n, k, q = map(int, input().split())
a = list(map(int, input().split()))
c = list(map(int, input().split()))
N = n - (k - 1)

# sum(a[i:i+k]), sum(c[i:i+k]) の計算
asum = [0] * N
csum = [0] * N
aa = sum(a[:k-1])
cc = sum(c[:k-1])
for i in range(k - 1, n):
  aa += a[i]
  asum[i-(k-1)] = aa
  aa -= a[i-(k-1)]
  cc += c[i]
  csum[i-(k-1)] = cc
  cc -= c[i-(k-1)]

n_blocks = (N + B - 1) // B
blocks = [Block() for _ in range(n_blocks)]

def build_block(ii):
  L = ii * B
  R = min(L + B, N)
  if len(blocks[ii].Amin) == 0:
    # 初回
    blocks[ii].cc_min = min(csum[L:R])
    cc_max = max(csum[L:R])
    blocks[ii].Amin = [INF] * (cc_max - blocks[ii].cc_min + 1)
  else:
    # 2回目以降
    cc_min = blocks[ii].cc_min
    blocks[ii].Amin = [INF] * len(blocks[ii].Amin)

  for i in range(L, R):
    idx = csum[i] - blocks[ii].cc_min
    if blocks[ii].Amin[idx] > asum[i]:
      blocks[ii].Amin[idx] = asum[i]

  for i in range(len(blocks[ii].Amin) - 1, 0, -1):
    if blocks[ii].Amin[i - 1] > blocks[ii].Amin[i]:
      blocks[ii].Amin[i - 1] = blocks[ii].Amin[i]

def update(l, r, v):
  # 更新クエリ
  if l % B:
    # 左の端数
    L = l
    R = min(l // B * B + B, r)
    for i in range(L, R):
      asum[i] += v
    build_block(l // B)
    l = R
  if l < r and r % B:
    # 右の端数
    L = r // B * B
    R = r
    for i in range(L, R):
      asum[i] += v
    build_block(r // B)
    r = L
  if l < r:
    # 真ん中
    LL = l // B
    RR = r // B
    for ii in range(LL, RR):
      blocks[ii].lazy += v

def query(x):
  # 質問クエリ
  ans = INF
  for block in blocks:
    p = max(0, x - block.cc_min)
    if p >= len(block.Amin):
      continue
    ans = min(ans, block.Amin[p] + block.lazy)
  return ans

for ii in range(n_blocks):
  build_block(ii)

for _ in range(q):
  t, x, y = map(int, input().split())
  if t == 1:
    x -= 1
    l = max(0, x - (k - 1))
    r = min(N, x + k - (k - 1))
    update(l, r, y - a[x])
    a[x] = y
  else:
    ans = query(x)
    if ans == INF:
      print("IMPOSSIBLE")
    else:
      print(ans)