WARush

SRMの結果とか、解けた問題のコードを書いていきます

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;
}