線分ツリー-Lazy_Tag
51820 ワード
転載LINK：LAZY_TAG
まず具体的な問題を見てみましょうPKU 3468
http://poj.org/problem?id=3468
題意がはっきりしている1≤ N,Q ≤ 100000.
"C a b c"means adding c to each of Aa, Aa+1, ... , Ab. -10000 ≤ c ≤ 10000."Q a b"means querying the sum of Aa, Aa+1, ... , Ab.
素朴なやり方でO(NQ)の明らかなTLE
区間統計の問題なので線分ツリーで解決してみます
線分ツリーノードが何を記録するかを考慮します
左右の息子区間範囲は必須:ls[]rs[]l[]r[]
質問に答えるために、現在の区間の和を保存するためにS[]を記録します.
*ツリーを建てるのは難しくないので、s[]の値を息子から上げることに注意してください.
*C操作に遭遇した場合、aからbの間の区間で覆われているすべてのセグメントツリー区間を修正します.
+3行目で完全に上書きされているかどうかを判断すると、s[]値を直接変更します.
+5行目-7行目交差再帰修正があるかどうかを判断
+8行目で、完全に上書きされていない場合にのみ、息子から新しいs[]値が得られます.
*Q操作に遭遇した場合,aからbの区間内のすべてのサブ区間の和を再帰的にクエリして答えを得る.
-5行目調べた区間が完全に上書きされた場合、直接戻り値
-10-14行目交差に基づいて再帰クエリ
クエリ操作の複雑さがO(Log 2 N)を超えないことを証明できる[定数が2]未満 問題のニーズに対応
しかし,修正操作の最悪の複雑さはO(N)に達することができ,定数は素朴さよりも大きく最適化を考慮しなければならない.
2つの操作の差を2つの概略図で見ることができます
クエリ[2,10]
修正[2,10]
この問題を解決するために有名なLazy-Tag思想が生まれた.
毎回すべての区間を修正するのが遅すぎるので、怠けて先に帳簿を覚えてからやったほうがいいです.
怠け者-記帳=Lazy-Tag
どうやって記録しますか?もう1つのドメインv[]を追加する必要があります.このドメインはタグです.
現在のノードがルートであるサブツリーを記録するには、どのくらい加算するかを指定します.
私たちのプログラムはもうすぐ変更されます.
+現在の区間を完全に修正したい区間に上書きされるたびに、直接タグに付けて終了します.
+1つのノードにアクセスするたびに、現在のノードのタグを空にします.
-アクセスにはさまざまなアクションが含まれます 削除を挿入してもクエリーを挿入しても、ノードのみのs[]値を使用しても
-現在のノードをタグで更新するだけでなく、タグの下を左右のサブツリーに渡すことも含まれます.
*個別のプロセスcleanを使用して、タグをクリアする操作を行います.
注意が必要なのは、リーフノードが下にマークを付けなくてもRE
*修正後の修正プロセス
+最初の行をクリアする
+5行目修正タグを完全に上書きした場合は終了
+10～12行目の再帰的なサブツリーの変更
+13～14行目現在の区間のs[]値を更新 マークを空にする必要があります.
*変更後のクエリー
クリアマークも付けて
この再帰完了更新s[]値を加えることも避けられない
完全なコードは文章の最後にあります
もちろんLazy-Tagは非常に強力なデータ構造Splayに使用できます
この問題はまだLazy-Tagの一般的な法則を運用していない.
もう一つの質問を考えましたが、区間全体を1つ乗せれば?
次に、デュアルタグの問題について説明します.
あと1つの数でタグドメインを追加します
u[]でノードxがルートであるサブツリーを表すにはu[x]を付ける必要がある
ノードxがルートであるサブツリーをv[]で表すにはv[x]を乗じる必要がある
実際の演算では,乗算と加算の動作シーケンスが不確定であることが分かった.
操作シーケンス全体を2つのタグで要約するには
振り返ってみると、一つの問題は加算だけの場合、加算シーケンスがどんなものであっても
加算の交換法則と結合法則に基づいて,配列全体の和を保存すればよい.
でも乗せれば簡単には覚えられない
マークの操作規則を先に規定するのが良い方法です 先に乗ってから加える
任意のノードx v[x]およびu[x]に対して現在のs[x]がs[x]*v[x]+u[x]に更新される必要があることを示す
タグを変更するたびに
現在の区間に数cを乗じる必要がある場合は、v[x]とu[x]の両方にcを乗じる
(s[x]*v[x]+u[x])*c=s[x]*(v[x]*c)+(u[x]*c)
現在の区間に数cを加算する必要がある場合はu[x]+cのみでよい
(s[x]*v[x]+u[x])+c=s[x]*v[x]+(u[x]+c)
いずれかの操作に対してのみ
無条件に区間のマークを直接修正して効果を達成できることを保証します.
Lazy-Tagを便利に使えます
そうでなければ、今マークを渡すときは、まず息子のマークを空にすることを考えなければなりません.
cleanプロセスは再帰的プロセス効率になりまたO(N)に戻る
コードの必要は前の問題に修正して文章の最後に貼り付けます
コアのプロセスはcleanです
もう一つの問題を議論するのもダブルタグです
シーケンスのメンテナンス
サポート操作は1つの区間に1つの数を統一的に加算します.
1つの区間を統一して1つの数に変更する
区間とどのくらいですか
3つのドメインs[]{Sum}c[]{Cover}d[]{Delta}の追加メンテナンスが容易に考えられる
現在区間をそれぞれ表す和s現在区間をc現在区間に上書きするにはdを加算する必要がある
2つのタグドメインd[]とc[]の関係を同様に分析する
2つのタグドメインが存在する場合、それはまず上書きしますか、それとも先に上書きしますか.
以下のいくつかの性質を発見することができます
ある区間xに対してc[x]を上書きすると以前のc[x]とd[x]は自動的に消失する
ある区間にd[x]を加えた後、c[x]に値があればc[x]に直接加えることができる.
これにより,c[x]とd[x]の最大1つの値が存在することを保証できる. 上の問題はありません
したがって、c[]の優先度はd[]より高いと規定してもよい. c[x]に値がある場合はc[x]のみを実行し、そうでない場合はd[x]を実行する
私たちはまた一つの結論を得た. 相互干渉のタグに対して明確な優先度を定めて操作秩序を保証する
コアかcleanプロセスか
Lazy-Tagについての議論はここまでです
次のディスカッション 線分ツリーの拡張
Bob HANオリジナル転載は出典を明記してくださいhttp://www.cnblogs.com/Booble/
完全なコードを添付
Simple
SuperSImple
Paint
まず具体的な問題を見てみましょうPKU 3468
http://poj.org/problem?id=3468
題意がはっきりしている1≤ N,Q ≤ 100000.
"C a b c"means adding c to each of Aa, Aa+1, ... , Ab. -10000 ≤ c ≤ 10000."Q a b"means querying the sum of Aa, Aa+1, ... , Ab.
素朴なやり方でO(NQ)の明らかなTLE
区間統計の問題なので線分ツリーで解決してみます
線分ツリーノードが何を記録するかを考慮します
左右の息子区間範囲は必須:ls[]rs[]l[]r[]
質問に答えるために、現在の区間の和を保存するためにS[]を記録します.
*ツリーを建てるのは難しくないので、s[]の値を息子から上げることに注意してください.
1 procedure build(a,b:longint);
2 var x,mid:longint;
3 begin
4 inc(tt); x:=tt;
5 l[x]:=a; r[x]:=b;
6 if b-a=1
7 thenbegin
8 s[x]:=m[b];
9 exit; end
10 elsebegin
11 mid:=(a+b)shr 1;
12 ls[x]:=tt+1; build(a,mid);
13 rs[x]:=tt+1; build(mid,b);
14 s[x]:=s[ls[x]]+s[rs[x]];
15 end;
16 end;*C操作に遭遇した場合、aからbの間の区間で覆われているすべてのセグメントツリー区間を修正します.
+3行目で完全に上書きされているかどうかを判断すると、s[]値を直接変更します.
+5行目-7行目交差再帰修正があるかどうかを判断
+8行目で、完全に上書きされていない場合にのみ、息子から新しいs[]値が得られます.
1 procedure insert(x,a,b,c:longint);
2 var mid:longint;
3 if (a<=l[x])and(r[x]<=b)
4 then s[x]:=s[x]+(r[x]-l[x])*c;
5 mid:=(l[x]+r[x])shr 1;
6 if a<mid then insert(ls[x],a,b,c);
7 if mid<b then insert(rs[x],a,b,c);
8 ifnot(a<=l[x])and(r[x]<=b)
9 then s[x]:=s[ls[x]]+s[rs[x]];
10 end; *Q操作に遭遇した場合,aからbの区間内のすべてのサブ区間の和を再帰的にクエリして答えを得る.
-5行目調べた区間が完全に上書きされた場合、直接戻り値
-10-14行目交差に基づいて再帰クエリ
1 function query(x,a,b:longint):int64;
2 var mid:longint;
3 ans:int64;
4 begin
5 if (a<=l[x])and(r[x]<=b)
6 thenbegin
7 query:=s[x];
8 exit;
9 end;
10 ans:=0;
11 mid:=(l[x]+r[x])shr 1;
12 if a<mid then ans:=ans+query(ls[x],a,b);
13 if mid<b then ans:=ans+query(rs[x],a,b);
14 query:=ans;
15 end;クエリ操作の複雑さがO(Log 2 N)を超えないことを証明できる[定数が2]未満 問題のニーズに対応
しかし,修正操作の最悪の複雑さはO(N)に達することができ,定数は素朴さよりも大きく最適化を考慮しなければならない.
2つの操作の差を2つの概略図で見ることができます
クエリ[2,10]
修正[2,10]
この問題を解決するために有名なLazy-Tag思想が生まれた.
毎回すべての区間を修正するのが遅すぎるので、怠けて先に帳簿を覚えてからやったほうがいいです.
怠け者-記帳=Lazy-Tag
どうやって記録しますか?もう1つのドメインv[]を追加する必要があります.このドメインはタグです.
現在のノードがルートであるサブツリーを記録するには、どのくらい加算するかを指定します.
私たちのプログラムはもうすぐ変更されます.
+現在の区間を完全に修正したい区間に上書きされるたびに、直接タグに付けて終了します.
+1つのノードにアクセスするたびに、現在のノードのタグを空にします.
-アクセスにはさまざまなアクションが含まれます 削除を挿入してもクエリーを挿入しても、ノードのみのs[]値を使用しても
-現在のノードをタグで更新するだけでなく、タグの下を左右のサブツリーに渡すことも含まれます.
*個別のプロセスcleanを使用して、タグをクリアする操作を行います.
注意が必要なのは、リーフノードが下にマークを付けなくてもRE
1 procedure clean(x:longint);
2 begin
3 if v[x]<>0
4 thenbegin
5 s[x]:=s[x]+(r[x]-l[x])*v[x];
6 if ls[x]<>0then v[ls[x]]:=v[ls[x]]+v[x];
7 if rs[x]<>0then v[rs[x]]:=v[rs[x]]+v[x];
8 v[x]:=0;
9 end;
10 end;*修正後の修正プロセス
+最初の行をクリアする
+5行目修正タグを完全に上書きした場合は終了
+10～12行目の再帰的なサブツリーの変更
+13～14行目現在の区間のs[]値を更新 マークを空にする必要があります.
1 procedure insert(x,a,b,c:longint);
2 var mid:longint;
3 begin
4 clean(x);
5 if (a<=l[x])and(r[x]<=b)
6 thenbegin
7 v[x]:=v[x]+c;
8 exit;
9 end;
10 mid:=(l[x]+r[x])shr 1;
11 if a<mid then insert(ls[x],a,b,c);
12 if mid<b then insert(rs[x],a,b,c);
13 clean(ls[x]); clean(rs[x]);
14 s[x]:=s[ls[x]]+s[rs[x]];
15 end;*変更後のクエリー
クリアマークも付けて
この再帰完了更新s[]値を加えることも避けられない
1 function query(x,a,b:longint):int64;
2 var mid:longint;
3 ans:int64;
4 begin
5 clean(x);
6 if (a<=l[x])and(r[x]<=b)
7 thenbegin
8 query:=s[x];
9 exit;
10 end;
11 ans:=0;
12 mid:=(l[x]+r[x])shr 1;
13 if a<mid then ans:=ans+query(ls[x],a,b);
14 if mid<b then ans:=ans+query(rs[x],a,b);
15 clean(ls[x]); clean(rs[x]);
16 s[x]:=s[ls[x]]+s[rs[x]];
17 query:=ans;
18 end;完全なコードは文章の最後にあります
もちろんLazy-Tagは非常に強力なデータ構造Splayに使用できます
この問題はまだLazy-Tagの一般的な法則を運用していない.
もう一つの質問を考えましたが、区間全体を1つ乗せれば?
次に、デュアルタグの問題について説明します.
あと1つの数でタグドメインを追加します
u[]でノードxがルートであるサブツリーを表すにはu[x]を付ける必要がある
ノードxがルートであるサブツリーをv[]で表すにはv[x]を乗じる必要がある
実際の演算では,乗算と加算の動作シーケンスが不確定であることが分かった.
操作シーケンス全体を2つのタグで要約するには
振り返ってみると、一つの問題は加算だけの場合、加算シーケンスがどんなものであっても
加算の交換法則と結合法則に基づいて,配列全体の和を保存すればよい.
でも乗せれば簡単には覚えられない
マークの操作規則を先に規定するのが良い方法です 先に乗ってから加える
任意のノードx v[x]およびu[x]に対して現在のs[x]がs[x]*v[x]+u[x]に更新される必要があることを示す
タグを変更するたびに
現在の区間に数cを乗じる必要がある場合は、v[x]とu[x]の両方にcを乗じる
(s[x]*v[x]+u[x])*c=s[x]*(v[x]*c)+(u[x]*c)
現在の区間に数cを加算する必要がある場合はu[x]+cのみでよい
(s[x]*v[x]+u[x])+c=s[x]*v[x]+(u[x]+c)
いずれかの操作に対してのみ
無条件に区間のマークを直接修正して効果を達成できることを保証します.
Lazy-Tagを便利に使えます
そうでなければ、今マークを渡すときは、まず息子のマークを空にすることを考えなければなりません.
cleanプロセスは再帰的プロセス効率になりまたO(N)に戻る
コードの必要は前の問題に修正して文章の最後に貼り付けます
コアのプロセスはcleanです
1 procedure clean(x:longint);
2 begin
3 if (u[x]<>0)or(v[x]<>1)
4 thenbegin
5 s[x]:=s[x]*v[x]+u[x]*(r[x]-l[x]);
6 if ls[x]<>0
7 thenbegin
8 v[ls[x]]:=v[ls[x]]*v[x];
9 u[ls[x]]:=u[ls[x]]*v[x]+u[x];
10 end;
11 if rs[x]<>0
12 thenbegin
13 v[rs[x]]:=v[rs[x]]*v[x];
14 u[rs[x]]:=u[rs[x]]*v[x]+u[x];
15 end;
16 v[x]:=1; u[x]:=0;
17 end;
18 end;もう一つの問題を議論するのもダブルタグです
シーケンスのメンテナンス
サポート操作は1つの区間に1つの数を統一的に加算します.
1つの区間を統一して1つの数に変更する
区間とどのくらいですか
3つのドメインs[]{Sum}c[]{Cover}d[]{Delta}の追加メンテナンスが容易に考えられる
現在区間をそれぞれ表す和s現在区間をc現在区間に上書きするにはdを加算する必要がある
2つのタグドメインd[]とc[]の関係を同様に分析する
2つのタグドメインが存在する場合、それはまず上書きしますか、それとも先に上書きしますか.
以下のいくつかの性質を発見することができます
ある区間xに対してc[x]を上書きすると以前のc[x]とd[x]は自動的に消失する
ある区間にd[x]を加えた後、c[x]に値があればc[x]に直接加えることができる.
これにより,c[x]とd[x]の最大1つの値が存在することを保証できる. 上の問題はありません
したがって、c[]の優先度はd[]より高いと規定してもよい. c[x]に値がある場合はc[x]のみを実行し、そうでない場合はd[x]を実行する
私たちはまた一つの結論を得た. 相互干渉のタグに対して明確な優先度を定めて操作秩序を保証する
コアかcleanプロセスか
1 procedure down(x:longint);
2 begin
3 if c[x]<>key
4 thenbegin
5 s[x]:=c[x]*(r[x]-l[x]);
6 if ls[x]<>0
7 thenbegin
8 c[ls[x]]:=c[x];
9 d[ls[x]]:=0;
10 end;
11 if rs[x]<>0
12 thenbegin
13 c[rs[x]]:=c[x];
14 d[rs[x]]:=0;
15 end;
16 c[x]:=key;
17 end
18 elseif d[x]<>0
19 thenbegin
20 s[x]:=s[x]+d[x]*(r[x]-l[x]);
21 if ls[x]<>0thenif c[ls[x]]<>key
22 then c[ls[x]]:=c[ls[x]]+d[x]
23 else d[ls[x]]:=d[ls[x]]+d[x];
24 if rs[x]<>0thenif c[rs[x]]<>key
25 then c[rs[x]]:=c[rs[x]]+d[x]
26 else d[rs[x]]:=d[rs[x]]+d[x];
27 d[x]:=0;
28 end;
29 end;Lazy-Tagについての議論はここまでです
次のディスカッション 線分ツリーの拡張
Bob HANオリジナル転載は出典を明記してくださいhttp://www.cnblogs.com/Booble/
完全なコードを添付
Simple
1 const maxn=200000;
2 var l,r,ls,rs:array[1..maxn shl 1]of longint;
3 v,s:array[1..maxn shl 1]of int64;
4 m:array[1..maxn]of longint;
5 n,tt,i,q,a,b,c:longint;
6 ch,blank:char;
7 procedure build(a,b:longint);
8 var x,mid:longint;
9 begin
10 inc(tt); x:=tt;
11 l[x]:=a; r[x]:=b;
12 v[x]:=0;
13 if b-a=1
14 thenbegin
15 s[x]:=m[b];
16 exit; end
17 elsebegin
18 mid:=(a+b)shr 1;
19 ls[x]:=tt+1; build(a,mid);
20 rs[x]:=tt+1; build(mid,b);
21 s[x]:=s[ls[x]]+s[rs[x]];
22 end;
23 end;
24 procedure clean(x:longint);
25 begin
26 if v[x]<>0
27 thenbegin
28 s[x]:=s[x]+(r[x]-l[x])*v[x];
29 if ls[x]<>0then v[ls[x]]:=v[ls[x]]+v[x];
30 if rs[x]<>0then v[rs[x]]:=v[rs[x]]+v[x];
31 v[x]:=0;
32 end;
33 end;
34 procedure insert(x,a,b,c:longint);
35 var mid:longint;
36 begin
37 clean(x);
38 if (a<=l[x])and(r[x]<=b)
39 thenbegin
40 v[x]:=v[x]+c;
41 exit;
42 end;
43 mid:=(l[x]+r[x])shr 1;
44 if a<mid then insert(ls[x],a,b,c);
45 if mid<b then insert(rs[x],a,b,c);
46 clean(ls[x]); clean(rs[x]);
47 s[x]:=s[ls[x]]+s[rs[x]];
48 end;
49 function query(x,a,b:longint):int64;
50 var mid:longint;
51 ans:int64;
52 begin
53 clean(x);
54 if (a<=l[x])and(r[x]<=b)
55 thenbegin
56 query:=s[x];
57 exit;
58 end;
59 ans:=0;
60 mid:=(l[x]+r[x])shr 1;
61 if a<mid then ans:=ans+query(ls[x],a,b);
62 if mid<b then ans:=ans+query(rs[x],a,b);
63 clean(ls[x]); clean(rs[x]);
64 s[x]:=s[ls[x]]+s[rs[x]];
65 query:=ans;
66 end;
67 begin
68 assign(input,'simple.in'); reset(input);
69 assign(output,'simple.out'); rewrite(output);
70 readln(n,q);
71 for i:=1to n do
72 read(m[i]);
73 tt:=0;
74 build(0,n);
75 readln;
76 for i:=1to q do
77 begin
78 read(ch); read(blank);
79 case ch of
80 'Q': begin
81 readln(a,b);
82 writeln(query(1,a-1,b));
83 end;
84 'C': begin
85 readln(a,b,c);
86 insert(1,a-1,b,c);
87 end;
88 end;
89 end;
90 close(input); close(output);
91 end.
92 SuperSImple
1 const maxn=100000;
2 var l,r,ls,rs:array[1..maxn shl 1-1]of longint;
3 u,v,s:array[1..maxn shl 1-1]of int64;
4 m:array[1..maxn]of longint;
5 n,q,tt,i,a,b,c:longint;
6 ch,blank:char;
7 procedure build(a,b:longint);
8 var mid,x:longint;
9 begin
10 inc(tt); x:=tt;
11 l[x]:=a; r[x]:=b;
12 u[x]:=0; v[x]:=1;
13 if b-a=1
14 then s[x]:=m[b]
15 elsebegin
16 mid:=(a+b)shr 1;
17 ls[x]:=tt+1; build(a,mid);
18 rs[x]:=tt+1; build(mid,b);
19 s[x]:=s[ls[x]]+s[rs[x]];
20 end;
21 end;
22 procedure clean(x:longint);
23 begin
24 if (u[x]<>0)or(v[x]<>1)
25 thenbegin
26 s[x]:=s[x]*v[x]+u[x]*(r[x]-l[x]);
27 if ls[x]<>0
28 thenbegin
29 v[ls[x]]:=v[ls[x]]*v[x];
30 u[ls[x]]:=u[ls[x]]*v[x]+u[x];
31 end;
32 if rs[x]<>0
33 thenbegin
34 v[rs[x]]:=v[rs[x]]*v[x];
35 u[rs[x]]:=u[rs[x]]*v[x]+u[x];
36 end;
37 v[x]:=1; u[x]:=0;
38 end;
39 end;
40 procedure mult(x,a,b,c:longint);
41 var mid:longint;
42 begin
43 clean(x);
44 if (a<=l[x])and(r[x]<=b)
45 thenbegin
46 u[x]:=u[x]*c;
47 v[x]:=v[x]*c;
48 exit; end;
49 mid:=(l[x]+r[x])shr 1;
50 if a<mid then mult(ls[x],a,b,c);
51 if mid<b then mult(rs[x],a,b,c);
52 clean(ls[x]); clean(rs[x]);
53 s[x]:=s[ls[x]]+s[rs[x]];
54 end;
55 procedure plus(x,a,b,c:longint);
56 var mid:longint;
57 begin
58 clean(x);
59 if (a<=l[x])and(r[x]<=b)
60 thenbegin
61 u[x]:=u[x]+c;
62 exit; end;
63 mid:=(l[x]+r[x])shr 1;
64 if a<mid then plus(ls[x],a,b,c);
65 if mid<b then plus(rs[x],a,b,c);
66 clean(ls[x]); clean(rs[x]);
67 s[x]:=s[ls[x]]+s[rs[x]];
68 end;
69 function query(x,a,b:longint):int64;
70 var mid:longint;
71 ans:int64;
72 begin
73 clean(x);
74 if (a<=l[x])and(r[x]<=b)
75 thenbegin
76 query:=s[x];
77 exit; end;
78 ans:=0;
79 mid:=(l[x]+r[x])shr 1;
80 if a<mid then ans:=ans+query(ls[x],a,b);
81 if mid<b then ans:=ans+query(rs[x],a,b);
82 query:=ans;
83 clean(ls[x]); clean(rs[x]);
84 s[x]:=s[ls[x]]+s[rs[x]];
85 end;
86 begin
87 assign(input,'ssimple.in'); reset(input);
88 assign(output,'ssimple.out'); rewrite(output);
89 readln(n,q);
90 for i:=1to n do
91 read(m[i]);
92 readln;
93 tt:=0;
94 build(0,n);
95 for i:=1to q do
96 begin
97 read(ch); read(blank);
98 case ch of
99 'Q': begin
100 readln(a,b);
101 writeln(query(1,a-1,b));
102 end;
103 'M': begin
104 readln(a,b,c);
105 mult(1,a-1,b,c);
106 end;
107 'P': begin
108 readln(a,b,c);
109 plus(1,a-1,b,c);
110 end;
111 end;
112 end;
113 close(input); close(output);
114 end.
115 Paint
1 const maxn=100000;
2 key=-219;
3 max=maxn*2;
4 var l,r,ls,rs,c,d,s:array[1..max]of longint;
5 v:array[1..maxn]of longint;
6 m,k,i,tt,x,y,z:longint;
7 ch,ignore:char;
8 procedure down(x:longint);
9 begin
10 if c[x]<>key
11 thenbegin
12 s[x]:=c[x]*(r[x]-l[x]);
13 if ls[x]<>0
14 thenbegin
15 c[ls[x]]:=c[x];
16 d[ls[x]]:=0;
17 end;
18 if rs[x]<>0
19 thenbegin
20 c[rs[x]]:=c[x];
21 d[rs[x]]:=0;
22 end;
23 c[x]:=key;
24 end
25 elseif d[x]<>0
26 thenbegin
27 s[x]:=s[x]+d[x]*(r[x]-l[x]);
28 if ls[x]<>0thenif c[ls[x]]<>key
29 then c[ls[x]]:=c[ls[x]]+d[x]
30 else d[ls[x]]:=d[ls[x]]+d[x];
31 if rs[x]<>0thenif c[rs[x]]<>key
32 then c[rs[x]]:=c[rs[x]]+d[x]
33 else d[rs[x]]:=d[rs[x]]+d[x];
34 d[x]:=0;
35 end;
36 end;
37 procedure update(x:longint);
38 begin
39 down(ls[x]); down(rs[x]);
40 s[x]:=s[ls[x]]+s[rs[x]];
41 end;
42 procedure build(a,b:longint);
43 var x,mid:longint;
44 begin
45 inc(tt); x:=tt;
46 l[x]:=a; r[x]:=b;
47 d[x]:=0; c[x]:=key;
48 if b-a=1
49 then s[x]:=v[b]
50 elsebegin
51 mid:=(a+b)shr 1;
52 ls[x]:=tt+1; build(a,mid);
53 rs[x]:=tt+1; build(mid,b);
54 s[x]:=s[ls[x]]+s[rs[x]];
55 end;
56 end;
57 procedure cover(x,a,b,v:longint);
58 var mid:longint;
59 begin
60 down(x);
61 if (a<=l[x])and(r[x]<=b)
62 thenbegin c[x]:=v; d[x]:=0; end
63 elsebegin
64 mid:=(l[x]+r[x])shr 1;
65 if a<mid then cover(ls[x],a,b,v);
66 if b>mid then cover(rs[x],a,b,v);
67 update(x);
68 end;
69 end;
70 procedure insert(x,a,b,v:longint);
71 var mid:longint;
72 begin
73 down(x);
74 if (a<=l[x])and(r[x]<=b)
75 thenif c[x]<>key
76 then c[x]:=c[x]+v
77 else d[x]:=d[x]+v
78 elsebegin
79 mid:=(l[x]+r[x])shr 1;
80 if a<mid then insert(ls[x],a,b,v);
81 if b>mid then insert(rs[x],a,b,v);
82 update(x);
83 end;
84 end;
85 function sum(x,a,b:longint):longint;
86 var mid:longint;
87 begin
88 down(x);
89 if (a<=l[x])and(r[x]<=b)
90 then sum:=s[x]
91 elsebegin
92 sum:=0;
93 mid:=(l[x]+r[x])shr 1;
94 if a<mid then sum:=sum+sum(ls[x],a,b);
95 if b>mid then sum:=sum+sum(rs[x],a,b);
96 update(x);
97 end;
98 end;
99 begin
100 assign(input,'paint.in'); reset(input);
101 assign(output,'paint.out'); rewrite(output);
102 readln(m,k);
103 for i:=1to m do
104 read(v[i]);
105 readln;
106 tt:=0;
107 build(0,m);
108 for i:=1to k do
109 begin
110 read(ch);
111 repeat read(ignore); until ignore='';
112 read(x,y);
113 if ch<>'S'then read(z);
114 readln;
115 case ch of
116 'C':cover(1,x-1,y,z);
117 'A':insert(1,x-1,y,z);
118 'S':writeln(sum(1,x-1,y));
119 end;
120 end;
121 close(input); close(output);
122 end.
123