学网站设计和平面设计,网站做多个产品,网站后台文件名,百度网盘app下载安装费用流线段树 看见这个题我们马上就能想到费用流#xff0c;设立源汇#xff0c;分别向每个点连接容量为1费用为0的边#xff0c;然后相邻的点之间连边#xff0c;费用为点权#xff0c;跑费用流就行了#xff0c;但是很明显这样会超时#xff0c;那么我们要优化一下线段树 看见这个题我们马上就能想到费用流设立源汇分别向每个点连接容量为1费用为0的边然后相邻的点之间连边费用为点权跑费用流就行了但是很明显这样会超时那么我们要优化一下我们观察费用流的过程发现对于点与点之间的边每次取一段区间相当于把正向边改为反向边费用变负于是我们可以用线段树来模拟这个过程像费用流一样贪心地选取区间的最大子段和然后取反每次取k次然后恢复。这样就好了 但是写的时候有很多问题比如如何返回一个区间结构体参考了popoqqq大神的代码发现我们可以通过重载小于号直接对结构体取max这样就十分好写了 然后这道题有点卡常一定要在重载的时候把传入参数变成const引用这样在cf上快了200ms 这就是传说中的五倍经验吗 #includebits/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
