kuangbin专题七 POJ3468 A Simple Problem with Integers (线段
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. 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 1 #include <iostream> 2 #include <stdio.h> 3 #include <math.h> 4 #include <string.h> 5 #include <stdlib.h> 6 #include <string> 7 #include <vector> 8 #include <set> 9 #include <map> 10 #include <queue> 11 #include <algorithm> 12 #include <sstream> 13 #include <stack> 14 using namespace std; 15 #define FO freopen("in.txt","r",stdin); 16 #define rep(i,a,n) for (int i=a;i<n;i++) 17 #define per(i,n) for (int i=n-1;i>=a;i--) 18 #define pb push_back 19 #define mp make_pair 20 #define all(x) (x).begin(),(x).end() 21 #define fi first 22 #define se second 23 #define SZ(x) ((int)(x).size()) 24 #define debug(x) cout << "&&" << x << "&&" << endl; 25 #define lowbit(x) (x&-x) 26 #define mem(a,b) memset(a,b,sizeof(a)); 27 typedef vector<int> VI; 28 typedef long long ll; 29 typedef pair<int,int> PII; 30 const ll mod=1000000007; 31 const int inf = 0x3f3f3f3f; 32 ll powmod(ll a,ll b) {ll res=1;a%=mod;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} 33 ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;} 34 //head 35 36 //区间修改 区间查询 37 const int maxx=100010; 38 ll sum[maxx<<2],lazy[maxx<<2],val; 39 int n,q; 40 41 void Pushup(int rt) { 42 sum[rt]=sum[rt<<1]+sum[rt<<1|1]; 43 } 44 45 void build(int rt,int L,int R) { 46 lazy[rt]=0; 47 if(L==R) { 48 scanf("%lld",&sum[rt]); 49 return; 50 } 51 int mid=(L+R)>>1; 52 build(rt<<1,L,mid); 53 build(rt<<1|1,mid+1,R); 54 Pushup(rt); 55 } 56 57 void Pushdown(int rt,int x) { 58 if(lazy[rt]) { 59 lazy[rt<<1]+=lazy[rt]; 60 lazy[rt<<1|1]+=lazy[rt]; 61 sum[rt<<1]+=(x-(x>>1))*lazy[rt];//左子树加左边一半的值 62 sum[rt<<1|1]+=(x>>1)*lazy[rt];//右子树同理 63 lazy[rt]=0;//清空 64 } 65 } 66 67 void Updata(int rt,int R,int l,int r) { 68 if(L>=l&&R<=r) { 69 lazy[rt]+=val;//累加标记 70 sum[rt]+=(R-L+1)*val;//更新值 71 return; 72 } 73 int mid=(L+R)>>1; 74 Pushdown(rt,R-L+1);//这里多了一个参数 L R区间的个数 75 if(l<=mid) Updata(rt<<1,mid,l,r); 76 if(r>mid) Updata(rt<<1|1,R,r); 77 Pushup(rt); 78 } 79 80 ll Query(int rt,int r) { 81 if(L>=l&&R<=r) 82 return sum[rt]; 83 ll ans=0; 84 int mid=(L+R)>>1; 85 Pushdown(rt,R-L+1); 86 if(l<=mid) ans+=Query(rt<<1,r); 87 if(r>mid) ans+=Query(rt<<1|1,r); 88 Pushup(rt); 89 return ans; 90 } 91 92 93 int main() { 94 while(~scanf("%d%d",&n,&q)) { 95 build(1,1,n); 96 char s[3]; 97 while(q--) { 98 scanf("%s",s); 99 int l,r; 100 if(s[0]==‘Q‘) { 101 scanf("%d%d",&l,&r); 102 printf("%lldn",Query(1,n,r)); 103 } else { 104 scanf("%d%d%lld",&r,&val); 105 Updata(1,r); 106 } 107 } 108 } 109 } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |