A Simple Problem with Integers---poj3468線段樹 -开发者知识库

A Simple Problem with Integers---poj3468線段樹 -开发者知识库,第1张

http://poj.org/problem?id=3468

 

A Simple Problem with Integers---poj3468線段樹 -开发者知识库,第2张

 

題意:有一個比較長的區間可能是100000.長度, 每個點都有一個值(值還比較大),

現在有一些操作:

C a b c, 把區間a--b內全部加上c

Q a b,求區間ab的值和。

線段樹 改變整個區間的數

這題不能直接更新到樹的葉子節點, 因為那樣時間復雜度太高,我們可以在每個節點上加一個變量k,表示這個節點的所有點(L到R)都要增加 k, 所以我們可以在從上往下查找的過程中如果不是所求區間,那么我們就把本區間加上應該加的數,否則的話,就停止,這樣每次更新的過程時間復雜度也是log n,查找時, 我們需要把含有K值得那些點放到它的子節點上去,只需要一層就可以了,具體過程看代碼

 

 

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

#define INF 0xfffffff
#define N 400050
#define Lson root<<1
#define Rson root<<1|1

struct SegmentTree
{
    int L, R;
    long long sum, k;
    int Mid()
    {
        return (L R)>>1;
    }
    int len()
    {
        return R-L 1;
    }
} a[N<<2];

void BuildSegTree(int root, int L, int R)
{
    a[root].L = L;
    a[root].R = R;
    a[root].k = 0;
    if( L == R )
    {
        scanf("%lld", &a[root].sum);
        return ;
    }

    BuildSegTree(Lson, L, a[root].Mid());
    BuildSegTree(Rson, a[root].Mid() 1, R);

    a[root].sum = a[Rson].sum   a[Lson].sum;
}

void Update(int root, int L, int R, int k)
{
    a[root].sum  = (R - L   1) * k;

    if(a[root].L == L && a[root].R == R)///當到達要更新的那個區間時,把k值更新,並返回;
    {
        a[root].k  = k;
        return ;
    }

    if(R <= a[root].Mid())///右邊;
        Update(Lson, L, R, k);
    else if(L > a[root].Mid())///左邊;
        Update(Rson, L, R, k);
    else///中間;
    {
        Update(Lson, L, a[root].Mid(), k);
        Update(Rson, a[root].Mid() 1, R, k);
    }
}

void Down(int root)
{
    a[Lson].sum  = a[Lson].len()*a[root].k;
    a[Rson].sum  = a[Rson].len()*a[root].k;///左右兒子的和都要增加對應的值,注意這里看清楚增加的是誰;
    a[Lson].k  = a[root].k;
    a[Rson].k  = a[root].k;///接着往下傳遞K值;
    a[root].k = 0;///傳下去之后就置0;
}
long long Query(int root, int L, int R)
{
    if(a[root].L==L && a[root].R == R)///當剛好是這個區間時返回結果;
        return a[root].sum;

    Down(root);///往下傳遞K值;

    if(R <= a[root].Mid())
        return Query(Lson, L, R);
    else if( L > a[root].Mid())
        return Query(Rson, L, R);
    else
    {
        long long Lsum = Query(Lson, L, a[root].Mid());
        long long Rsum = Query(Rson, a[root].Mid() 1, R);
        return Lsum   Rsum;
    }
}

int main()
{
    int n, m, L, R, k;
    long long ans;
    char s[10];
    while(scanf("%d %d", &n, &m) != EOF)
    {
        BuildSegTree(1, 1, n);
        for(int i=0; i<m; i  )
        {
            scanf("%s", s);
            if(s[0] == 'Q')
            {
                scanf("%d %d", &L, &R);
                ans = Query(1, L, R);
                printf("%lld\n", ans);
            }
            else
            {
                scanf("%d %d %d", &L, &R, &k);
                Update(1, L, R, k);
            }
        }
    }
    return 0;
}
/*
100
2 3 4 5 6 7 8 9 10
Q 1 5
C 1 10 1
Q 3 5

*/

最佳答案:

本文经用户投稿或网站收集转载,如有侵权请联系本站。

发表评论

0条回复