线段树模板（贼慢的版本）-白红宇

线段树模板（贼慢的版本）

阅读量：4619 次

发布时间：2019-06-09

本文共 3044 字，大约阅读时间需要 10 分钟。

事先说明这个模板很慢。。。。。

Accepted 100

用时: 933ms / 内存: 7592KB

编译信息

编译成功

/tmp/tmpj3s839y9/src: 在函数‘void change(long long int, long long int, long long int, long long int)’中:

/tmp/tmpj3s839y9/src:48:21: 警告：建议在‘>>’的操作数中出现的‘+’前后加上括号 [-Wparentheses]

int mid=tr[p].ll+tr[p].rr>>1;

~~~~~~~~^~~~~~~~~

/tmp/tmpj3s839y9/src: 在函数‘long long int outt(int, int, int)’中:

/tmp/tmpj3s839y9/src:57:21: 警告：建议在‘>>’的操作数中出现的‘+’前后加上括号 [-Wparentheses]

int mid=tr[p].ll+tr[p].rr>>1;

~~~~~~~~^~~~~~~~~

测试点信息

3ms/600KB

4ms/524KB

3ms/564KB

20ms/892KB

21ms/804KB

18ms/808KB

23ms/676KB

278ms/7592KB

316ms/7540KB

#10

247ms/7556KB

（这是洛谷的模板评测）

因为我太弱了，目前也就只能这样

当然，十分欢迎DALAO的指点！！！！

题目描述

如题，已知一个数列，你需要进行下面两种操作：

1.将某区间每一个数加上x

2.求出某区间每一个数的和

输入输出格式

输入格式：

第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。

第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。

接下来M行每行包含3或4个整数，表示一个操作，具体如下：

操作1：格式：1 x y k 含义：将区间[x,y]内每个数加上k

操作2：格式：2 x y 含义：输出区间[x,y]内每个数的和

输出格式：

输出包含若干行整数，即为所有操作2的结果。

输入输出样例

输入样例#1：

5 51 5 4 2 32 2 41 2 3 22 3 41 1 5 12 1 4

输出样例#1：

说明

时空限制：1000ms,128M

数据规模：

对于30%的数据：N<=8，M<=10

对于70%的数据：N<=1000，M<=10000

对于100%的数据：N<=100000，M<=100000

（数据已经过加强^_^，保证在int64/long long数据范围内）

样例说明：

#include
       
        using namespace std;long long n,m;long long a[100005];struct tree{    long long pre;    int ll;    int rr;    long long tag;//懒标记 }tr[100000*4+5];void spread(int p){
     //lazy tag    if(tr[p].tag){        tr[p*2].pre+=tr[p].tag*(tr[p*2].rr-tr[p*2].ll+1);        tr[p*2+1].pre+=tr[p].tag*(tr[p*2+1].rr-tr[p*2+1].ll+1);        tr[p*2].tag+=tr[p].tag;        tr[p*2+1].tag+=tr[p].tag;        tr[p].tag=0;    }}void push_down(long long p){    tr[p].pre=tr[p*2].pre+tr[p*2+1].pre;}void build(int p,int l,int r){    tr[p].ll=l;    tr[p].rr=r;    if(l==r){        tr[p].pre=a[l];        return;    }    int midd=(l+r)/2;    build(p*2,l,midd);    build(p*2+1,midd+1,r);    push_down(p);}void change(long long p,long long x,long long y,long long k){
     //区间加权     if(x<=tr[p].ll&&y>=tr[p].rr){        tr[p].pre+=k*(tr[p].rr-tr[p].ll+1);        tr[p].tag+=k;        return;    }    spread(p);    int mid=tr[p].ll+tr[p].rr>>1;    if(x<=mid) change(p*2,x,y,k);    if(y>mid) change(p*2+1,x,y,k);    tr[p].pre=tr[p*2].pre+tr[p*2+1].pre;   }long long outt(int p,int x,int y){
     //区间和输出     if(x<=tr[p].ll&&y>=tr[p].rr) return tr[p].pre;    spread(p);    int mid=tr[p].ll+tr[p].rr>>1;    long long ans=0;    if(x<=mid) ans+=outt(p*2,x,y);    if(y>mid) ans+=outt(p*2+1,x,y);    return ans;}int main(){    scanf("%lld%lld",&n,&m);    for(long long i=1;i<=n;++i){        scanf("%lld",&a[i]);    }    build(1,1,n);    while(m--){        int t;        scanf("%d",&t);        if(t==1){            long long x,y,k;//x,y    +k            scanf("%lld%lld%lld",&x,&y,&k);            change(1,x,y,k);        }        else{            long long x,y;            scanf("%lld%lld",&x,&y);            cout<
        
         <

建议大家把它换成函数，调用方便。。。

还有，这里有个横不好的的习惯

return 0；

优化及时更新哦！！！

转载于:https://www.cnblogs.com/crazily/p/10061495.html

你可能感兴趣的文章