LibreOJ 6277. 数列ブロック入門1題解

タイトルリンク:https://loj.ac/problem/6277
タイトルの説明
長さ(n)の数列と、区間加算、単点検出値を含む(n)個の操作を与えます.
入力フォーマット
最初の行に数値(n)を入力します.2行目には(n)個の数字を入力し、(i)個目には(a_i)と入力し、スペースで区切ります.次に、(n)行問合せを入力し、行ごとに4つの数値(opt)、(l)、(r)、(c)を入力してスペースで区切ります.(opt=0)の場合、([l,r])の間にある数字に(c)が加算されます.(opt=1)の場合は、問い合わせ(a_r)の値((l)および(c)無視)を表します.
出力フォーマット
質問のたびに、1行1つの数字を出力して答えを表します.
サンプル入力

4
1 2 2 3
0 1 3 1
1 0 1 0
0 1 2 2
1 0 2 0

サンプル出力

2
5

データ範囲とヒント
(100%)のデータに対して、(1le nle 50000,−2^{31}le others,ansle 2^{31}−1)である.
問題を解く構想.
この問題に関連するアルゴリズム:数列ブロック.数列ブロックとは、長さが(n)の配列を、連続した長さが(lfloorsqrt{n}rfloor)の小さなブロックに分割することである((n)が(lfloorsqrt{n}rfloor)によって除去されない場合、最後のブロックの長さは(n)mod(lfloorsqrt{n}rfloor))である.次に(m=sqrt{n})を設定すると、配列内の(i)個目の要素(a_i)が属するブロックを(lfloorfrac{i-1}{m}rfloor+1)と定義することができる(すなわち、(a_1,a_2,cdots,a_m)個目のブロックに属し、(a_{m+1},a_{m+2},cdots,a_{2 m})個目のブロックに属し、...).入門の便宜上、配列(p[i])が(a_i)を表すグループ番号を定義します.

scanf("%d", &n);
m = sqrt(n);
for (int i = 1; i <= n; i ++) p[i] = (i-1)/m + 1;
for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);

実際、すべてのブロックは、1つの数列をいくつかのブロックに分割し、一括処理します.一般に,ブロックサイズを直接(sqrt{n})に設定するが,実際にはデータ範囲,具体的な複雑さに基づいてブロックサイズを決定する場合がある.
更新アクション
ここの更新操作を分析してみましょう.本題では、区間([l,r])の範囲内の各数に値(c)を追加する更新操作についてのみ説明します.これらの数は必ず連続するブロック(p[l],p[l]+1,cdots,p[r])内に属する.さらに、ブロックの数(gt 2)の場合、(p[l])と(p[r])の2つのブロックを除いて「一部の要素は更新する必要がある」場合があり、残りのすべてのブロック((p[l]+1,p[l]+2,cdots,p[r]-1))はブロック要素全体を(c)増加させることが分かった.
番号が(k)のブロックの場合、このブロックに属する要素の番号は(mtimes(k-1)+1)から(mtimes k)までわかります.我々の更新操作がブロック全体の要素を更新することに直面している場合、我々は以下の素朴な方法を採用することができる.

for (int i = m*(k-1)+1; i <= m*k; i ++)
    a[i] += c;

この方法の時間的複雑さは(O(m)=O(sqrt{n}))である.
しかし、実際には、ブロック全体の各要素に(c)を追加する必要はありません.彼らは(c)を追加しているので、私はいっそこのブロックに全体的な増分(c)をマークすればいいです.サイズ(sqrt{n})の配列(v)を開くことができ、ここで(v[i])は、(i)番目のブロックの全体的な更新量を表すために使用される.では、(k)と番号の付いたブロックを全体的に更新する必要がある場合は、次のコードを実行できます.

v[k] += c;

したがって、区間([l,r])全体に(c)を追加する操作を以下のように分割することができます.まず、(a[l])と(a[r])が同じブロックに属している場合(不完全なブロックは1つしかありません)、私はやはり素朴に(a[l])から(a[r])まで遍歴し、各要素に(c)を追加します.

if (p[l] == p[r]) { //         ，    
    for (int i = l; i <= r; i ++) a[i] += c;
    return;
}

そうでなければ、(a[l])から(a[r])まで少なくとも2つのブロックがあることを示す.私たちは問題を3つのステップに分割しました.

一番左のブロックを更新します.

一番右のブロックを更新します.

中間のブロックを更新します(もしあれば).

step.1一番左のブロックを更新
まず、一番左のブロック、すなわち(a[l])が属するブロックを分析します.

(l)mod(m e 1)、説明(a[l])が彼のいるブロックの最初の要素ではない場合、私はやはり(a[l])から前後にすべての和(a[l])が同じブロックに属する要素(すなわち、条件(ige l)を満たし、(p[i]=p[l])の(a[i])を追加する必要がある.

そうでなければ((l)mod(m=1))、説明(a[l])は彼のいるブロックの最初の要素であり、ブロック全体が更新されれば:(v[p[l]+=c)である.

if (l % m != 1) {    //   l    p[l]      
    for (int i = l; p[i]==p[l]; i ++)
        a[i] += c;
}
else v[p[l]] += c;

step.2一番右のブロックを更新
次に、右端のブロック、すなわち(a[r])が属するブロックを分析します.

(r)mod(m=0)、説明(a[r])が彼のいるブロックの最後の要素ではない場合、(a[r])からすべてと(a[r])が同じブロックに属する要素(すなわち、条件(ile r)を満たし、(p[i]=p[r])を後から更新する必要がある.

そうでなければ((r)mod(m=0))、説明(a[r])は彼のいるブロックの最後の要素であり、ブロック全体の更新だけでよい:(v[p[r]+=c).

if (r % m != 0) { //   r    p[r]       
    for (int i = r; p[i]==p[r]; i --)
        a[i] += c;
}
else v[p[r]] += c;

3.中間のブロックを更新(あれば)
最初の2つのステップでは、一番左のブロック((a[l])が属するブロック)と一番右のブロック((a[r])が属するブロック)を更新しました.残りは、中間のブロック(すなわち、番号が(p[l]+1、p[l]+2、cdots、p[r]-1)のブロック)です.これらのブロックはすべてブロック全体が更新され、これらのブロックに対して、更新量(c)を全体の更新量に直接加算すればよい.

for (int i = p[l]+1; i < p[r]; i ++)
    v[i] += c;

クエリー操作
(a[i])に対応する値を検索する場合は、次の2つの部分に対応する必要があります.

(a[i])自体の値.

(a[i])が属するブロック(p[i])の全体更新量(v[p[i])です.

したがって、(a[i])の実際の値は(a[i]+v[p[i])である.
これにより,数列ブロックに対応する更新とクエリの2つの操作を解析した.完全な実装コードは次のとおりです.

#include 
using namespace std;
const int maxn = 50050;
int n, m, a[maxn], p[maxn], v[300], op, l, r, c;
void add(int l, int r, int c) {
    if (p[l] == p[r]) { //         ，    
        for (int i = l; i <= r; i ++) a[i] += c;
        return;
    }
    if (l % m != 1) {    //   l    p[l]      
        for (int i = l; p[i]==p[l]; i ++)
            a[i] += c;
    }
    else v[p[l]] += c;
    if (r % m != 0) { //   r    p[r]       
        for (int i = r; p[i]==p[r]; i --)
            a[i] += c;
    }
    else v[p[r]] += c;
    for (int i = p[l]+1; i < p[r]; i ++)
        v[i] += c;
}
int main() {
    scanf("%d", &n);
    m = sqrt(n);
    for (int i = 1; i <= n; i ++) p[i] = (i-1)/m + 1;
    for (int i = 1; i <= n; i ++) scanf("%d", a+i);
    for (int i = 0; i < n; i ++) {
        scanf("%d%d%d%d", &op, &l, &r, &c);
        if (op == 0) add(l, r, c);
        else printf("%d
", a[r] + v[p[r]]);
    }
    return 0;
}

じかんふくごうどぶんせき
更新
一番左のブロックを更新:各ブロックの要素は(sqrt{n})を超えないため、操作回数は(sqrt{n})を超えない;
一番右のブロックを更新:各ブロックの要素は(sqrt{n})を超えないため、操作回数は(sqrt{n})を超えない;
中間のブロックを更新:ブロック数が(sqrt{n}+1)を超えないため、中間のブロックの数は(sqrt{n})を超えない.
したがって、更新の時間的複雑度は(O(sqrt{n})+O(sqrt{n})+O(sqrt{n})=O(sqrt{n}))である.
検索
クエリは直接(a[i]+v[p[i])を返すので,クエリの時間的複雑度は(O(1))である.
以上のように,合計(n)回の操作があるため,このアルゴリズムの時間的複雑度は(O(nsqrt{n}))である.
参照リンク:https://www.cnblogs.com/louhancheng/p/10051136.html