3141110_wa.cc

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <iostream>

using namespace std;

const int N = 100600;

long long n, m;
long long num[N];
long long sum[N];

long long len;
struct SegTree
{
    long long sum;
    long long increment;
    long long left, right;
    SegTree * Lchild, * Rchild;
    
    void Build(long long, long long);
    void Add(long long, long long, long long);
    long long Query(long long, long long);
}Tree[2 * N], * Root = Tree;

void SegTree::Build(long long l, long long r)
{
    left = l; right = r;
    if(l + 1 == r)
    {
        Lchild = &Tree[++len]; Rchild = &Tree[++len];
        Lchild -> Build(l, l); Rchild -> Build(r, r);
        return;
    }
    if(l == r)
    {
        Lchild = Rchild = NULL;
        return;
    }
    int mid = (l + r) / 2;
    Lchild = &Tree[++len]; Rchild = &Tree[++len];
    Lchild -> Build(l, mid); Rchild -> Build(mid + 1, r);
}

long long SegTree::Query(long long s, long long t)
{
    if(increment)
    {
        if(Lchild)
        {
            Lchild -> increment = increment;
            Lchild -> sum += (Lchild -> right - Lchild -> left + 1) * increment;
        }
        if(Rchild)
        {
            Rchild -> increment = increment;
            Rchild -> sum += (Rchild -> right - Rchild -> left + 1) * increment;
        }
        increment = 0;
    }
    if(left == s && right == t)
        return sum;
    int mid = (left + right) / 2;
    if(t <= mid)
        return Lchild -> Query(s, t);
    if(s >= mid + 1)
        return Rchild -> Query(s, t);
    return Lchild -> Query(s, mid) + Rchild -> Query(mid + 1, t);
}

void SegTree::Add(long long s, long long t, long long k)
{
    if(left == s && right == t)
    {
        increment = k;
        sum += (t - s + 1) * k;
        //cout << '.' << left << ' ' << right << ' ' << sum << endl;
        return;
    }
    long mid = (left + right) / 2;
    if(t <= mid)
    {
        Lchild -> Add(s, t, k);
        sum = Lchild -> sum + Rchild -> sum;
        return;
    }
    if(s >= mid + 1)
    {
        Rchild -> Add(s, t ,k);
        sum = Lchild -> sum + Rchild -> sum;
        return;
    }
    
    Lchild -> Add(s, mid, k);
    Rchild -> Add(mid + 1, t, k);
    
    sum = Lchild -> sum + Rchild -> sum;
    //cout << left << ' ' << right << ' ' << sum << endl;
    //cout << left << ' ' << right  << ' ' << Lchild -> tot << '+' << Rchild -> tot<<endl;
}

void read()
{
    
    scanf("%lld %lld", &n, &m);
    for(long long i = 1; i <= n; i++)
    {
        scanf("%lld", &num[i]);
        sum[i] = sum[i - 1] + num[i];
    }
}

int main()
{
    read();
    Root -> Build(1, n);
    
    long s, t, k;
    while(m)
        switch(getchar())
        {
            case 'Q' :
                m--;
                scanf("%lld %lld", &s, &t);
                printf("%lld\n", Root -> Query(s, t) + sum[t] - sum[s - 1]);
                break;
            case 'C' :
                m--;
                scanf("%lld %lld %lld", &s, &t, &k);
                Root -> Add(s, t, k);
                break;
        }
    
    return 0;
}