P3372 【模板】线段树 1
题目描述
如题，已知一个数列，你需要进行下面两种操作：
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 5 1 5 4 2 3 2 2 4 1 2 3 2 2 3 4 1 1 5 1 2 1 4
输出样例#1：
11 8 20
说明
时空限制：1000ms,128M
数据规模：
对于30%的数据：N<=8，M<=10
对于70%的数据：N<=1000，M<=10000
对于100%的数据：N<=100000，M<=100000
（数据已经过加强^_^，保证在int64/long long数据范围内）
样例说明：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> 6 #define max(a,b) ((a) > (b) ? (a) : (b)) 7 #define min(a,b) ((a) > (b) ? (b) : (a)) 8 #define lowbit(a) (a & (-(a))) 9 const int INF = 0x3f3f3f3f; 10 const int MAXN = 100000 + 10; 11 const int MAXM = 100000 + 10; 12 inline void read(long long &x) 13 { 14 x = 0;char ch = getchar();char c = ch; 15 while(ch > '9' || ch < '0')c = ch, ch = getchar(); 16 while(ch >= '0' && ch <= '9')x = x * 10 + ch - '0',ch = getchar(); 17 if(c == '-')x = -x; 18 } 19 20 long long stdata[MAXN << 2]; 21 long long stlazy[MAXN << 2]; 22 long long n,m; 23 24 25 void modify1(long long p, long long k, long long o = 1,long long l = 1,long long r = n) 26 { 27 if(l == r == p) 28 { 29 stdata[o] += k; 30 return; 31 } 32 long long mid = (l + r) >> 1; 33 if(p <= mid) modify1(p, k, o << 1, l, mid); 34 else modify1(p, k, o << 1 | 1, mid + 1, r); 35 stdata[o] = stdata[o << 1] + stdata[o << 1 | 1]; 36 return ; 37 } 38 39 40 void modify2(long long ll, long long rr, long long k, long long o = 1, long long l = 1, long long r = n) 41 { 42 if(l >= ll && r <= rr) 43 { 44 stlazy[o] += k; 45 stdata[o] += (r - l + 1) * k; 46 return; 47 } 48 if(ll <= l && rr <= r && rr >= l) 49 { 50 stdata[o] += k * (rr - l + 1); 51 } 52 else if(ll >= l && rr <= r) 53 { 54 stdata[o] += k * (rr - ll + 1); 55 } 56 else if(ll >= l && ll <= r && rr >= r) 57 { 58 stdata[o] += k * (r - ll + 1); 59 } 60 long long mid = (l + r) >> 1; 61 if(ll <= mid)modify2(ll, rr, k, o << 1, l, mid); 62 if(rr > mid) modify2(ll, rr, k, o << 1 | 1, mid + 1, r); 63 } 64 65 long long query(long long ll, long long rr, long long o = 1, long long l = 1, long long r = n) 66 { 67 long long mid = (l + r) >> 1; 68 if(ll <= l && rr >= r) 69 { 70 return stdata[o]; 71 } 72 if(stlazy[o]) 73 { 74 stlazy[o << 1] += stlazy[o]; 75 stlazy[o << 1 | 1] += stlazy[o]; 76 stdata[o << 1] += (mid - l + 1) * stlazy[o]; 77 stdata[o << 1 | 1] += (r - mid) * stlazy[o]; 78 stlazy[o] = 0; 79 } 80 long long ans = 0; 81 if(ll <= mid)ans += query(ll, rr, o << 1, l, mid); 82 if(rr > mid) ans += query(ll, rr, o << 1 | 1, mid + 1, r); 83 stdata[o] = stdata[o << 1] + stdata[o << 1 | 1]; 84 return ans; 85 } 86 87 long long num[MAXN]; 88 long long cnt; 89 void build(long long o = 1,long long l = 1,long long r = n) 90 { 91 if(l == r) 92 { 93 stdata[o] = num[++cnt]; 94 return; 95 } 96 long long mid = (l + r) >> 1; 97 build(o << 1, l, mid); 98 build(o << 1 | 1, mid + 1, r); 99 stdata[o] = stdata[o << 1] + stdata[o << 1 | 1]; 100 } 101 102 long long tmp1,tmp2,tmp3,tmp4; 103 104 int main() 105 { 106 read(n);read(m); 107 for(long long i = 1;i <= n;i ++) 108 { 109 read(num[i]); 110 } 111 build(); 112 for(long long i = 1;i <= m;i ++) 113 { 114 read(tmp1); 115 switch(tmp1) 116 { 117 case 1: 118 { 119 read(tmp1);read(tmp2);read(tmp3); 120 modify2(tmp1, tmp2, tmp3); 121 break; 122 } 123 case 2: 124 { 125 read(tmp1);read(tmp2); 126 printf("%lld ", query(tmp1, tmp2)); 127 } 128 } 129 } 130 return 0; 131 }