題目鏈接：http://codeforces.com/problemset/problem/295/A 我果斷想錯了時間復雜度，所以就沒敲出來。 有兩種解法，一種是線段樹，兩棵線段樹，一棵維護每種指令用了多少次，一棵維護每段被怎么更新，時間復雜度都是nlogn級別的，可是我算錯了五個數量級，昨天晚上比賽沒敢寫…… 另一種方法是掃描法，O(n)級別，很簡單，編碼復雜度也比線段樹解法小得多。
掃描法
  view code
1 #include <cstdio>
2 #define LL long long
3 const int maxn = 100100;
4 LL a[maxn], b[maxn], d[maxn], ll[maxn], rr[maxn], c[maxn];
5 int l, r, n, m, k;
6 int main(){
7 scanf("%d%d%d", &n, &m, &k);
8 for (int i = 1; i <= n; i++) scanf("%I64d", &a[i]);
9 for (int i = 1; i <= m; i++) scanf("%I64d%I64d%I64d", &ll[i], &rr[i], &d[i]);
10 for (int i = 1; i <= k; i++){
11 scanf("%d%d", &l, &r);
12 c[l - 1] += 1; c[r] -= 1;
13 }
14 LL t = 0;
15 for (int i = 0; i <= m; i++){
16 d[i] *= t;
17 t += c[i];
18 }
19 t = 0;
20 for (int i = 0; i <= m; i++){
21 b[ll[i] - 1] += d[i];
22 b[rr[i]] -= d[i];
23 }
24 for (int i = 0; i <= n; i++){
25 a[i] += t; t += b[i];
26 }
27 for (int i = 1; i<= n; i++) printf("%I64d ", a[i]);
28 printf("\n");
29 return 0;
30 線段樹法 view code
1 #include <cstdio>
2 #include <cstring>
3 #define lson l, m, rt << 1
4 #define rson m + 1, r, rt << 1 | 1
5 #define LL long long
6 const int maxn = 101000;
7 struct seg{
8 LL sum[maxn << 2], add[maxn << 2];
9 void PushUp(int rt){
10 sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
11 }
12 void PushDown(int rt, int m){
13 if (add[rt]){
14 add[rt << 1] += add[rt];
15 add[rt << 1 | 1] += add[rt];
16 sum[rt << 1] += add[rt] * (m - (m >> 1));
17 sum[rt << 1 | 1] += add[rt] * (m >> 1);
18 add[rt] = 0;
19 }
20 }
21 void build(int l, int r, int rt){
22 add[rt] = 0;
23 if (l == r){
24 scanf("%I64d", &sum[rt]);
25 return;
26 }
27 int m = (l + r) >> 1;
28 build(lson);
29 build(rson);
30 PushUp(rt);
31 }
32 void update(int ll, int rr, LL c, int l, int r, int rt){
33 if (ll <= l && rr >= r){
34 sum[rt] += c * (r - l + 1);
35 add[rt] += c;
36 return;
37 }
38 PushDown(rt, r - l + 1);
39 int m = (l + r) >> 1;
40 if (ll <= m) update(ll, rr, c, lson);
41 if (rr > m) update(ll, rr, c, rson);
42 PushUp(rt);
43 }
44 LL query(int x, int l, int r, int rt){
45 if (l == r) return sum[rt];
46 PushDown(rt, r - l + 1);
47 int m = (l + r) >> 1;
48 if (x <= m) return query(x, lson);
49 else return query(x, rson);
50 }
51 };
52 struct chg{
53 int l, r;
54 LL d;
55 void get(){
56 scanf("%d%d%I64d", &l, &r, &d);
57 }
58 }x[maxn];
59 seg a, b;
60 int main(){
61 int n, m, k;
62 while (~scanf("%d%d%d", &n, &m, &k)){
63 a.build(1, n, 1);
64 memset(b.sum, 0, sizeof(b.sum));
65 memset(b.add, 0, sizeof(b.add));
66 for (int i = 1; i <= m; i++) x[i].get();
67 for (int i = 1; i <= k; i++){
68 int l, r;
69 scanf("%d%d", &l, &r);
70 b.update(l, r, 1, 1, m, 1);
71 }
72 for (int i = 1; i <= m; i++){
73 LL tt = b.query(i, 1, m, 1);
74 a.update(x[i].l, x[i].r, x[i].d * tt, 1, n, 1);
75 }
76 for (int i = 1; i <= n; i++){
77 LL ans = a.query(i, 1, n, 1);
78 printf("%I64d ", ans);
79 }
80 printf("\n");
81 }
82 return 0;
83
|