关键词:
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
Hint
1 #include<iostream> 2 #include<stdio.h> 3 using namespace std; 4 5 const int MAXN = 500005; 6 int a[MAXN]; 7 long long int tree[MAXN*4]; 8 long long int lazy[MAXN*4]; 9 int N,Q; 10 string s; 11 int x , y, z; 12 void push_down(int l ,int r ,int rt) 13 14 int m = (l+r)/2; 15 16 if(lazy[rt]) 17 18 tree[rt*2] += lazy[rt]*(m-l+1); 19 tree[rt*2+1] += lazy[rt]*(r-m); 20 lazy[rt*2] += lazy[rt]; 21 lazy[rt*2+1] += lazy[rt]; 22 lazy[rt] = 0; 23 24 25 void bulid_tree(int l ,int r ,int rt) 26 27 if(l==r) 28 29 tree[rt] = a[l]; 30 return ; 31 32 int m = (l+r)/2; 33 34 bulid_tree(l,m,rt*2); 35 bulid_tree(m+1,r,rt*2+1); 36 tree[rt] = tree[rt*2]+tree[rt*2+1]; 37 38 39 long long int Query(int x ,int y ,int l ,int r ,int rt) 40 41 long long sum = 0 ; 42 if(x<=l&&r<=y) 43 44 return tree[rt]; 45 46 int m = (l+r)/2; 47 push_down(l,r,rt); 48 if(x<=m) 49 50 sum += Query(x,y,l,m,rt*2); 51 52 if(m<y) 53 54 sum += Query(x,y,m+1,r,rt*2+1); 55 56 return sum; 57 58 void Update(int x ,int y ,int k ,int l ,int r ,int rt) 59 60 if(x<=l&&y>=r) 61 62 tree[rt] += k*(r-l+1); 63 lazy[rt] += k; 64 return ; 65 66 push_down(l,r,rt); 67 int m = (l+r)/2; 68 if(x<=m) 69 70 Update(x,y,k,l,m,rt*2); 71 72 if(y>m) 73 74 Update(x,y,k,m+1,r,rt*2+1); 75 76 tree[rt] = tree[rt*2]+tree[rt*2+1]; 77 78 int main() 79 80 scanf("%d%d",&N,&Q); 81 for(int i = 1 ; i <= N;i++) 82 83 scanf("%d",&a[i]); 84 85 bulid_tree(1,N,1); 86 while(Q--) 87 88 cin>>s; 89 if(s[0]==‘Q‘) 90 91 scanf("%d%d",&x,&y); 92 printf("%lld\n",Query(x,y,1,N,1)); 93 94 95 else 96 if(s[0]==‘C‘) 97 98 scanf("%d%d%d",&x,&y,&z); 99 Update(x,y,z,1,N,1); 100 101 102 return 0; 103
poj3468(代码片段)
POJ3468题目链接POJ3468题目概述给出一个包含有(N)个元素的数组(a),然后是(m)次操作,操作有以下两种类型:Qxy((xleqy))计算(sum_i=x^ya[i])Cxyd((xleqy))将区间([x,y])内部的每一个(a[i])加上(d).对于第一种查询操作输出对应的结果,数据规模:[1leqN,M... 查看详情
poj3468asimpleproblemwithintegers
DescriptionYouhaveNintegers,A1,A2,...,AN.Youneedtodealwithtwokindsofoperations.Onetypeofoperationistoaddsomegivennumbertoeachnumberinagiveninterval.Theotheristoaskforthesumofnumbersinagiveninterval.In 查看详情
线段树poj3468
DescriptionYouhaveNintegers,A1,A2,...,AN.Youneedtodealwithtwokindsofoperations.Onetypeofoperationistoaddsomegivennumbertoeachnumberinagiveninterval.Theotheristoaskforthesumofnumbersinagiveninterval.In 查看详情
poj-3468asimpleproblemwithintegers
YouhaveNintegers,A1,A2,...,AN.Youneedtodealwithtwokindsofoperations.Onetypeofoperationistoaddsomegivennumbertoeachnumberinagiveninterval.Theotheristoaskforthesumofnumbersinagiveninterval.InputThefirst 查看详情
[poj3468]asimpleproblemwithintegers
DescriptionYouhaveNintegers,A1,A2,...,AN.Youneedtodealwithtwokindsofoperations.Onetypeofoperationistoaddsomegivennumbertoeachnumberinagiveninterval.Theotheristoaskforthesumofnumbersinagiveninterval.In 查看详情
poj3468asimpleproblemwithintegers分块
题解:分块解题报告:是个板子题呢qwq先占坑,今天会写,over 查看详情
poj3468(线段树)(代码片段)
题目链接:http://poj.org/problem?id=3468Youhave N integers, A1, A2,..., AN.Youneedtodealwithtwokindsofoperations.Onetypeofoperationistoaddsomegivennumbertoeachnumberinagiveninterva 查看详情
poj3468
成段更新这题数据很大,注意要__int64。其他差不多,/*poj3468注意标签的作用,注意是+=,才能传递正确的值下去,一定要注意到这定,标签的值*/#include<stdio.h>#include<stdlib.h>#defineMAX150000usingnamespacestd;typedefstructnode{ints,e;__i... 查看详情
poj3468asimpleproblemwithintegers
题目链接:http://poj.org/problem?id=3468区间更新,区间求和。1#include<cstdio>2#include<algorithm>3usingnamespacestd;4#definelllonglong5#definelsonl,m,rt<<16#definersonm+1,r,rt<<1|17constintma 查看详情
poj3468asimpleproblemwithintegers
ASimpleProblemwithIntegersTimeLimit:5000MS MemoryLimit:131072KTotalSubmissions:110999 Accepted:34570CaseTimeLimit:2000MSDescriptionYouhaveNintegers,A1,A2,...,AN.Youneedtodealwithtwokindsofop 查看详情
asimpleproblemwithintegers~poj-3468
Youhave N integers, A1, A2,..., AN.Youneedtodealwithtwokindsofoperations.Onetypeofoperationistoaddsomegivennumbertoeachnumberinagiveninterval.Theotheristoaskforthesumofnumbers 查看详情
poj3468asimpleproblemwithintegers
ASimpleProblemwithIntegersTimeLimit: 5000MS MemoryLimit: 131072KTotalSubmissions: 110087 Accepted: 34277CaseTimeLimit: 2000MSDescriptionYouhave N integers, 查看详情
poj3468asimpleproblemwithintegers——线段树区间修改
题目链接:https://vjudge.net/problem/POJ-3468 Youhave N integers, A1, A2,..., AN.Youneedtodealwithtwokindsofoperations.Onetypeofoperationistoaddsomegivennumbertoeachnumberinag 查看详情
poj3468asimpleproblemwithintegers(线段树单点更新+区间求和)
题目链接:http://poj.org/problem?id=3468题意:单点更新,区间求和。题解:裸题1//POJ3468ASimpleProblemwithIntegers2//单点更新区间求和3#include<cstdio>4#include<iostream>5#include<algorithm>6usingnamespacestd;78typed 查看详情
poj3468asimpleproblemwithintegers(线段树+区间更新+区间求和)
题目链接:id=3468http://">http://poj.org/problem?id=3468ASimpleProblemwithIntegersTimeLimit: 5000MS MemoryLimit: 131072KTotalSubmissions: 83959 Accepted: 25989CaseTimeLimit:&n 查看详情
poj3468asimpleproblemwithintegers
TimeLimit: 5000MS MemoryLimit: 131072KTotalSubmissions: 106771 Accepted: 33308CaseTimeLimit: 2000MSDescriptionYouhave N integers, A1, A2,...,&nbs 查看详情
poj3468asimpleproblemwithintegers(代码片段)
Youhave N integers, A1, A2,..., AN.Youneedtodealwithtwokindsofoperations.Onetypeofoperationistoaddsomegivennumbertoeachnumberinagiveninterval.Theotheristoaskforthesumofnumbers 查看详情
poj3468
TLE+WA了无数次,发现了不少毛病,做个记录先1#include<iostream>2#include<cstring>3#include<cstdio>4#include<cstdlib>5#include<algorithm>6#include<cmath>7usingnamespacestd;8910#definels 查看详情