CodeForces Round #179 (295A) - Greg and Array

题目链接:http://codeforces.com/problemset/problem/295/A

我的做法,两次线段树

#include <cstdio>
#include <cstring> const int N = 100005; long long sumv[N * 3];
long long add[N * 3];
long long a[N]; struct opera {
int l, r;
long long d;
} op[N]; void pushdown(int o, int l, int r)
{
int m = (l + r) >> 1;
sumv[o << 1] += add[o] * (m - l + 1);
add[o << 1] += add[o];
sumv[o << 1 | 1] += add[o] * (r - m);
add[o << 1 | 1] += add[o];
add[o] = 0;
} int ql, qr;
long long val;
void update(int o, int l, int r)
{
if (ql <= l && qr >= r) {
sumv[o] += (r - l + 1) * val;
add[o] += val;
return ;
}
if (add[o]) pushdown(o, l, r);
int m = (l + r) >> 1;
if (m < qr) update(o << 1 | 1, m + 1, r);
if (m >= ql) update(o << 1, l, m);
sumv[o] = sumv[o << 1] + sumv[o << 1 | 1];
} int q;
long long query(int o, int l, int r)
{
if (l == r) return sumv[o];
if (add[o]) pushdown(o, l, r);
int m = (l + r) >> 1;
if (m < q) return query(o << 1 | 1, m + 1, r);
else return query(o << 1, l, m);
} int main()
{
//freopen("a.in", "r", stdin); int n, m, k;
int i;
scanf("%d%d%d", &n, &m, &k);
for (i = 1; i <= n; ++i) scanf("%lld", a + i);
for (i = 1; i <= m; ++i) {
scanf("%d%d%lld", &op[i].l, &op[i].r, &op[i].d);
}
val = 1;
for (i = 1; i <= k; ++i) {
scanf("%d%d", &ql, &qr);
update(1, 1, m);
}
for (i = 1; i <= m; ++i) {
q = i;
op[i].d *= query(1, 1, m);
}
memset(sumv, 0, sizeof sumv);
memset(add, 0, sizeof add);
for (i = 1; i <= m; ++i) {
ql = op[i].l;
qr = op[i].r;
val = op[i].d;
update(1, 1, n);
}
for (i = 1; i <= n; ++i) {
q = i;
printf("%lld", a[i] + query(1, 1, n));
if (i != n) printf(" ");
}
return 0;
}

  

后来看了学长的代码,又写了一遍.......:

#include <cstdio>

const int N = 100005;

long long l[N];
long long r[N];
long long d[N];
long long a[N];
long long op[N];
long long b[N]; main()
{
//freopen("in.txt", "r", stdin);
long long n, m, k;
scanf("%lld%lld%lld", &n, &m, &k);
for (int i = 1; i <= n; ++i)
scanf("%lld", &a[i]);
for (int i = 1; i <= m; ++i)
scanf("%lld%lld%lld", &l[i], &r[i], &d[i]);
long long x, y;
for (int i = 1; i <= k; ++i) {
scanf("%lld%lld", &x, &y);
++op[x];
--op[y+1];
}
for (int i = 1; i <= m; ++i) {
op[i] += op[i - 1];
d[i] *= op[i];
}
for (int i = 1; i <= m; ++i) {
b[l[i]] += d[i];
b[r[i]+1] -= d[i];
}
for (int i = 1; i <= n; ++i) {
b[i] += b[i - 1];
a[i] += b[i];
}
printf("%lld", a[1]);
for (int i = 2; i <= n; ++i)
printf(" %lld", a[i]);
}

  

上一篇:G - Greg and Array CodeForces - 296C 差分+线段树


下一篇:解析 Json 相关