CF484E Sign on Fence

题目大意

给定一个长度为 n n n的数列，有 m m m次询问，询问形如l r k，要求在区间 [ l , r ] [l,r] [l,r]内选一个长度为 k k k的区间，求区间最小数的最大值。

题目思路

首先可以考虑二分答案，那么问题变为如何检验 [ l , r ] [l, r] [l,r]是否存在长度为 k k k且最小值为 ≥ m i d \geq mid ≥mid的子区间。

然后发现每次二分答案开销很大，考虑使用数据结构去维护。但发现区间信息不可并。这里参考洛谷dalao的妙妙题解：

将大于等于 m i d mid mid设为 1 1 1，否则设为 0 0 0，则问题变为查询区间内最长全 1 1 1区间长度是否大于 k k k。

然后就可以通过维护全后缀最长全 1 1 1区间来实现，不难发现这个信息是可以合并的。那么就可以使用主席树维护这一信息。

Code

#include 
#define int long long
#define endl '\n'
using namespace std;

const int N = 1e5 + 10;
int a[N], b[N], rk[N];
int n = 0;
namespace PresidentTree{
    struct Info{ 
        int len, pre, suf, maxx; 
        const Info operator+ (const Info &x) const {
            return (Info) {
                len + x.len,
                pre == len ? pre + x.pre : pre,
                x.suf == x.len ? x.suf + suf : x.suf,
                max({maxx, x.maxx, suf + x.pre})
            };
        }
    };

    int root[N = L) ans = ans + query(lson, L, R);
        if(mid > n;
    for(int i = 1; i > a[i], b[i] = a[i], rk[i] = i;
    sort(b + 1, b + 1 + n, [](int x, int y){ return x > y; });
    sort(rk + 1, rk + 1 + n, [](int x, int y){ return a[x] > a[y]; });
    PresidentTree::build(root[0], 1, n);
    for(int i = 1; i > m;
    for(int i = 1; i > L >> R >> k;
        int l = 1, r = n;
        while(l > 1;
            if(PresidentTree::query(root[mid], 1, n, L, R).maxx >= k) ans = mid, r = mid - 1;
            else l = mid + 1;
        }
        cout