Codeforces #179 Div2 C "Greg and Array"
問題
http://codeforces.com/contest/296/problem/C
訳
a = a1, a2, ..., an という配列と、m個のオペレーションがある。
各オペレーションは li, ri, di ( 1 <= li <= ri <= n )
という形式になっている。
オペレーション i を実行すると、
配列のli番目からri番目の要素全てをdiだけ増加させる。
k個のクエリがある。
各クエリは xi, yi ( 1 <= xi <= yi <= m )という形式になっている。
そのクエリは、xi番目からyi番目のオペレーションを実行せよ、という意味である。
全てのクエリに対応した時の配列の状態を出力せよ。
制約
1 <= n, m, k <= 10^5
1 <= ai <= 10^5
1 <= di <= 10^5
考えた事
全てのクエリ見ていって、
いもす法で各オペレーションが何回行われるかを確認し、
BITを使って配列の値を増加させていく。
事後
xr0038さんが進研ゼミに例えたけどまさにそんな感じ。
「あ、これゼミでやったのと同じだ!」
ソースコード
// BITクラス宣言 class BinaryIndexedTree { public: BinaryIndexedTree(); ~BinaryIndexedTree(); void init( int size ); int elementNumber(); void add( int a, int b, long long x ); long long sum( int a, int b ) const; private: void add( int a, int b, long long x, int i, int l, int r ); long long sum( int a, int b, int i, int l, int r ) const; int m_ElementNumber; int m_ArrayCapacity; long long* m_tree_a; long long* m_tree_b; }; int N, M, K; int L[100050]; int R[100050]; int D[100050]; int C[100050]; BinaryIndexedTree bit; int main() { // 配列(BIT)初期化 cin >> N >> M >> K; bit.init(N+1); for( int i = 1; i <= N; i++ ){ int x; cin >> x; bit.add( i, i+1, x ); } // オペレーション入力 for( int i = 1; i <= M; i++ ){ cin >> L[i] >> R[i] >> D[i]; } // いもす法発動 memset( C, 0, sizeof(C) ); for( int i = 1; i <= K; i++ ){ int x, y; cin >> x >> y; C[x]++; C[y+1]--; } // オペレーションを実行 for( int i = 1, count = 0; i <= M; i++ ){ count += C[i]; bit.add( L[i], R[i]+1, (long long)D[i] * count ); } // 出力 for( int i = 1; i <= N; i++ ){ long long num = bit.sum( i, i+1 ); printf( "%I64d ", num ); } } // BITクラス定義 BinaryIndexedTree::BinaryIndexedTree() { } BinaryIndexedTree::~BinaryIndexedTree() { delete[] m_tree_a; m_tree_a = 0; delete[] m_tree_b; m_tree_b = 0; } void BinaryIndexedTree::init( int elementNumber ) { m_ElementNumber = elementNumber; int power = 0; while( elementNumber != 0 ){ elementNumber >>= 1; power++; } m_ArrayCapacity = 1 << (power + 1); m_tree_a = new long long[m_ArrayCapacity]; m_tree_b = new long long[m_ArrayCapacity]; for( int i = 0; i < m_ArrayCapacity; i++ ){ m_tree_a[i] = m_tree_b[i] = 0; } } int BinaryIndexedTree::elementNumber() { return m_ElementNumber; } void BinaryIndexedTree::add( int a, int b, long long x ) { add( a, b, x, 0, 0, m_ElementNumber ); } long long BinaryIndexedTree::sum( int a, int b ) const { return sum( a, b, 0, 0, m_ElementNumber ); } void BinaryIndexedTree::add( int a, int b, long long x, int i, int l, int r ) { if( a <= l && r <= b ){ m_tree_a[i] += x; }else if( a < r && l < b ){ m_tree_b[i] += x * (min( b, r ) - max( a, l )); add( a, b, x, i*2+1, l, (l+r)/2 ); add( a, b, x, i*2+2, (l+r)/2, r ); } } long long BinaryIndexedTree::sum( int a, int b, int i, int l, int r ) const { long long res = 0; if( a <= l && r <= b ){ res = m_tree_a[i] * (r - l) + m_tree_b[i]; }else if( a < r && l < b ){ res += m_tree_a[i] * (min( b, r ) - max( a, l )); res += sum( a, b, i*2+1, l, (l+r)/2 ); res += sum( a, b, i*2+2, (l+r)/2, r ); } return res; }