题目链接:http://codeforces.com/problemset/problem/295/A 我果断想错了时间复杂度,所以就没敲出来。 有两种解法,一种是线段树,两棵线段树,一棵维护每种指令用了多少次,一棵维护每段被怎么更新,时间复杂度都是nlogn级别的,可是我算错了五个数量级,昨天晚上比赛没敢写…… 另一种方法是扫描法,O(n)级别,很简单,编码复杂度也比线段树解法小得多。 扫描法
![](/Images/OutliningIndicators/ContractedBlock.gif) 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 线段树法 ![](/Images/OutliningIndicators/ContractedBlock.gif) 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
|