首页 > 代码库 > poj 3468 A Simple Problem with Integers
poj 3468 A Simple Problem with Integers
A Simple Problem with Integers
Time Limit: 5000MS | Memory Limit: 131072K | |
Total Submissions: 60604 | Accepted: 18470 | |
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 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
线段树(区间求和,更新线段)
#include<stdio.h> #include<iostream> #include<algorithm> using namespace std; #define MAX_N 100001 __int64 sum = 0; __int64 num[MAX_N]; struct node { int left; int right; __int64 count; //表示该节点的总个数 __int64 data; //表示增量的那个数 }N[4*MAX_N]; void CreateTree(int i,int a,int b) { N[i].left = a; N[i].right = b; N[i].data = http://www.mamicode.com/0; >
TML代码:
真心苦逼啊。。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int max(int a,int b) { return (a>b?a:b); } int a[200000]; struct Node { int left,right; int t; }node[4*200000]; void MakeTree(int l,int r,int i) { node[i].left=l; node[i].right=r; if(l==r) { node[i].t=a[l]; return ; } int mid=(l+r)/2; MakeTree(l,mid,2*i); MakeTree(mid+1,r,2*i+1); node[i].t=node[2*i].t+node[2*i+1].t; } void UpdateTree(int i,int x,int k) { int l=node[i].left; int r=node[i].right; int mid=(l+r)/2; if(x==l&&x==r) { node[i].t+=k; return ; } if(x>mid) UpdateTree(2*i+1,x,k); else UpdateTree(2*i,x,k); node[i].t=node[2*i].t+node[2*i+1].t; } int QueryTree(int x,int y,int i) { if(node[i].left==x && node[i].right==y) return node[i].t; int m=(node[i].left+node[i].right)/2; if(x>m) return QueryTree(x,y,2*i+1); else if(y<=m) return QueryTree(x,y,2*i); else return QueryTree(x,m,2*i)+QueryTree(m+1,y,2*i+1); } int main () { int T,n,m; int i,j,x,y,k; char c[10]; while(~scanf("%d%d",&n,&m)) { for(i=1;i<=n;i++) scanf("%d",&a[i]); MakeTree(1,n,1); for(j=1;j<=m;j++) { scanf("%s%d%d",c,&x,&y); if(c[0]=='C') { scanf("%d",&k); for(i=x;i<=y;i++) { UpdateTree(1,i,k); } } else cout<<QueryTree(x,y,1)<<endl; } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。