Problem E

Time Limit : 3000/2000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)

Total Submission(s) : 357 Accepted Submission(s) : 16

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

给定一个长度为n的数组 a[1],a[2],a[3],a[4].....a[n]。
同时给定m个操作，每个操作有三个整形数据 x，y，z。
每个操作的意义就是给数组中下标为x与下标为y之间（包括x，y）的元素的值加上z。

Input

输入有多组数据(3组左右)
每一组数据第一行有两个整数 n，m 。（0<m<100000,0<n<1000000）;
第二行有n个整数，分别代表 a[1]，a[2]，a[3]，a[4]......a[n]的初始值.（0<=a[i]<10）
接下来就m行，每一行有3个整数,x,y,z。 (0<=x,y<=n, 0<z<10)
（请大家特别注意本题的数据范围）

Output

在一行内输出这个序列的所有元素的值，并且每个值之间应该以空格隔开。
（题目保证所有的输出数据都在int32范围内）

Sample Input

10 5

0 0 0 0 0 0 0 0 0 0

1 5 1

2 6 1

3 7 1

4 9 1

5 10 1

1 1

1

1 1 2

Sample Output

1 2 3 4 5 4 3 2 2 1

3

Author

moonlike

没错！！！看似简单其实很坑，坑在a和b不一定是a<b的关系。知道这个，用线段树就好

#include<stdio.h>

//#include<bits/stdc++.h>

#include<string.h>

#include<iostream>

#include<math.h>

#include<sstream>

#include<set>

#include<queue>

#include<map>

#include<vector>

#include<algorithm>

#include<limits.h>

#define inf 0x3fffffff

#define INF 0x3f3f3f3f

#define lson l,m,rt<<1

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

#define LL long long

#define ULL unsigned long long

using namespace std;

const int maxn = 1000000;

int add[maxn<<2];

int sum[maxn<<2];

int aa[1000000];

void PushUp(int rt){

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

}

void PushDown(int rt,int m){

    if (add[rt]){

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

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

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

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

        add[rt] = 0;

    }

}

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

    add[rt] = 0;

    if (l == r){

        sum[rt]=0;

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

        return ;

    }

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

    build(lson);

    build(rson);

    PushUp(rt);

}

void update(int L,int R,int c,int l,int r,int rt){

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

        add[rt] += c;

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

        return ;

    }

    PushDown(rt , r - l + 1);

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

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

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

    PushUp(rt);

}

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

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

        return sum[rt];

    }

    PushDown(rt , r - l + 1);

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

    int ret = 0;

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

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

    return ret;

}

int main(){

    int N , M;

    int i,j;

    int a,b,c;

    while(~scanf("%d%d",&N,&M)){

        build(1 , N , 1);

        for(i=1; i<=N; i++){

            scanf("%d",&aa[i]);

        }

        for(i=1; i<=M; i++){

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

            if(a==0){

                a+=1;

            }

            if(b==0){

                b+=1;

            }

            update(min(a,b),max(b,a),c,1,N,1);

        }

        if(N==1){

            printf("%d\n",aa[1]+query(1,1,1,N,1));

        }

        else{

            for(i=1; i<=N; i++){

                if(i!=N){

                    printf("%d ",aa[i]+query(i,i,1,N,1));

                }

                else{

                    printf("%d\n",aa[i]+query(i,i,1,N,1));

                }

            }

        }

    }

    return 0;

}

巴特西

华东交通大学2015年ACM“双基”程序设计竞赛1005