记录编号	600880	评测结果	AAAAAAAAAA
题目名称	[HEOI 2016] 排序	最终得分	100
用户昵称	wdsjl	是否通过	通过
代码语言	C++	运行时间	4.422 s
提交时间	2025-05-20 17:15:34	内存使用	4.81 MiB

#include <bits/stdc++.h> 
using namespace std;

inline int lc(int u) { return u<<1; }
inline int rc(int u) { return u<<1|1; }
inline int mid(int l, int r) { return (l+r)/2; }

const int N = 100010;
int n, m, p;
int T[4*N], lazy[4*N];
int a[N], ch[N], L[N], R[N];

inline void build(int u, int l, int r, int x) {
    if (l == r) {
        T[u] = a[l] >= x;
        lazy[u] = 0;
        return;
    }
    build(lc(u), l, mid(l, r), x);
    build(rc(u), mid(l, r)+1, r, x);
    T[u] = T[lc(u)]+T[rc(u)];
    lazy[u] = 0;
}

inline void pushdown(int u, int l, int r) {
    if (!lazy[u]) return;
    lazy[lc(u)] = lazy[rc(u)] = lazy[u];
    if (lazy[u] == 1) {
        T[lc(u)] = mid(l, r)-l+1;
        T[rc(u)] = r-mid(l, r);
    } else {
        T[lc(u)] = T[rc(u)] = 0;
    }
    lazy[u] = 0;
}

inline int query(int u, int l, int r, int x, int y) {
    if (x <= l && y >= r) return T[u];
    if (x > r || y < l) return 0;
    pushdown(u, l, r);
    return query(lc(u), l, mid(l, r), x, y) + query(rc(u), mid(l, r)+1, r, x, y);
}

inline int queryPoint(int u, int l, int r, int x) {
    if (l == x && r == x) return T[u];
    pushdown(u, l, r);
    if (x <= mid(l, r)) return queryPoint(lc(u), l, mid(l, r), x);
    else return queryPoint(rc(u), mid(l, r)+1, r, x);
}

inline void upd(int u, int l, int r, int x, int y, int val) {
    if (x <= l && y >= r) {
        T[u] = val*(r-l+1);
        lazy[u] = val ? 1 : -1;
        return;
    }
    if (x > r || y < l) return;
    pushdown(u, l, r);
    upd(lc(u), l, mid(l, r), x, y, val);
    upd(rc(u), mid(l, r)+1, r, x, y, val);
    T[u] = T[lc(u)]+T[rc(u)];
}

inline bool check(int x) {
    build(1, 1, n, x);
    for (int i = 1; i <= m; i++) {
        int cnt1 = query(1, 1, n, L[i], R[i]);
        if (ch[i] == 0) {
            upd(1, 1, n, R[i]-cnt1+1, R[i], 1);
            upd(1, 1, n, L[i], R[i]-cnt1, 0);
        } else {
            upd(1, 1, n, L[i], L[i]+cnt1-1, 1);
            upd(1, 1, n, L[i]+cnt1, R[i], 0);
        }
    }
    return queryPoint(1, 1, n, p);
}

int main() {
	freopen("heoi2016_sort.in","r",stdin);
	freopen("heoi2016_sort.out","w",stdout); 
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
    	
	}
    for (int i = 1; i <= m; i++) {
        scanf("%d %d %d", &ch[i], &L[i], &R[i]);
    }
    scanf("%d", &p);
    int ll = 1, rr = n, midd, ans;
    while (ll <= rr) {
    	//cout<<ll<<"  "<<rr<<endl;
        midd = (ll+rr) >> 1;
        if (check(midd)){
			ans = midd;
			 ll = midd+1;
		} 
        else rr = midd-1;
    }
    printf("%d\n", ans);
    return 0;
}