rockdu
题目描述
如题，已知一个数列，你需要进行下面两种操作：
1.将某区间每一个数加上x
2.求出某区间每一个数的和
输入输出格式
输入格式：
第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。
第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。
接下来M行每行包含3或4个整数，表示一个操作，具体如下：
操作1： 格式：1 x y k 含义：将区间[x,y]内每个数加上k
操作2： 格式：2 x y 含义：输出区间[x,y]内每个数的和
输出格式：
输出包含若干行整数，即为所有操作2的结果。
输入输出样例
说明
时空限制：1000ms,128M
数据规模：
对于30%的数据：N<=8，M<=10
对于70%的数据：N<=1000，M<=10000
对于100%的数据：N<=100000，M<=100000
（数据已经过加强^_^，保证在int64/long long数据范围内）
样例说明：
ZKW的确是个好东西，就是写起来总是写不对，还需要多加练习啊。这是一道zkw写的板子，具体可以参考这一篇博客：=w= <----- 这篇博客。有几点需要注意：1、计算层数一只统计到<n + 3，因为有一个0，一个n + 1方便查询。2、pushdown比差分好写得多，常数也不大，可以考虑保留递归pushdown而不差分。 164ms:
#include<cstdio>
#define LL long long
using namespace std;
const int maxn = 1e6 + 5;
int data[maxn];
LL tree[maxn << 2], fre[maxn << 2];
int bit, n, m, o, a, dt, b, size[maxn << 2];
inline void push_up(const int &rt) {
tree[rt] = tree[rt << 1 | 1] + tree[rt << 1];
}
inline void build(int n) {
register int &b = bit;
for(b = 1; b < n + 3; b <<= 1);
for(register int i = 1; i <= n; ++i) tree[i + b] = data[i];
for(register int i = b; i < (b << 1); ++i) size[i] = 1;
for(register int i = b - 1; i; --i)
size[i] = size[i << 1] + size[i << 1 | 1], push_up(i);
}
int len, lazy;
void push_down(int rt) {
if(rt != 1) push_down(rt >> 1);
if(!fre[rt]) return;
len = size[rt << 1];
lazy = fre[rt];
tree[rt + rt + 1] += lazy * len;
tree[rt << 1] += lazy * len;
fre[rt << 1] += lazy;
fre[rt + rt + 1] += lazy;
fre[rt] = 0;
}
inline LL query(register int l, register int r) {
LL ans = 0;
l = bit + l - 1, r = bit + r + 1;
push_down(l >> 1), push_down(r >> 1);
for(; l ^ r ^ 1; l >>= 1, r >>= 1) {
if(~l & 1) ans += tree[l ^ 1];
if(r & 1) ans += tree[r ^ 1];
}
return ans;
}
inline void add(register int l, register int r, LL dt) {
l = bit + l - 1, r = bit + r + 1;
push_down(l >> 1), push_down(r >> 1);
for(; l ^ r ^ 1; push_up(l >>= 1), push_up(r >>= 1)){
if(~l & 1) fre[l ^ 1] += dt, tree[l ^ 1] += dt * size[l];
if(r & 1) fre[r ^ 1] += dt, tree[r ^ 1] += dt * size[r];
}
for(l >>= 1; l; l >>= 1) push_up(l);
}
int main() {
scanf("%d%d", &n, &m);
for(register int i = 1; i <= n; ++i) scanf("%d", &data[i]);
build(n);
while(m--) {
scanf("%d", &o);
if(o == 1) scanf("%d%d%d", &a, &b, &dt), add(a, b, dt);
else scanf("%d%d", &a, &b), printf("%lld\n", query(a, b));
}
return 0;
} 突然发现分块也是一个好东西，要注意块的大小最好手动调整sqrt（n）不一定是最优的 824ms。
#include<cstdio>
#include<cmath>
#include<algorithm>
#define LL long long
using namespace std;
const int maxn = 5e5 + 5;
const int Bsize = 200;
LL a[maxn], sum[maxn], lazy[maxn], z;
int Bnum, n, m, op, x, y;
void push_down(int x) {
if(!lazy[x]) return;
int ed = min(n, Bsize * (x + 1)), st = Bsize * x;
for(register int i = st; i < ed; ++i)
a[i] += lazy[x];
lazy[x] = 0;
}
LL query(int l, int r) {
LL ans = 0;
--l, --r;
int bl = l / Bsize, br = r / Bsize;
if(bl == br) {
push_down(bl);
for(register int i = l; i <= r; ++i)
ans += a[i];
return ans;
}
for(register int i = bl + 1; i <= br - 1; ++i)
ans += sum[i];
push_down(bl), push_down(br);
for(register int i = l; i <= (bl + 1) * Bsize - 1; ++i)
ans += a[i];
for(register int i = br * Bsize; i <= r; ++i)
ans += a[i];
return ans;
}
void add(int l, int r, LL w) {
--l, --r;
int bl = l / Bsize, br = r / Bsize;
if(bl == br) {
push_down(bl);
for(register int i = l; i <= r; ++i)
a[i] += w;
sum[bl] += w * (r - l + 1);
return ;
}
for(register int i = bl + 1; i <= br - 1; ++i)
sum[i] += w * Bsize, lazy[i] += w;
push_down(bl), push_down(br);
for(register int i = l; i <= (bl + 1) * Bsize - 1; ++i)
a[i] += w, sum[bl] += w;
for(register int i = br * Bsize; i <= r; ++i)
a[i] += w, sum[br] += w;
}
int main() {
scanf("%d%d", &n, &m);
for(register int i = 0; i < n; ++i) scanf("%lld", &a[i]);
Bnum = (n - 1) / Bsize + 1;
for(register int i = 0; i < Bnum; ++i) {
int pre = i * Bsize;
for(register int j = 0; j < Bsize; ++j)
sum[i] += a[pre + j];
}
for(register int i = 1; i <= m; ++i) {
scanf("%d", &op);
if(op == 2) {
scanf("%d%d", &x, &y);
printf("%lld\n", query(x, y));
} else {
scanf("%d%d%lld", &x, &y, &z);
add(x, y, z);
}
}
return 0;
}其实Splay也是一个好东西，虽然说它的log是假的，但是功能还是挺真的。1936ms:
#include<cstdio>
#include<cmath>
#include<algorithm>
#define LL long long
using namespace std;
const int maxn = 5e5 + 5;
const int Bsize = 200;
LL a[maxn], sum[maxn], lazy[maxn], z;
int Bnum, n, m, op, x, y;
void push_down(int x) {
if(!lazy[x]) return;
int ed = min(n, Bsize * (x + 1)), st = Bsize * x;
for(register int i = st; i < ed; ++i)
a[i] += lazy[x];
lazy[x] = 0;
}
LL query(int l, int r) {
LL ans = 0;
--l, --r;
int bl = l / Bsize, br = r / Bsize;
if(bl == br) {
push_down(bl);
for(register int i = l; i <= r; ++i)
ans += a[i];
return ans;
}
for(register int i = bl + 1; i <= br - 1; ++i)
ans += sum[i];
push_down(bl), push_down(br);
for(register int i = l; i <= (bl + 1) * Bsize - 1; ++i)
ans += a[i];
for(register int i = br * Bsize; i <= r; ++i)
ans += a[i];
return ans;
}
void add(int l, int r, LL w) {
--l, --r;
int bl = l / Bsize, br = r / Bsize;
if(bl == br) {
push_down(bl);
for(register int i = l; i <= r; ++i)
a[i] += w;
sum[bl] += w * (r - l + 1);
return ;
}
for(register int i = bl + 1; i <= br - 1; ++i)
sum[i] += w * Bsize, lazy[i] += w;
push_down(bl), push_down(br);
for(register int i = l; i <= (bl + 1) * Bsize - 1; ++i)
a[i] += w, sum[bl] += w;
for(register int i = br * Bsize; i <= r; ++i)
a[i] += w, sum[br] += w;
}
int main() {
scanf("%d%d", &n, &m);
for(register int i = 0; i < n; ++i) scanf("%lld", &a[i]);
Bnum = (n - 1) / Bsize + 1;
for(register int i = 0; i < Bnum; ++i) {
int pre = i * Bsize;
for(register int j = 0; j < Bsize; ++j)
sum[i] += a[pre + j];
}
for(register int i = 1; i <= m; ++i) {
scanf("%d", &op);
if(op == 2) {
scanf("%d%d", &x, &y);
printf("%lld\n", query(x, y));
} else {
scanf("%d%d%lld", &x, &y, &z);
add(x, y, z);
}
}
return 0;
}
没有帐号? 立即注册