費用流+線段樹

看見這個題我們馬上就能想到費用流，設立源匯，分別向每個點連接容量為1費用為0的邊，然后相鄰的點之間連邊，費用為點權，跑費用流就行了，但是很明顯這樣會超時，那么我們要優(yōu)化一下，我們觀察費用流的過程，發(fā)現(xiàn)對于點與點之間的邊，每次取一段區(qū)間相當于把正向邊改為反向邊，費用變負，于是我們可以用線段樹來模擬這個過程，像費用流一樣貪心地選取區(qū)間的最大子段和，然后取反，每次取k次，然后恢復。這樣就好了

但是寫的時候有很多問題，比如如何返回一個區(qū)間？結構體！參考了popoqqq大神的代碼，發(fā)現(xiàn)我們可以通過重載小于號直接對結構體取max，這樣就十分好寫了

然后這道題有點卡常，一定要在重載的時候把傳入參數(shù)變成const+引用，這樣在cf上快了200ms

這就是傳說中的五倍經驗嗎

#include<bits/stdc++.h> using namespace std; const int N = 100010; namespace IO {const int Maxlen = N * 50;char buf[Maxlen], *C = buf;int Len;inline void read_in(){Len = fread(C, 1, Maxlen, stdin);buf[Len] = '\0';}inline void fread(int &x) {x = 0;int f = 1;while (*C < '0' || '9' < *C) { if(*C == '-') f = -1; ++C; }while ('0' <= *C && *C <= '9') x = (x << 1) + (x << 3) + *C - '0', ++C;x *= f;}inline void read(int &x){x = 0;int f = 1; char c = getchar();while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); }while(c >= '0' && c <= '9') { x = (x << 1) + (x << 3) + c - '0'; c = getchar(); }x *= f;}inline void read(long long &x){x = 0;long long f = 1; char c = getchar();while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); }while(c >= '0' && c <= '9') { x = (x << 1ll) + (x << 3ll) + c - '0'; c = getchar(); }x *= f;} } using namespace IO; struct data {int l, r, v;data() {}data(int l, int r, int v) : l(l), r(r), v(v) {}friend bool operator < (const data &a, const data &b) { return a.v < b.v; }friend data operator + (const data &a, const data &b) { return data(a.l, b.r, a.v + b.v); } }; struct node {data lmax, rmax, mx, mn, lmin, rmin, sum;int tag;node() {}node(int x, int v) {lmax = rmax = mx = mn = lmin = rmin = sum = data(x, x, v);}friend node operator + (const node &a, const node &b) {node c;if(a.tag == -1) return b;if(b.tag == -1) return a;c.tag = 0;c.sum = a.sum + b.sum;c.lmax = max(a.lmax, a.sum + b.lmax);c.lmin = min(a.lmin, a.sum + b.lmin);c.rmax = max(b.rmax, a.rmax + b.sum);c.rmin = min(b.rmin, a.rmin + b.sum);c.mx = max(max(a.mx, b.mx), a.rmax + b.lmax);c.mn = min(min(a.mn, b.mn), a.rmin + b.lmin);return c; } } tree[N << 2], st[21]; int n, q; int a[N]; void paint(node &o) {swap(o.lmax, o.lmin);swap(o.rmax, o.rmin);swap(o.mx, o.mn);o.sum.v *= -1;o.lmax.v *= -1;o.lmin.v *= -1;o.rmax.v *= -1;o.rmin.v *= -1;o.mx.v *= -1;o.mn.v *= -1;o.tag ^= 1; } void pushdown(int x) {if(tree[x].tag <= 0) return;paint(tree[x << 1]);paint(tree[x << 1 | 1]);tree[x].tag ^= 1; } void build(int l, int r, int x) {if(l == r){tree[x] = node(l, a[l]);return;}int mid = (l + r) >> 1;build(l, mid, x << 1);build(mid + 1, r, x << 1 | 1);tree[x] = tree[x << 1] + tree[x << 1 | 1]; } node query(int l, int r, int x, int a, int b) {if(l > b || r < a) return tree[0];if(l >= a && r <= b) return tree[x];pushdown(x); int mid = (l + r) >> 1;return (query(l, mid, x << 1, a, b)) + (query(mid + 1, r, x << 1 | 1, a, b)); } void reverse(int l, int r, int x, int a, int b) {if(l > b || r < a) return;if(l >= a && r <= b){paint(tree[x]);return;}pushdown(x);int mid = (l + r) >> 1;reverse(l, mid, x << 1, a, b);reverse(mid + 1, r, x << 1 | 1, a, b);tree[x] = tree[x << 1] + tree[x << 1 | 1]; } void update(int l, int r, int x, int pos, int v) {if(l == r){tree[x] = node(l, v);return;}pushdown(x);int mid = (l + r) >> 1;if(pos <= mid) update(l, mid, x << 1, pos, v);else update(mid + 1, r, x << 1 | 1, pos, v);tree[x] = tree[x << 1] + tree[x << 1 | 1]; } int main() {read_in();fread(n);for(int i = 1; i <= n; ++i) fread(a[i]);tree[0].tag = -1;build(1, n, 1);fread(q);while(q--){int opt, l, r, v;fread(opt);if(opt == 0){fread(l);fread(v);update(1, n, 1, l, v);}if(opt == 1){fread(l);fread(r);fread(v);int sum = 0, top = 0;while(v--){node ans = query(1, n, 1, l, r);if(ans.mx.v <= 0) break;reverse(1, n, 1, ans.mx.l, ans.mx.r);node tmp = query(1, n, 1, ans.mx.l, ans.mx.r);st[++top] = ans;sum += ans.mx.v;}printf("%d\n", sum);for(int i = top; i; --i) reverse(1, n, 1, st[i].mx.l, st[i].mx.r);}} return 0; } View Code

?

轉載于:https://www.cnblogs.com/19992147orz/p/7549892.html

總結

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

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