ccnu-线段树-简单的区间更新（三题）

Description

You have N integers, A1, A2, ... , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.

Input

The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000.

The second line contains N numbers, the initial values of A1, A2, ... , AN. -1000000000 ≤ Ai ≤ 1000000000.

Each of the next Q lines represents an operation.

"C abc" means adding c to each of Aa, Aa+1, ... , Ab. -10000 ≤ c ≤ 10000.

"Q ab" means querying the sum of Aa, Aa+1, ... , Ab.

Output

You need to answer all Q commands in order. One answer in a line.

Sample Input

10 5

1 2 3 4 5 6 7 8 9 10

Q 4 4

Q 1 10

Q 2 4

C 3 6 3

Q 2 4

Sample Output

4

55

9

15

Hint

The sums may exceed the range of 32-bit integers.

裸的区间更新，关于lazy标记，还是老话，在下一次更新或询问时才把区间信息传递（pushdown）下去。

代码：

#include<iostream>

#include<cstdio>

#include<string>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define Max  100020

long long a,b,q,n;

long long sum[Max<<2],c,lazy[Max<<2];

void pushup(int rt)

{

    sum[rt] = sum[rt<<1] + sum[rt<<1|1];

}

void pushdown(int rt,int m)

{

    if(lazy[rt])

    {

        lazy[rt<<1] += lazy[rt];

        lazy[rt<<1|1] += lazy[rt];

        sum[rt<<1] += lazy[rt] * (m - (m>>1));

        sum[rt<<1|1] += lazy[rt] * (m>>1);

        lazy[rt] = 0;

    }

}

void build(int l,int r,int rt)

{

    sum[rt] = 0;

    if(l == r)

    {

        scanf("%lld",&sum[rt]);

        return;

    }

    int m = (r + l)>>1;

    build(lson);

    build(rson);

    pushup(rt);

}

void Add(int L,int R,int v,int l,int r,int rt)

{

    if(L <= l&&r <= R)

    {

        lazy[rt] += v;

        sum[rt] += (long long)(r - l + 1) * v;

        return ;

    }

    pushdown(rt,r-l+1);

    int m = (r + l)>>1;

    if(L <= m) Add(L,R,v,lson);

    if(m < R) Add(L,R,v,rson);

    pushup(rt);

}

long long query(int L,int R,int l,int r,int rt)

{

    if(L <= l&&r <= R)

    {

        return sum[rt];

    }

    long long rec = 0;

    int m = (r + l)>>1;

    pushdown(rt,r-l+1);

    if(L <= m) rec += query(L,R,lson);

    if(m < R) rec += query(L,R,rson);

    return rec;

}

int main()

{

    scanf("%d%d",&n,&q);

    build(1,n,1);

    while(q--)

    {

        char qus[2];

        scanf("%s",&qus);

        if(qus[0] == 'C')

        {

            scanf("%d%d%d",&a,&b,&c);

            Add(a,b,c,1,n,1);

        }

        else

        {

            scanf("%d%d",&a,&b);

            printf("%lld\n",query(a,b,1,n,1));

        }

    }

    return 0;

}

题型二：http://acm.hdu.edu.cn/showproblem.php?pid=1698

把上题的求和改成更新区间值就可以了。

代码如下：

#include<iostream>

#include<cstdio>

#define Max 100010

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

using namespace std;

int sum[Max<<2],lazy[Max<<2];

void pushup(int rt)

{

    sum[rt] = sum[rt<<1] + sum[rt<<1|1];

}

void pushdown(int rt,int INL)

{

    if(lazy[rt])

    {

        lazy[rt<<1] = lazy[rt<<1|1] = lazy[rt];

        sum[rt<<1] = lazy[rt] * (INL - (INL>>1));

        sum[rt<<1|1] = lazy[rt] * (INL>>1);

        lazy[rt] = 0;

    }

}

void build(int l,int r,int rt)

{

    lazy[rt] = 0;

    sum[rt] = 1;

    if(r == l)

    {

        return;

    }

    int m = (r + l) >>  1;

    build(lson);

    build(rson);

    pushup(rt);

}

void update(int L,int R,int val,int l,int r,int rt)

{

    if(L <= l&&r <= R)

    {

        sum[rt] = val * (r-l+1);

        lazy[rt] = val;

        return;

    }

    pushdown(rt,r-l+1);

    int m = (r + l)>>1;

    if(L <= m) update(L,R,val,lson);

    if(m < R) update(L,R,val,rson);

    pushup(rt);

}

int main()

{

    int T,n,x,y,z,q;

    scanf("%d",&T);

    int lala = T;

    while(T--)

    {

        scanf("%d",&n);

        build(1,n,1);

        scanf("%d",&q);

        while(q--)

        {

            scanf("%d%d%d",&x,&y,&z);

            update(x,y,z,1,n,1);

        }

        printf("Case %d: The total value of the hook is %d.\n",(lala-T),sum[1]);

    }

    return 0;

}

【题型三-hdu-ColorTheBall】http://acm.hdu.edu.cn/showproblem.php?pid=1556

题意：把a,b区间的气球都涂上颜色，输出每个气球被涂色的次数。

思路：每次更新只记录到所更新的区间便不再往下记录更新，不需要pushup，只需要在输出时pushdown更新一次到每个节点就可以了

经验教训：不要用cout，不要用cout，不要用cout！

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

#define maxn 100010

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

int lazy[maxn<<4];

 int n;

//int index[maxn];

void build(int l, int r, int rt)

{

  int m;

  m = (l + r)>>1;

  lazy[rt] = 0;

  if(l == r) return;

  build(lson);

  build(rson);

}

void pushdown(int rt)

{

  if(lazy[rt])

  {

    lazy[rt<<1] += lazy[rt];

    lazy[rt<<1|1] += lazy[rt];

    lazy[rt] = 0;

  }

}

void paint(int l, int r, int rt, int L, int R)

{

  if(L <= l && r <= R)

  {

    lazy[rt]++;

    return ;

  }

  int m = (r+l)>>1;

  if(L <= m) paint(lson, L,R);

  if(m < R) paint(rson, L, R);

}

void finalQuery(int l, int r, int rt)

{

  int m = (l+r)>>1;

  if(l == r)

  {

     printf("%d%c",lazy[rt],l==n?'\n':' ');

     return;

  }

  pushdown(rt);   //在查询的时候才pushdown

  finalQuery(lson);

  finalQuery(rson);

}

int main()

{

 while(scanf("%d", &n) != EOF&&n)

 {

   build(1,n,1);

   for(int i = 0; i < n; i++)

   {

     int a, b;

     scanf("%d%d", &a, &b);

     paint(1, n, 1, a, b);

     //cout<<"-"<<endl;

   }

   finalQuery(1, n, 1);

 }

 return 0;

}

巴特西

ccnu-线段树-简单的区间更新（三题）

最新文章

热门文章