题意：一组数，两个操作，Q为查询l到r区间的和，C为更改l到r区间的值为原来的值加上c。
解法：可以用线段树或树状数组。
线段数成段更新，套模板改了改，万万没想到题目说int不会爆是骗我的………………
线段树代码：
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<limits.h>
#include<time.h>
#include<stdlib.h>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#define LL long long
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define maxn 100005
using namespace std;
LL sum[maxn << 2], col[maxn << 2], point[maxn << 2];
void pushdown(int rt)
{
if(col[rt])
{
col[rt << 1] += col[rt];
col[rt << 1 | 1] += col[rt];
sum[rt << 1] += col[rt] * point[rt << 1];
sum[rt << 1 | 1] += col[rt] * point[rt << 1 | 1];
col[rt] = 0;
}
}
void pushup(int rt)
{
sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}
void build(int l, int r, int rt)
{
col[rt] = 0;
if(l == r)
{
scanf("%I64d", &sum[rt]);
point[rt] = 1;
return ;
}
int m = (l + r) >> 1;
build(lson);
build(rson);
point[rt] = point[rt << 1] + point[rt << 1 | 1];
pushup(rt);
}
void update(int ll, int rr, int c, int l, int r, int rt)
{
if(ll <= l && rr >= r)
{
col[rt] += c;
sum[rt] += (LL)c * point[rt];
return ;
}
pushdown(rt);
int m = (l + r) >> 1;
if(ll <= m)
update(ll, rr, c, lson);
if(rr > m)
update(ll, rr, c, rson);
pushup(rt);
}
LL query(int ll, int rr, int l, int r, int rt)
{
if(ll <= l && rr >= r)
return sum[rt];
pushdown(rt);
int m = (l + r) >> 1;
LL ret = 0;
if(ll <= m)
ret += query(ll, rr, lson);
if(rr > m)
ret += query(ll, rr, rson);
return ret;
}
int main()
{
int n, q;
while(~scanf("%d%d", &n, &q))
{
build(1, n, 1);
for(int i = 0; i < q; i++)
{
char ch[2];
scanf("%s", ch);
if(ch[0] == 'Q')
{
int l, r;
scanf("%d%d", &l, &r);
printf("%I64d
", query(l, r, 1, n, 1));
}
else
{
int l, r, c;
scanf("%d%d%d", &l, &r, &c);
update(l, r, c, 1, n, 1);
}
}
}
return 0;
}
树状数组解法：http://kenby.iteye.com/blog/962159
写的很好……我就不多说了……
树状数组代码：
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<limits.h>
#include<time.h>
#include<stdlib.h>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#define LL long long
using namespace std;
LL sum[100005], c1[100005], c2[100005];
int n;
inline int lowbit(int x)
{
return x & (-x);
}
void update(LL a[], int pos, LL val)
{
for(int i = pos; i <= n; i += lowbit(i))
a[i] += val;
}
LL getsum(LL a[], int pos)
{
LL res = 0;
for(int i = pos; i > 0; i -= lowbit(i))
res += a[i];
return res;
}
int main()
{
int m;
while(~scanf("%d%d", &n, &m))
{
memset(c1, 0, sizeof(c1));
memset(c2, 0, sizeof(c2));
sum[0] = 0;
for(int i = 1; i <= n; i++)
{
LL x;
scanf("%lld", &x);
sum[i] = sum[i - 1] + x;
}
for(int i = 0; i < m; i++)
{
char com[2];
int l, r;
scanf("%s%d%d", com, &l, &r);
if(com[0] == 'Q')
{
LL ans = sum[r] - sum[l - 1];
ans += (r + 1) * getsum(c1, r) - l * getsum(c1, l - 1);
ans -= getsum(c2, r) - getsum(c2, l - 1);
printf("%I64d
", ans);
}
else
{
LL c;
scanf("%I64d", &c);
update(c1, l, c);
update(c1, r + 1, -c);
update(c2, l, c * l);
update(c2, r + 1, -c * (r + 1));
}
}
}
return 0;
}