Google Kick Start 2020 Round C - Candies
May 19, 2020
問題概要
サイズNの配列と、Q個のクエリが与えらえれる。
クエリの書式はoperation x yでoperation = 'Q'の場合はx~y区間において、以下を計算するa[x] * 1 - a[x+1] * 2 + a[x+2] * 3 ... a[y] * (y-x+1)
operation = 'U'の場合は、a[x]の値をyに更新する
全てのクエリの結果の和を出力せよという問題
考えたこと
一点更新かつ、区間に関する値の取得となればセグメント木を使うことになりそう
ただクエリがクセがありすぎる、、区間の開始地点から1...(y-x+1)が掛けられるので、クエリのたびに計算処理が走りそう..
でもそれだと絶対に間に合わないし..
わからない, 結局コンテスト中にACはできませんでした。
解説をみて
この動画をみて、理解しました。
このクエリは複雑なので、問題を整理してみます.1~7の範囲のクエリは以下です。
a[1]*1 - a[2]*2 + a[3]*3 - a[4]*4 + a[5]*5 - a[6]*6 * a[7]*7
これを整理すると
- 範囲にインデックス(
iとする)を割り振ったとして、i番目の値はiをかける i%2==0(つまりインデックスが偶数)は-1をかける
一緒に考えると大変なので独立にして考えてみます。
範囲にインデックス(iとする)を割り振ったとして、i番目の値はiをかける
-1をかけるのは無視して、「i番目の値はiをかけた」のを全て足した和を求めてみます
N=7の配列を考えてみます。
この時x=5 y=7のクエリをかんがえてみます。
つまりa[5] + 2*a[6] + 3*a[7]を求めたいです。
まず先頭から最後まで全ての和を計算しておきます。
これを①とします
次に、先頭からx-1までを全ての和を計算します
これを②とします。
そして①-②をしてみます
すると,5*a[5] + 6*a[6] + 7*a[7]が残ります。
これに対して、求めたい解であるa[5] + 2*a[6] + 3*a[7]を引いてみます
この式の値は4 * (a[5] + a[6] + a[7])となります。
これより求めたい解は
(5*a[5] + 6*a[6] + 7*a[7]) - 4 * (a[5] + a[6] + a[7]) であると言えます。
これらを一般化していくと, 以下2つのsegment treeがあるとして
i番目の値はa[i]にiをかけた値が入ってる(segAとする)i番目の値はa[i]が入ってる(segBとする)
このx~yに対するクエリの答えは
segA.query(1, y+1) - segA.query(1, x) - (x-1)*segB.qeury(x, y+1)
と言えます
i%2==0(つまりインデックスが偶数)は-1をかける
インデックスが偶数の時は-1をかけるのを考えます。
こちらの方は結構シンプルにできます。
「i番目の値はiをかける」というのを無視して、インデックスが偶数の時は-1をかけるのだけを考えてみます
こちらもN=7の配列を考えてみます。
この時x=5 y=7のクエリをかんがえてみます。
この答えはa[5] - a[6] + a[7]となります。
x=4 y=7のクエリをかんがえてみます。
この答えはa[4] - a[5] + a[6] - a[7]をなります。
x=3 y=7のクエリをかんがえてみます。
この答えはa[3] - a[4] + a[5] - a[6] + a[7]をなります。
ある1つの値（例えば、a[5])に注目すると、x(範囲の開始地点)が1変化するたびに正負が変わるのがわかります。
結局偶奇なので, 2パターンが交互にくるというわけです。
というわけで, 以下のようなsegment treeを考えます。
iが奇数の時は、i番目の値にはa[i]が入ってる。iが偶数の時は、i番目の値には-1*a[i]が入ってる
N = 7だとしたら以下のような感じですね
a[1] - a[2] + a[3] - a[4] + a[5] - a[6] + a[7]
x=5 y=7の範囲を得るためには、ここから1~4の値を引いてあげればいいですね
a[1] - a[2] + a[3] - a[4] + a[5] - a[6] + a[7]-a[1] - a[2] + a[3] - a[4]= a[5] - a[6] + a[7]
x=4 y=7の範囲を得るために、ここから1~3の値を引いてみます
a[1] - a[2] + a[3] - a[4] + a[5] - a[6] + a[7]-a[1] - a[2] + a[3]= -a[4] + a[5] - a[6] + a[7]
これは上で求めた答えと違いますね、ここでこの解に-1をかけてみます
-1*-a[4] + a[5] - a[6] + a[7]a[4] - a[5] + a[6] - a[7]
上で求めた解となりました。
これよりあらかじめ「iが奇数の時は、i番目の値にはa[i]が入ってる。 iが偶数の時は、i番目の値には-1*a[i]が入ってる」segment treeを用意しておき
xの値が奇数だったら、そのままseg.query(x, y)xの値が偶数だったら、seg.qeury(x, y) * (-1)
が答えとなります。
あとはこれらをまとめて実装してあげればおkです。
実装
segment treeはこちらをコピペさせてもらいました。
上のサンプルでは、区間の最小値を求めるのになってますが、今回は区間の和を求めたいのでコンストラクタに和を返す関数を渡しています。
SegmentTree< ll > segA(n, [](ll a, ll b) { return a+b; }, 0);
あとは、結構最大値がでかくなるため、intだと桁あふれします。long longを使いましょう
template< typename Monoid >
struct SegmentTree {
using F = function< Monoid(Monoid, Monoid) >;
int sz;
vector< Monoid > seg;
const F f;
const Monoid M1;
SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1) {
sz = 1;
while(sz < n) sz <<= 1;
seg.assign(2 * sz, M1);
}
void set(int k, const Monoid &x) {
seg[k + sz] = x;
}
void build() {
for(int k = sz - 1; k > 0; k--) {
seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
}
}
void update(int k, const Monoid &x) {
k += sz;
seg[k] = x;
while(k >>= 1) {
seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
}
}
Monoid query(int a, int b) {
Monoid L = M1, R = M1;
for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
if(a & 1) L = f(L, seg[a++]);
if(b & 1) R = f(seg[--b], R);
}
return f(L, R);
}
Monoid operator[](const int &k) const {
return seg[k + sz];
}
template< typename C >
int find_subtree(int a, const C &check, Monoid &M, bool type) {
while(a < sz) {
Monoid nxt = type ? f(seg[2 * a + type], M) : f(M, seg[2 * a + type]);
if(check(nxt)) a = 2 * a + type;
else M = nxt, a = 2 * a + 1 - type;
}
return a - sz;
}
template< typename C >
int find_first(int a, const C &check) {
Monoid L = M1;
if(a <= 0) {
if(check(f(L, seg[1]))) return find_subtree(1, check, L, false);
return -1;
}
int b = sz;
for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
if(a & 1) {
Monoid nxt = f(L, seg[a]);
if(check(nxt)) return find_subtree(a, check, L, false);
L = nxt;
++a;
}
}
return -1;
}
template< typename C >
int find_last(int b, const C &check) {
Monoid R = M1;
if(b >= sz) {
if(check(f(seg[1], R))) return find_subtree(1, check, R, true);
return -1;
}
int a = sz;
for(b += sz; a < b; a >>= 1, b >>= 1) {
if(b & 1) {
Monoid nxt = f(seg[--b], R);
if(check(nxt)) return find_subtree(b, check, R, true);
R = nxt;
}
}
return -1;
}
};
int main() {
int t; cin >> t;
vector<ll> ans(t,0);
rep(tcase, t) {
int n, q; cin >> n >> q;
ll tmpans = 0;
// i番目の値はa[i]が値が入ってるセグ木
SegmentTree< ll > segA(n, [](ll a, ll b) { return a+b; }, 0);
// i番目の値はa[i]にiをかけた値が入ってるセグ木
SegmentTree< ll > segB(n, [](ll a, ll b) { return a+b; }, 0);
rep(i, n) {
ll ai; cin >> ai;
// インデックスが偶数の時は-1をかける(0-indexなので、解説と偶奇逆になってるよ)
if(i%2 == 1) ai *= -1;
segA.update(i, ai);
segB.update(i, ai*(i+1));
}
rep(i, q) {
char ope; cin >> ope;
if(ope == 'U') {
// 更新処理
int x,y; cin >> x >> y;
x--;
// 更新時は両方のセグ木更新と、インデックスが偶数の場合は-1をかけるの忘れずに
if(x%2 == 1) y *= -1;
segA.update(x, y);
segB.update(x, y*(x+1));
} else {
// クエリ
int x,y; cin >> x >> y;
x--; y--;
ll start = segB.query(0, x);
ll all = segB.query(0, y+1);
ll minsum = x * segA.query(x, y+1);
// 解説で書いたやつ
ll ret = all - start - minsum;
// 開始地点が偶数なら、-1をかけたのが答え
if(x%2 == 1) ret *= -1;
// 全てのクエリの和を求めるので、加算していく
tmpans += ret;
}
}
ans[tcase] = tmpans;
}
rep(i, t) {
cout << "Case #" << i+1 << ": " << ans[i] << endl;
}
return 0;
}