線分ツリー:CDOJ 1597-An easy problem C(区間更新線分ツリー)
11695 ワード
An easy problem C
Time Limit: 4000/2000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)
Problem Description
N個の数を一列に並べて、3種類の操作があります.1.区間内の各数に非負の整数を乗算します.2.区間内の各数に非負の整数.3を加算し、区間の和型上Pの値を尋ねる.
Input
1行目の2つの整数N(1≦N≦100000)は数の個数を表し、P(1≦P≦10000000)はモードの値を表す.次の行のN個の整数ai(0≦ai≦10000000)、次の行の1個の整数M(1≦M≦100000)は、動作数を表し、次に、M行の各行は、動作数を表す.1つ目の動作説明:1 LのR C(0≦C≦10000000)は、LからRまでの区間の各数に1つのCを乗算することを示す.第2の動作説明:2 LのR C(0≦C≦10000000)は、LからRまでの区間の各数に1つのCを加算することを示す.第3の動作3 L Rは、LからRまでの区間の数を尋ねる和型上Pの値を示す.
Output
各質問に対して、対応する答えを出力し、各質問が1行を占めます.
Sample Input
7 43 1 2 3 4 5 6 7 5 1 2 5 5 3 2 4 2 3 7 9 3 1 3 3 4 7
Sample Output
2 35 8
問題を解く心得:これは区間更新の線分樹で、書くのが煩わしいです.この線分の木を書いてまず何時か話します. は、まずlazyタグである.このlazyタグは、区間全体をタグする区間ですが、この区間のサブツリーを処理するのではなく、この区間のサブツリーを使用する場合にのみサブツリーを更新し、lazyタグを下に移動することで、区間更新を処理する際に時間的複雑度がO(logn)になります.Lazyタグの特徴は怠け者で、現在のタグを下に移動しないだけで、下のサブツリーを使用するときに下に移動します.ここで注意しなければならないのは、lazyマークが下に移動した後、この区間のlazyマークがキャンセルされるべきだという初心者は忘れやすいことです. それからこの問題の処理で、面倒で、それは1つの区間に1つの数を加えることを要求して、あるいは1つの数を乗ることを要求して、毎回プラスしてあるいは乗る時すべての区間のsumを更新して、また上へ維持します.現在のsumはすぐに更新されますが、このときの乗算の合計と加算の合計はlazyタグと見なされ、使用するときに下に移動します.また、乗算と加算の優先度の問題は、先に加算に乗るべきです. この問題は、アップメンテナンスとダウンメンテナンスに対する要求が高く、注意しないと多くのバグが発生します.
転載先:https://www.cnblogs.com/GoldenFingers/p/9107310.html
Time Limit: 4000/2000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)
Problem Description
N個の数を一列に並べて、3種類の操作があります.1.区間内の各数に非負の整数を乗算します.2.区間内の各数に非負の整数.3を加算し、区間の和型上Pの値を尋ねる.
Input
1行目の2つの整数N(1≦N≦100000)は数の個数を表し、P(1≦P≦10000000)はモードの値を表す.次の行のN個の整数ai(0≦ai≦10000000)、次の行の1個の整数M(1≦M≦100000)は、動作数を表し、次に、M行の各行は、動作数を表す.1つ目の動作説明:1 LのR C(0≦C≦10000000)は、LからRまでの区間の各数に1つのCを乗算することを示す.第2の動作説明:2 LのR C(0≦C≦10000000)は、LからRまでの区間の各数に1つのCを加算することを示す.第3の動作3 L Rは、LからRまでの区間の数を尋ねる和型上Pの値を示す.
Output
各質問に対して、対応する答えを出力し、各質問が1行を占めます.
Sample Input
7 43 1 2 3 4 5 6 7 5 1 2 5 5 3 2 4 2 3 7 9 3 1 3 3 4 7
Sample Output
2 35 8
問題を解く心得:
// long long
#include
",ans);
}
}
}
return 0;
}
転載先:https://www.cnblogs.com/GoldenFingers/p/9107310.html