BZOJ 4552: [TJOI/HEOI2016]排序 – [线段树/二分]


题目传送门(BZOJ)
>原文链接<

题解 :

直接求看起来不太可做, 但是如果我们变成已知是哪个数然后验证似乎就变得有一点可做了.

我们先二分一个mid, 对于所有的a[i] , 令其为0, 否则为1,

每次操作相当于把区间里的1放到一侧,把区间里的0放到另一侧

当所有操作都做完之后, 若查询的位置答案是1, 代表实际答案大于等于当前mid, 否则小于当前mid,

更改边界继续二分即可

一共会二分出\log N次答案, 每次操作\log N, 总共复杂度O(N\log^2N)

代码 :

#include 
#include 
#include 
#define ls p << 1
#define rs p << 1|1
using namespace std;
const int N = 110000;
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2)?EOF:*p1++)
char buf[100000], *p1, *p2;
inline int rd() {
    int x = 0; char ch = nc();
    while(!isdigit(ch)) ch = nc();
    while(isdigit(ch)) x = ((x+(x<<2))<<1)+(ch^48), ch = nc();
    return x;
}
int t[N<<2], laz[N<<2];
int a[N], opt[N], x[N], y[N], b[N], n, m;
void build(int l, int r, int p) {
    laz[p] = -1;
    if(l == r) return t[p] = b[l], void();
    int mid = (l+r) >> 1;
    build(l, mid, ls); build(mid+1, r, rs);
    t[p] = t[ls]+t[rs];
}
inline void pd(int l, int r, int p) {
    if(~laz[p]) {
        laz[ls] = laz[rs] = laz[p];
        int mid = (l+r) >> 1;
        t[ls] = (mid-l+1)*laz[p];
        t[rs] = (r-mid)*laz[p];
        laz[p] = -1;
    }
}
void change(int l, int r, int p, int x, int y, int c) {
    if(x <= l && y >= r) return t[p] = (r-l+1)*c, laz[p] = c, void();
    pd(l, r, p);
    int mid = (l+r) >> 1;
    if(x <= mid) change(l, mid, ls, x, y, c);
    if(y >  mid) change(mid+1, r, rs, x, y, c);
    t[p] = t[ls]+t[rs];
}
int query(int l, int r, int p, int x, int y) {
    if(x <= l && y >= r) return t[p];
    pd(l, r, p);
    int mid = (l+r) >> 1, re = 0;
    if(x <= mid) re = query(l, mid, ls, x, y);
    if(y >  mid) re+= query(mid+1, r, rs, x, y);
    return re;
}
inline void init(int mid) {
    for(int i = 1; i <= n; i ++ ) b[i] = a[i] >= mid;
    build(1, n, 1);
}
inline void work() {
    for(int i = 1; i <= m; i ++ ) {
        int s = query(1, n, 1, x[i], y[i]);
        change(1, n, 1, x[i], y[i], 0);
        if(s) opt[i] == 1 ? change(1, n, 1, x[i], x[i]+s-1, 1) : change(1, n, 1, y[i]-s+1, y[i], 1);
    }
}
inline int solve(int k) {
    int l = 1, r = n;
    while(l < r) {
        int mid = (l+r) >> 1;
        init(mid);
        work();
        if(query(1, n, 1, k, k) == 1) l = mid+1;
        else r = mid;
    }
    return l-1;
}
int main() {
    n = rd(), m = rd();
    for(int i = 1; i <= n; i ++ ) a[i] = rd();
    for(int i = 1; i <= m; i ++ ) opt[i] = rd(), x[i] = rd(), y[i] = rd();
    printf("%d\n", solve(rd()));
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注