SP685 SEQPAR - Partition the sequence Solution

更好的阅读体验戳此进入

（建议您从上方链接进入我的个人网站查看此 Blog，在 Luogu 中图片会被墙掉，部分 Markdown 也会失效）

题面

给定 $n$$n$ 个数的数列 $a_n$$a_n$，给定 $k$$k$，将数列分成 $k$$k$ 段，满足每一段的元素和不大于 $m$$m$，求最小的 $m$$m$。$T$$T$ 组数据。

$1\le k\le n\le 1.5\times {10}^4,-3\times {10}^4\le a_i\le 3\times {10}^4,1\le T\le 10$$1 \le k \le n \le 1.5 \times 10^4, -3 \times 10^4 \le a_i \le 3 \times 10^4, 1 \le T \le 10$。

Solution

首先二分答案很显然，二分 $m$$m$，并验证 $m$$m$ 是否对于 $k$$k$ 成立。

然后对于验证 $m$$m$ 是否成立，我们显然可以想到，对于这样的一个数列和 $m$$m$，有解的情况下，一定存在一个最小的和最大的块数的划分方案，并且解是存在连续性的，对于最小 $fmn$$fmn$ 和最大 $fmx$$fmx$ 一定有 $\mathrm{\forall }k\in [fmn,fmx]$$\forall k \in \left[ fmn, fmx \right]$ 都成立，这个的严谨证明我不会很显然，就不证明了。

The proof is left to the reader.

然后对于求 $fmn(i)$$fmn(i)$ 和 $fmx(i)$$fmx(i)$，令其为考虑前 $i$$i$ 个数的合法方案的最小和最大的 $k$$k$，求个前缀和 $sum(i)$$sum(i)$，显然有如下的 DP 方程：

对于二分的范围，不难想到我们令数列中负数的和为 $\xi$$\xi$，正数的和为 $ϵ$$\epsilon$，那么范围即为 $[\xi ,ϵ]$$\left[ \xi, \epsilon \right]$，我们令这个区间长度为 $v$$v$。

发现这个东西的复杂度是 $O(n^2)$$O(n^2)$ 的，最终复杂度 $O(T{n}^2\log v)$$O(T n^2 \log v)$，显然会寄，于是考虑优化 DP。

显然我们发现这个转移时可以优化的，可以考虑写个平衡树然后区间取最大最小值等，但是我不会不好写，于是我们考虑线段树。

普通线段树显然开不下，所以我们要写一个动态开点的权值线段树，其中的叶子节点下标表示 $sum(i)$$sum(i)$ 的值，存的是 $fmn(i)$$fmn(i)$ 和 $fmx(i)$$fmx(i)$ 的值，然后支持单点修改和区间求 $min$$\min$ 和 $max$$\max$。考虑在每次验证的时候新开一个线段树，然后每次查询 $[sum(i)-m,inf]$$\left[ sum(i) - m, \inf \right]$ 区间的 $min$$\min$ 和 $max$$\max$ 然后 $+1$$+1$ 作为新的 $fmn(i)$$fmn(i)$ 和 $fmx(i)$$fmx(i)$，然后再把这两个值插到线段树中对应的 $sum(i)$$sum(i)$ 中，具体实现可以看一下代码，这道题还是挺巧妙的。

对于权值线段树的范围，显然与二分限制相同。

那么最终复杂度为 $O(Tn\log n\log v)$$O(T n \log n \log v)$。

Code

xxxxxxxxxx
113
1
#define _USE_MATH_DEFINES
2
#include <bits/extc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12
using namespace __gnu_pbds;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
#define INF 0x3f3f3f3f
24

25
template<typename T = int>
26
inline T read(void);
27

28
struct Node{
29
    Node *ls, *rs;
30
    int fmn, fmx;
31
    OPNEW;
32
}nd[30000000];
33
void* Node::operator new(size_t){static Node* P = nd; return P++;}
34
int limMin, limMax;
35
int N, K;
36
int a[18000];
37
int sum[18000];
38
int fmn[18000], fmx[18000];
39
Node* rt;
40
class SegTree{
41
    private:
42
        #define MID ((gl + gr) >> 1)
43
        #define SIZ (gr - gl + 1)
44
    public:
45
        void Pushup(Node* p){
46
            if(!p)return;
47
            p->fmn = min(p->ls ? p->ls->fmn : INF, p->rs ? p->rs->fmn : INF),
48
            p->fmx = max(p->ls ? p->ls->fmx : -INF, p->rs ? p->rs->fmx : -INF);
49
        }
50
        void Modify(int idx, pair < int, int > val, Node* &p = rt, int gl = limMin, int gr = limMax){
51
            if(!p)p = new Node{npt, npt, INF, 0};
52
            if(gl == gr)return tie(p->fmn, p->fmx) = val, void();
53
            if(idx <= MID) Modify(idx, val, p->ls, gl, MID);
54
            else Modify(idx, val, p->rs, MID + 1, gr);
55
            Pushup(p);
56
        }
57
        pair < int, int > Query(int l, int r, Node* p = rt, int gl = limMin, int gr = limMax){
58
            // printf("Querying l = %d, r = %d, gl = %d, gr = %d, val = %d,%d\n", l, r, gl, gr, p ? p->fmn : -114514, p ? p->fmx : 114514);
59
            if(!p)return {INF, -INF};
60
            if(l <= gl && gr <= r)return {p->fmn, p->fmx};
61
            auto L = MID >= l ? Query(l, r, p->ls, gl, MID) : make_pair(INF, -INF);
62
            auto R = MID + 1 <= r ? Query(l, r, p->rs, MID + 1, gr) : make_pair(INF, -INF);
63
            return {min(L.first, R.first), max(L.second, R.second)};
64
        }
65
}st;
66
bool Check(int M){
67
    rt = new Node{npt, npt, INF, -INF};
68
    fmx[0] = fmn[0] = 0;
69
    st.Modify(sum[0], {fmn[0], fmx[0]});
70
    for(int i = 1; i <= N; ++i){
71
        tie(fmn[i], fmx[i]) = st.Query(sum[i] - M, INF);
72
        ++fmn[i], ++fmx[i];
73
        st.Modify(sum[i], {fmn[i], fmx[i]});
74
    }
75
    if(fmn[N] <= K && K <= fmx[N])return true;
76
    return false;
77
}
78
int main(){
79
    int T = read();
80
    while(T--){
81
        limMin = limMax = 0;
82
        N = read(), K = read();
83
        for(int i = 1; i <= N; ++i)
84
            a[i] = read(),
85
            a[i] >= 0 ? limMax += a[i] : limMin += a[i],
86
            sum[i] = sum[i - 1] + a[i];
87
        int l = limMin, r = limMax, ans(-1);
88
        while(l <= r){
89
            int mid = (l + r) >> 1;
90
            if(Check(mid))ans = mid, r = mid - 1;
91
            else l = mid + 1;
92
        }
93
        printf("%d\n", ans);
94
    }
95
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
96
    return 0;
97
}
98

99
template<typename T>
100
inline T read(void){
101
    T ret(0);
102
    short flag(1);
103
    char c = getchar();
104
    while(c != '-' && !isdigit(c))c = getchar();
105
    if(c == '-')flag = -1, c = getchar();
106
    while(isdigit(c)){
107
        ret *= 10;
108
        ret += int(c - '0');
109
        c = getchar();
110
    }
111
    ret *= flag;
112
    return ret;
113
}

UPD

update-2022_10_13 初稿