题解：CF1990F Polygonal Segments

· · 题解

思路

首先思考如何判断能否构成多边形，考虑类比一下三角形，你取出最长的边，那么其他的边首位相接所能达到的最长长度如果小于等于这条边长，那么必然是不合法的，如果大于，则必定合法，这个读者自证不难。

于是我们得到了合法的充要条件：2 倍最大值大于和。考虑如何进行维护，如果我们钦定了最大值，那么必然是选择最左边和最右边的端点，因为数越多一定越优，然后我们进行判断是否合法，若合法则结束，否则递归到左右子区间。

注意到每次不合法说明区间和至少减半，那么递归层数只有 \log sum 层，但是复杂度仍然无法得到保障。

尝试把这个问题放到线段树上，对于每个节点，维护区间和、区间最大值以及这个节点的答案，考虑如何 pushup，还是像之前暴力那样，取出最大值和位置，判断是否合法，如果不合法，那么考虑形成了两个新的子区间，此时注意到：两个区间必然有一个被左右子树的区间完全包含，于是只要递归一个即可，单次复杂度 \Theta(\log^2 n)，因为最多递归 \log n 层，每层又要查询区间和、区间最大值。

复杂度 \Theta((n+q)\log^3 n)，时限 8s，随便过。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ls (s << 1)
#define rs (s << 1 | 1)
#define pii pair<int, int>
#define piI pair<int, pii>
#define mkp make_pair
#define fi first
#define se second
const int N = 200200, inf = 0x3f3f3f3f3f3f3f3f;
int T, n, m;
int a[N];
struct Seg{
    struct Tree{
        int l, r;
        int sm, ans;
        pii mx;
        Tree() {}
        Tree(int _l)
            : l(_l), r(0), sm(0), ans(0), mx(0, 0) {};
    } tr[N << 2];
    #define l(s) tr[s].l
    #define r(s) tr[s].r
    #define sm(s) tr[s].sm
    #define mx(s) tr[s].mx
    #define ans(s) tr[s].ans
    piI query(int s, int L, int R) {
        if (l(s) > R || r(s) < L) return mkp(0, mkp(-inf, -inf));
        if (l(s) >= L && r(s) <= R) return mkp(sm(s), mx(s));
        piI res1 = query(ls, L, R), res2 = query(rs, L, R);
        return mkp(res1.fi + res2.fi, max(res1.se, res2.se));
    }
    Tree merge(Tree x, Tree y, bool opt = 0) {
        if (x.l == -1) return y;
        if (y.l == -1) return x;
        int ans = -1;
        Tree res;
        res.l = x.l, res.r = y.r, res.sm = x.sm + y.sm, res.mx = max(x.mx, y.mx), res.ans = max(x.ans, y.ans);
        int l = res.l, r = res.r;
        while (l <= x.r && y.l <= r && r - l + 1 >= max(3ll, res.ans + 1)) {
            piI ak = mkp(res.sm, res.mx);
            if (l != x.l || r != y.r) ak = query(1, l, r);
            if (ak.se.fi * 2 < ak.fi) {
                res.ans = max(res.ans, r - l + 1);
                break;
            }
            if (ak.se.se <= x.r) l = ak.se.se + 1;
            else r = ak.se.se - 1;
        }
        return res;
    }
    void pushup(int s) {
        tr[s] = merge(tr[ls], tr[rs]);
        return;
    }
    void build(int s, int l, int r) {
        l(s) = l, r(s) = r;
        if (l == r) {
            sm(s) = mx(s).fi = a[l], mx(s).se = l, ans(s) = -1;
            return;
        }
        int mid = (l + r) >> 1;
        build(ls, l, mid), build(rs, mid + 1, r);
        pushup(s);
        return;
    }
    void modify(int s, int x, int k) {
        if (l(s) == r(s)) {
            sm(s) = mx(s).fi = k;
            return;
        }
        if (x <= r(ls)) modify(ls, x, k);
        else modify(rs, x, k);
        pushup(s);
        return;
    }
    Tree ask(int s, int l, int r) {
        if (l(s) > r || r(s) < l) return Tree(-1);
        if (l(s) >= l && r(s) <= r) return tr[s];
        return merge(ask(ls, l, r), ask(rs, l, r));
    }
    int getans(int l, int r) {
        Tree res = ask(1, l, r);
        return res.ans;
    }
} Seg;
void solve() {
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%lld", a + i);
    Seg.build(1, 1, n);
    for (int i = 1, op, x, y; i <= m; ++i) {
        scanf("%lld%lld%lld", &op, &x, &y);
        if (op == 1) {
            printf("%lld\n", Seg.getans(x, y));
        }
        else {
            Seg.modify(1, x, y);
        }
    }
    return;
}
signed main() {
    scanf("%d", &T);
    while (T--) solve();
    return 0;
}