首页 > 代码库 > poj3468 A Simple Problem with Integers 线段树区间更新
poj3468 A Simple Problem with Integers 线段树区间更新
A Simple Problem with Integers
| Time Limit: 5000MS | Memory Limit: 131072K | |
| Total Submissions: 97722 | Accepted: 30543 | |
| Case Time Limit: 2000MS | ||
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 a b c" means adding c to each of Aa, Aa+1, ... , Ab. -10000 ≤ c ≤ 10000.
"Q a b" 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 51 2 3 4 5 6 7 8 9 10Q 4 4Q 1 10Q 2 4C 3 6 3Q 2 4
Sample Output
455915
Hint
The sums may exceed the range of 32-bit integers.
1 #include <iostream> 2 #include <sstream> 3 #include <fstream> 4 #include <string> 5 #include <vector> 6 #include <deque> 7 #include <queue> 8 #include <stack> 9 #include <set> 10 #include <map> 11 #include <algorithm> 12 #include <functional> 13 #include <utility> 14 #include <bitset> 15 #include <cmath> 16 #include <cstdlib> 17 #include <ctime> 18 #include <cstdio> 19 #include <cstring> 20 #define FOR(i, a, b) for(int i = (a); i <= (b); i++) 21 #define RE(i, n) FOR(i, 1, n) 22 #define FORP(i, a, b) for(int i = (a); i >= (b); i--) 23 #define REP(i, n) for(int i = 0; i <(n); ++i) 24 #define SZ(x) ((int)(x).size ) 25 #define ALL(x) (x).begin(), (x.end()) 26 #define MSET(a, x) memset(a, x, sizeof(a)) 27 using namespace std; 28 29 30 typedef long long int ll; 31 typedef pair<int, int> P; 32 int read() { 33 int x=0,f=1; 34 char ch=getchar(); 35 while(ch<‘0‘||ch>‘9‘) { 36 if(ch==‘-‘)f=-1; 37 ch=getchar(); 38 } 39 while(ch>=‘0‘&&ch<=‘9‘) { 40 x=x*10+ch-‘0‘; 41 ch=getchar(); 42 } 43 return x*f; 44 } 45 const double pi=3.14159265358979323846264338327950288L; 46 const double eps=1e-6; 47 const int mod = 1e9 + 7; 48 const int INF = 0x3f3f3f3f; 49 const int MAXN = 100003; 50 const int xi[] = {0, 0, 1, -1}; 51 const int yi[] = {1, -1, 0, 0}; 52 53 int N, T; 54 struct seg { 55 ll sum, add; 56 } a[MAXN<<2]; 57 ll b[MAXN]; 58 59 void pushdown(int k, int m){ 60 if(a[k].add){ 61 a[k<<1].add += a[k].add; 62 a[k<<1|1].add += a[k].add; 63 a[k<<1].sum += a[k].add*(m - (m>>1)); 64 a[k<<1|1].sum += a[k].add*(m>>1); 65 a[k].add = 0; 66 } 67 } 68 void build(int k, int l, int r) { 69 a[k].add = 0; 70 if(r == l) { 71 a[k].sum = b[l]; 72 return; 73 } 74 int m = (l+r)>>1; 75 build(k<<1, l, m); 76 build(k<<1|1, m+1, r); 77 a[k].sum = a[k<<1].sum + a[k<<1|1].sum; 78 } 79 void update(int k, int x, int add, int l, int r) { 80 if(l == r ) { 81 a[k].sum += add; 82 return; 83 } 84 int m = (l + r)>>1; 85 if(x <= m) { 86 update(k<<1, x, add, l, m); 87 } else update(k<<1|1, x, add, m+1, r); 88 a[k].sum = a[k<<1].sum + a[k<<1|1].sum; 89 } 90 void change(int k, int l, int r, int ca, int cb, ll c) { 91 if(ca <= l && cb >= r){ 92 a[k].add += c; 93 a[k].sum += c*(r - l + 1); 94 return; 95 } 96 pushdown(k, r-l+1); 97 int m = (l+r) >>1; 98 if(ca <= m) change(k<<1, l, m, ca, cb, c); 99 if(cb > m) change(k <<1|1, m+1, r, ca, cb, c);100 a[k].sum = a[k<<1].sum + a[k<<1|1].sum;101 }102 ll query(int k, int l, int r, int qa, int qb) {103 if(qa <= l && qb >= r) return a[k].sum;104 pushdown(k, r-l+1);105 int m = (l+r) >>1;106 ll ans = 0;107 if(qa <= m) ans += query(k<<1, l, m, qa, qb);108 if(qb > m) ans += query(k<<1|1, m+1, r, qa, qb);109 return ans;110 }111 112 int main() {113 //freopen("in.txt", "r", stdin);114 int n, Q;115 scanf("%d%d", &n, &Q);116 for(int i = 1; i <= n; i++) {117 scanf("%I64d", &b[i]);118 }119 build(1, 1, n);120 char s[10];121 int ca, cb;122 while(Q--) {123 scanf("%s%d%d", s, &ca, &cb);124 if(s[0] == ‘Q‘) {125 printf("%I64d\n", query(1, 1, n, ca, cb));126 }127 else {128 ll add;129 scanf("%I64d", &add);130 // printf("SSS\n");131 change(1, 1, n, ca, cb, add);132 // printf("SSS\n");133 }134 }135 136 return 0;137 }
poj3468 A Simple Problem with Integers 线段树区间更新
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。