A Simple Problem with Integers
| Time Limit: 5000MS | Memory Limit: 131072K | |
| Total Submissions: 60712 | Accepted: 18509 | |
| 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
Hint
The sums may exceed the range of 32-bit integers.
题目大意：
给定Q (1 ≤ Q ≤ 100,000)个数A1,A2… AQ,
以及可能多次进行的两个操作:
1) 对某个区间Ai … Aj的每个数都加n(n可变）
2) 求某个区间Ai … Aj的数的和
思路：
很明显的线段树题，但是按普通方法对Ai … Aj的数都更新到叶子节点，很容易超时，对此，我们可以用一个暂时变量lnc，用来存储操作1)Ai … Aj每个数加的n。
如果增加时，如果要加的区间正好覆盖一个节点(区间)，则增加其节点的Inc值，不再往下走，否则要更新nSum(加上本次增量),再将增量往下传。这样更新的复杂度就是O(log(n))。
在查询时，如果待查区间不是正好覆盖一个节点，就将节点的Inc往下带，然后将Inc代表的所有增量累加到nSum上后将Inc清0，接下来再往下查询。 Inc往下带的过程也是区间分解的过程，复杂度也是O(log(n))。
版本一：北大ACM暑期培训时写的代码(含结构体、左右节点指针)
# include<iostream>
using namespace std;
struct CNode
{
int L,R;
CNode *pLeft, *pRight;
long long nSum;
long long lnc;
};
CNode Tree[200010];
int nCount = 0;//当前线段树建立了多少个节点
int Mid(CNode *pRoot)
{
return (pRoot->L + pRoot->R)/2;
}
void BuildTree(CNode *pRoot, int L, int R)
{
pRoot->L = L;
pRoot->R = R;
pRoot->nSum = 0;
pRoot->lnc = 0;
if(L==R)
return;
nCount++;
pRoot->pLeft = Tree + nCount;
nCount++;
pRoot->pRight = Tree + nCount;
BuildTree(pRoot->pLeft,L,(L+R)/2);
BuildTree(pRoot->pRight,(L+R)/2+1,R);
}
void Insert(CNode *pRoot,int i,int v)
{
if(pRoot->L == i && pRoot->R == i)
{
pRoot->nSum = v;
return;
}
pRoot->nSum += v;
if(i <= Mid(pRoot))
Insert(pRoot->pLeft,i,v);
else
Insert(pRoot->pRight,i,v);
}
void Add(CNode *pRoot,int a,int b,long long c)
{
if(pRoot->L ==a && pRoot->R == b)
{
pRoot->lnc += c;
return;
}
pRoot->nSum += c*(b-a+1);
if(b <= (pRoot->L+pRoot->R)/2)
Add(pRoot->pLeft,a,b,c);
else if(a >= (pRoot->L+pRoot->R)/2+1)
Add(pRoot->pRight,a,b,c);
else
{
Add(pRoot->pLeft,a,(pRoot->L+pRoot->R)/2,c);
Add(pRoot->pRight,(pRoot->L+pRoot->R)/2+1,b,c);
}
}
long long QuerynSum(CNode *pRoot,int a,int b)
{
if(pRoot->L==a && pRoot->R==b)
{
return pRoot->nSum + (pRoot->R - pRoot->L + 1)*pRoot->lnc;
}
pRoot->nSum += (pRoot->R - pRoot->L + 1)*pRoot->lnc;
Add(pRoot->pLeft,pRoot->L,Mid(pRoot),pRoot->lnc);
Add(pRoot->pRight,Mid(pRoot)+1,pRoot->R,pRoot->lnc);
pRoot->lnc = 0;
if(b <= Mid(pRoot))
return QuerynSum(pRoot->pLeft,a,b);
else if(a >= Mid(pRoot)+1)
return QuerynSum(pRoot->pRight,a,b);
else
{
return QuerynSum(pRoot->pLeft,a,Mid(pRoot)) + QuerynSum(pRoot->pRight,Mid(pRoot)+1,b);
}
}
int main()
{
int n,q,a,b,c;
char cmd[3];
scanf("%d%d",&n,&q);
nCount = 0;
BuildTree(Tree,1,n);
for(int i = 1; i <= n; i++)
{
scanf("%d",&a);
Insert(Tree,i,a);
}
for(int i = 0; i < q; i++)
{
scanf("%s",cmd);
if(cmd[0]=='C')
{
scanf("%d%d%d",&a,&b,&c);
Add(Tree,a,b,c);
}
else
{
scanf("%d%d",&a,&b);
printf("%I64d\n",QuerynSum(Tree,a,b));
}
}
return 0;
}
版本二：自己参考版本一修改(带结构体、不带左右节点指针)
# include<iostream>
using namespace std;
const int MAXN = 100000;
struct Node
{
int L,R;
__int64 sumV,lnc;
int Mid()
{
return (L+R)/2;
}
};
Node tree[MAXN*4+10];
void BuildTree(int root, int L, int R)
{
tree[root].L = L;
tree[root].R = R;
tree[root].sumV = 0;
tree[root].lnc = 0;
if(L==R)
return;
BuildTree(root*2+1,L,(L+R)/2);
BuildTree(root*2+2,(L+R)/2+1,R);
}
void InsertTree(int root, int i, int v)
{
if(tree[root].L == i && tree[root].R == i)
{
tree[root].sumV = v;
return;
}
tree[root].sumV += v;
if(i <= tree[root].Mid())
InsertTree(root*2+1,i,v);
else
InsertTree(root*2+2,i,v);
}
void Add(int root, int a, int b,__int64 c)
{
if(tree[root].L==a && tree[root].R==b)
{
tree[root].lnc += c;
return;
}
tree[root].sumV += c*(b-a+1);
if(b <= tree[root].Mid())
Add(root*2+1,a,b,c);
else if(a >= tree[root].Mid()+1)
Add(root*2+2,a,b,c);
else
{
Add(root*2+1,a,tree[root].Mid(),c);
Add(root*2+2,tree[root].Mid()+1,b,c);
}
}
__int64 QuerysumV(int root, int a, int b)
{
if(tree[root].L==a && tree[root].R==b)
{
return tree[root].sumV + (tree[root].R-tree[root].L+1)*tree[root].lnc;
}
tree[root].sumV += (tree[root].R-tree[root].L+1)*tree[root].lnc;
Add(root*2+1,tree[root].L,tree[root].Mid(),tree[root].lnc);
Add(root*2+2,tree[root].Mid()+1,tree[root].R,tree[root].lnc);
tree[root].lnc = 0;
if(b <= tree[root].Mid())
return QuerysumV(root*2+1,a,b);
else if(a >= tree[root].Mid()+1)
return QuerysumV(root*2+2,a,b);
else
{
return QuerysumV(root*2+1,a,tree[root].Mid()) + QuerysumV(root*2+2,tree[root].Mid()+1,b);
}
}
int main()
{
int n,q,a,b,c;
char cmd[10];
scanf("%d%d",&n,&q);
int i;
BuildTree(0,1,n);
for(i = 1; i <= n; i++)
{
scanf("%d",&a);
InsertTree(0,i,a);
}
for(i = 0; i < q; i++)
{
scanf("%s",cmd);
if(cmd[0]=='C')
{
scanf("%d%d%d",&a,&b,&c);
Add(0,a,b,c);
}
else
{
scanf("%d%d",&a,&b);
printf("%I64d\n",QuerysumV(0,a,b));
}
}
return 0;
}
版本三：参考HH大神模板写的(不带结构体、不带左右节点指针)
# include<stdio.h>
# include<iostream>
# include<algorithm>
using namespace std;
const int MAXN = 100010;
__int64 sum[MAXN<<2],add[MAXN<<2];
void pushup(int root)
{
sum[root] = sum[root<<1] + sum[root<<1|1];
}
void pushdown(int root,int len)
{
if(add[root])
{
add[root<<1] += add[root];
add[root<<1|1] += add[root];
sum[root<<1] += (add[root]*(len-(len>>1)));
sum[root<<1|1] += (add[root]*(len>>1));
add[root] = 0;
}
}
void build(int root,int L,int R)
{
add[root] = 0;
if(L == R)
{
scanf("%I64d", &sum[root]);
return;
}
int mid = (L+R)>>1;
build(root<<1,L,mid);
build(root<<1|1,mid+1,R);
pushup(root);
}
void updata(int root,int L,int R,int s,int e,__int64 v)
{
if(s<=L && e>=R)
{
add[root] += v;
sum[root] += (__int64)(v*(R-L+1));
return;
}
pushdown(root,R-L+1);
int mid = (L+R)>>1;
if(s <= mid)
updata(root<<1,L,mid,s,e,v);
if(e > mid)
updata(root<<1|1,mid+1,R,s,e,v);
pushup(root);
}
__int64 query(int root,int L,int R,int s,int e)
{
if(s<=L && e>=R)
return sum[root];
pushdown(root,R-L+1);
__int64 res = 0;
int mid = (L+R)>>1;
if(s <= mid)
res += query(root<<1,L,mid,s,e);
if(e > mid)
res += query(root<<1|1,mid+1,R,s,e);
return res;
}
int main()
{
int N,Q,s,e,a,b;
__int64 v;
char cmd[10];
scanf("%d%d", &N,&Q);
build(1,1,N);
while(Q--)
{
scanf("%s",cmd);
if(cmd[0]=='Q')
{
scanf("%d%d",&s,&e);
printf("%I64d\n",query(1,1,N,s,e));
}
else if(cmd[0]=='C')
{
scanf("%d%d%I64d",&a,&b,&v);
updata(1,1,N,a,b,v);
}
}
return 0;
}