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区间来实现，不难发现这个信息是可以合并的。那么就可以使用主席树维护这一信息。

#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 << 5], lc[N << 5], rc[N << 5], tot = 0;
    Info tree[N << 5];

    #define lson lc[rt], l, mid
    #define rson rc[rt], mid + 1, r

    void build(int &rt, int l, int r){
        rt = ++tot;
        if(l == r){
            tree[rt] = {1, 0, 0, 0};
            return;
        }
        int mid = l + r >> 1;
        build(lson), build(rson);
        tree[rt] = tree[lc[rt]] + tree[rc[rt]];
    }

    void update(int &rt, int pre, int l, int r, int pos){
        rt = ++tot, lc[rt] = lc[pre], rc[rt] = rc[pre];
        if(l == r){
            tree[rt] = {1, 1, 1, 1};
            return;
        }
        int mid = l + r >> 1;
        if(mid >= pos) update(lc[rt], lc[pre], l, mid, pos);
        else update(rc[rt], rc[pre], mid + 1, r, pos);
        tree[rt] = tree[lc[rt]] + tree[rc[rt]];
    }

    Info query(int rt, int l, int r, int L, int R){
        if(l >= L && r <= R) return tree[rt];
        int mid = l + r >> 1; Info ans = {0, 0, 0, 0};
        if(mid >= L) ans = ans + query(lson, L, R);
        if(mid < R) ans = ans + query(rson, L ,R);
        return ans;
    }
}

#define root PresidentTree::root

inline void solve(){
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> 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 <= n; i++) PresidentTree::update(root[i], root[i - 1], 1, n, rk[i]);
    int m = 0; cin >> m;
    for(int i = 1; i <= m; i++){
        int L, R, k, ans = 0; cin >> L >> R >> k;
        int l = 1, r = n;
        while(l <= r){
            int mid = l + r >> 1;
            if(PresidentTree::query(root[mid], 1, n, L, R).maxx >= k) ans = mid, r = mid - 1;
            else l = mid + 1;
        }
        cout << b[ans] << endl;
    }
}

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    int t = 1; //cin >> t;
    while(t--) solve();
    return 0;
}