题解 P1714 【切蛋糕】

· · 题解

Ad

个人新博客同步：http://blog.cinema000.xyz/%E3%80%90%E9%A2%98%E8%A7%A3%E3%80%91Luogu%201714%E3%80%90%E5%88%87%E8%9B%8B%E7%B3%95%E3%80%91/

Hints

读入优化比线段树长系列233

分析

这里一开始看以为题目给定了k然后来求，于是我就想着这样跑一个线段树就好了嘛，然后发现看错题了，，，

其实是维护区间最大子段和，那么就从朴素算法开始，O(n^3)，暴力枚举嘛，然后想着优化，求和可以用前缀和来搞（一开始还用线段树f**kO(n^2\log n)），这样是O(n^2)的，而且数据比较刁钻，好像不能有常数优化达到本题的n^2过百万，暴力碾标程的操作，于是继续优化就可以想到一个转移方程：max=\max(sum[i]-\min(sum[j]))，其中j\in [i-m,i-1]。

这样那个\min可以用线段树维护，而且这种方法在题解里面有人交过了f**k，于是就默默拿出著名的非递归线段树——zkw线段树

具体实现原理这里空白太小，写不下，请善用搜索引擎之。

代码

#pragma GCC optimize("Ofast")
#include<cstdio>
#include<algorithm>
#include<cctype>
const int MAXN = 500000 + 6;
int T[MAXN * 4],A[MAXN],sum[MAXN],M,n;

inline int L(int x){return x << 1;}
inline int R(int x){return x << 1 | 1;}
inline void maintain(int p){T[p] = std::min(T[L(p)],T[R(p)]);}

inline char read() {
    static const int IN_LEN = 1000000;
    static char buf[IN_LEN], *s, *t;
    if (s == t) {
        t = (s = buf) + fread(buf, 1, IN_LEN, stdin);
        if (s == t) return -1;
    }
    return *s++;
}

inline bool read(int &x) {
    static bool iosig;
    static char c;
    for (iosig = false, c = read(); !isdigit(c); c = read()) {
        if (c == '-') iosig = true;
        if (c == -1) return false;
    }
    for (x = 0; isdigit(c); c = read())
        x = (x + (x << 2) << 1) + (c ^ '0');
    if (iosig) x = -x;
    return true;
}
const int OUT_LEN = 10000000;
char obuf[OUT_LEN], *oh = obuf;
inline void print(char c) {
    if (oh == obuf + OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf;
    *oh++ = c;
}
inline void print(int x) {
    static int buf[30], cnt;
    if (x == 0) {
        print('0');
    } else {
        if (x < 0) print('-'), x = -x;
        for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 + 48;
        while (cnt) print((char)buf[cnt--]);
    }
}
inline void flush() {
    fwrite(obuf, 1, oh - obuf, stdout);
}

void build(){
    for(M = 1;M <= (n + 1); M <<= 1);
    for(int i = 1;i <= n;i++){sum[i] = sum[i - 1] + A[i],T[i + M] = sum[i];}
    for(int i = M - 1;i;i--) maintain(i);
}

int ask(int l,int r){
    int ans = 0x7fffffff;
    for(l += M - 1,r += M + 1;l ^ r ^ 1;l >>= 1,r >>= 1){
        if(~l & 1) ans = std::min(ans,T[l ^ 1]);
        if(r & 1) ans = std::min(ans,T[r ^ 1]);
    }
    return ans;
}

int main(){
    //freopen("in.txt","r",stdin);
    int m;read(n);read(m);
    for(int i = 1;i <= n;i++) read(A[i]);
    build();

    int max = -0x7fffffff;
    for(int i = m + 1;i <= n;i++){
        max = std::max(max,sum[i] - ask(i - m,i - 1));
    }
    printf("%d",max);

    return 0;
}