這題是可以用線段樹做的。

雖然$n\leq 10^9$

可以發現，真正需要用到的節點很少，故動態開點，只有需要用到的時候才新建節點。

這里我在下放標記的時候新建節點，因為每操作/查詢一個節點都需要先下放標記。

時間復雜度$O(m\log n)$，空間復雜度$O(m\log n)$左右，擁有所有題解里面最優的理論復雜度和最大的常數所以甚至跑的更慢

1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 typedef long long ll; 6 7 struct node { 8 ll data, tag; 9 node *lc, *rc; 10 11 node () { 12 data = 0, lc = rc = NULL; 13 } 14 15 void pushup() { 16 data = 0; 17 if(lc) data += lc->data; 18 if(rc) data += rc->data; 19 } 20 21 void pushtag(int l, int r) { 22 if(!lc) lc = new node; 23 if(!rc) rc = new node; 24 int mid = (l + r) >> 1; 25 lc->data += (mid - l + 1) * tag, lc->tag += tag; 26 rc->data += (r - mid) * tag, rc->tag += tag; 27 tag = 0; 28 } 29 30 } *st = new node; 31 32 void modify(node *cur, int l, int r, int ql, int qr, ll k) { 33 cur->pushtag(l, r); 34 if(ql <= l && r <= qr) { 35 cur->data += (r - l + 1) * k; 36 cur->tag = k; 37 } else { 38 int mid = (l + r) >> 1; 39 if(ql <= mid) modify(cur->lc, l, mid, ql, qr, k); 40 if(qr > mid) modify(cur->rc, mid + 1, r, ql, qr, k); 41 cur->pushup(); 42 } 43 } 44 45 ll query(node *cur, int l, int r, int ql, int qr) { 46 cur->pushtag(l, r); 47 if(ql <= l && r <= qr) { 48 return cur->data; 49 } 50 int mid = (l + r) >> 1; ll ans = 0; 51 if(ql <= mid) ans += query(cur->lc, l, mid, ql, qr); 52 if(qr > mid) ans += query(cur->rc, mid + 1, r, ql, qr); 53 return ans; 54 } 55 56 int main() { 57 int n, m, opt, x, y; ll z; 58 cin >> n >> m; 59 while(m--) { 60 cin >> opt; 61 if(opt == 1) { 62 cin >> x >> y >> z; 63 modify(st, 1, n, x, y, z); 64 } else { 65 cin >> x >> y; 66 cout << query(st, 1, n, x, y) << endl; 67 } 68 } 69 return 0; 70 } View Code

?

轉載于:https://www.cnblogs.com/zhylj/p/9488484.html

總結

以上是生活随笔為你收集整理的【Luogu P2781】 传教的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。