bzoj 3267: KC采花&&3272&&3638&&3502 线段树

题目大意

给定一个长为n的序列,维护两种操作:

1.单点修改

2.在[l,r]这段区间中取k个互不相交的子段,使子段之和最大.

\(n \leq 50000,k \leq 20\)

题解

四倍经验.(但我的写法太丑过不了3502)

我们可以很简单地构建出一个最大费用最大流模型

把每个点拆点,然后S,T分别连接即可

但是这道题n达到50000,直接上费用流绝对T的不要不要的

我们想一下这样费用流的时候都在干什么

每次找出一个费用最大的区间...把答案加上费用之和...把所有的费用取反...

我们发现我们可以用线段树维护这个过程!

支持最大子段和查询和反转操作

所以我们维护一个最大子段和和最小子段和即可！！

啥？好像好要维护取到最大子段和和最小子段和时的端点？

啥？要维护从左端点的开始的最大子段和和从右端点开始的最大子段和？

好麻烦啊。。。估计是我写丑了...所以3502才被卡空间了...

Code

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

inline void read(int &x){

    x=0;char ch;bool flag = false;

    while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;

    while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;

}

inline int cat_max(const int &a,const int &b){return a>b ? a:b;}

inline int cat_min(const int &a,const int &b){return a<b ? a:b;}

const int maxn = 100010;

const int inf = 0x3f3f3f3f;

struct Node{

    int mx,lmx,rmx,lx,rx,plx,prx;

    int mn,lmn,rmn,ln,rn,pln,prn;

    int sum,rev;

    Node(){

        mx = lmx = rmx = -inf;

        mn = lmn = rmn =  inf;

        sum = lx = rx = ln = rn = rev = 0;

    }

    inline void set(int x,int p){

        rev = 0;mx = lmx = rmx = mn = lmn = rmn = sum = x;

        lx=rx=plx=prx=ln=rn=pln=prn = p;

    }

    inline void reve(){

        swap(mx,mn);swap(lmn,lmx);swap(rmn,rmx);

        swap(lx,ln);swap(rx,rn);swap(plx,pln);swap(prx,prn);

        mx = -mx;mn = -mn;

        lmn = -lmn;lmx = -lmx;

        rmx = -rmx;rmn = -rmn;

        sum = -sum;rev ^= 1;

    }

    Node friend operator + (const Node &l,const Node &r){

        Node c;

        c.sum = l.sum + r.sum;

        c.lmx = max(l.lmx,l.sum+max(r.lmx,0));

        c.rmx = max(r.rmx,r.sum+max(l.rmx,0));

        c.mx = max(max(l.mx,r.mx),max(l.rmx+max(0,r.lmx),max(l.rmx,0)+r.lmx) );

        if(c.lmx == l.lmx) c.plx = l.plx;

        else c.plx = r.plx;

        if(c.rmx == r.rmx) c.prx = r.prx;

        else c.prx = l.prx;

        if(c.mx == l.mx) c.lx = l.lx,c.rx = l.rx;

        else if(c.mx == r.mx) c.lx = r.lx,c.rx = r.rx;

        else if(c.mx == l.rmx+r.lmx)c.lx = l.prx,c.rx = r.plx;

        c.lmn = min(l.lmn,l.sum+min(r.lmn,0));

        c.rmn = min(r.rmn,r.sum+min(l.rmn,0));

        c.mn = min(min(l.mn,r.mn),min(l.rmn+min(0,r.lmn),min(l.rmn,0)+r.lmn) );

        if(c.lmn == l.lmn) c.pln = l.pln;

        else c.pln = r.pln;

        if(c.rmn == r.rmn) c.prn = r.prn;

        else c.prn = l.prn;

        if(c.mn == l.mn) c.ln = l.ln,c.rn = l.rn;

        else if(c.mn == r.mn) c.ln = r.ln,c.rn = r.rn;

        else if(c.mn == l.rmn+r.lmn) c.ln = l.prn,c.rn = r.pln;

    }

}T[maxn<<2];

int a[maxn];

inline void pushdown(int rt,int l,int r){

    if(T[rt].rev == 0) return;

    T[rt].rev = 0;

    if(l == r) return;

    T[rt<<1].reve();T[rt<<1|1].reve();

}

void build(int rt,int l,int r){

    if(l == r){

        T[rt].set(a[l],l);

        return;

    }int mid = l+r >> 1;

    build(rt<<1,l,mid);build(rt<<1|1,mid+1,r);

    T[rt] = T[rt<<1] + T[rt<<1|1];

}

void modify(int rt,int l,int r,int pos,int val){

    if(l == r){

        T[rt].set(val,l);

        return;

    }

    int mid = l+r >> 1;

    pushdown(rt,l,r);

    if(pos <= mid) modify(rt<<1,l,mid,pos,val);

    else modify(rt<<1|1,mid+1,r,pos,val);

    T[rt] = T[rt<<1] + T[rt<<1|1];

}

Node query(int rt,int l,int r,int L,int R){

    if(L <= l && r <= R) return T[rt];

    int mid = l+r >> 1;

    pushdown(rt,l,r);

    if(R <= mid) return query(rt<<1,l,mid,L,R);

    if(L >  mid) return query(rt<<1|1,mid+1,r,L,R);

    return query(rt<<1,l,mid,L,R) + query(rt<<1|1,mid+1,r,L,R);

}

void rever(int rt,int l,int r,int L,int R){

    if(L <= l && r <= R){T[rt].reve();return;}

    int mid = l+r >> 1;

    pushdown(rt,l,r);

    if(L <= mid) rever(rt<<1,l,mid,L,R);

    if(R >  mid) rever(rt<<1|1,mid+1,r,L,R);

    T[rt] = T[rt<<1] +  T[rt<<1|1];

}

struct seg{

    int l,r;

    seg(int l=0,int r=0){this->l=l;this->r=r;}

}sta[22];

int top,n;

inline int spfa(int l,int r,int num){

    top = 0;int ret = 0;

    while(num--){

        Node x = query(1,1,n,l,r);

        if(x.mx < 0) break;

        sta[++top] = seg(x.lx,x.rx);

        ret += x.mx;

        rever(1,1,n,x.lx,x.rx);

    }

    while(top){

        rever(1,1,n,sta[top].l,sta[top].r);

        --top;

    }

    return ret;

}

int main(){

    read(n);

    for(int i=1;i<=n;++i) read(a[i]);

    build(1,1,n);

    int m;read(m);

    int op,l,r,k;

    while(m--){

        read(op);read(l);read(r);

        if(op == 0){

            modify(1,1,n,l,r);

        }else{

            read(k);

            printf("%d\n",spfa(l,r,k));

        }

    }

    getchar();getchar();

    return 0;

}

巴特西

bzoj 3267: KC采花&&3272&&3638&&3502 线段树

题目大意

题解

Code

最新文章

热门文章