思路
将小于等于 \(x\) 的元素赋为 \(1\),其余的赋为 \(0\)。那么一个区间内小于等于 \(x\) 的数量就是区间中 \(1\) 的数量。
那么,将区间升序排列就是将 \(1\) 先堆在前面,将 \(0\) 堆到后面;降序排列同理。
考虑动态维护 \(x\) 的位置,记其位置为 \(t\)。如果 \(l \leq t \leq r\),则 \(t\) 可能会改变;否则不会改变。
在升序排列中,\(t\) 将会改变到最后一个 \(1\) 的位置;在降序排序中,\(t\) 将会改变到第一个 \(1\) 的位置。然后维护 \(0/1\) 可以用线段树维护。
Code
#include <bits/stdc++.h>
#define re register
using namespace std;
const int N = 2e5 + 10;
int n,q,k,x;
int arr[N];
inline int read(){
int r = 0,w = 1;
char c = getchar();
while (c < '0' || c > '9'){
if (c == '-') w = -1;
c = getchar();
}
while (c >= '0' && c <= '9'){
r = (r << 3) + (r << 1) + (c ^ 48);
c = getchar();
}
return r * w;
}
struct seg{
#define ls(u) (u << 1)
#define rs(u) (u << 1 | 1)
struct node{
int l,r;
int sum,tag;
}tr[N << 2];
inline void calc(int u,int k){
tr[u].sum = (tr[u].r - tr[u].l + 1) * k;
tr[u].tag = k;
}
inline void pushup(int u){
tr[u].sum = tr[ls(u)].sum + tr[rs(u)].sum;
}
inline void pushdown(int u){
if (~tr[u].tag){
calc(ls(u),tr[u].tag); calc(rs(u),tr[u].tag);
tr[u].tag = -1;
}
}
inline void build(int u,int l,int r){
tr[u] = {l,r,0,-1};
if (l == r) return tr[u].sum = (arr[l] <= k),void();
int mid = l + r >> 1;
build(ls(u),l,mid); build(rs(u),mid + 1,r);
pushup(u);
}
inline void modify(int u,int l,int r,int k){
if (l > r) return;
if (l <= tr[u].l && tr[u].r <= r) return calc(u,k);
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) modify(ls(u),l,r,k);
if (r > mid) modify(rs(u),l,r,k);
pushup(u);
}
inline int query(int u,int l,int r){
if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
pushdown(u);
int res = 0;
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) res += query(ls(u),l,r);
if (r > mid) res += query(rs(u),l,r);
return res;
}
#undef ls
#undef rs
}T;
int main(){
n = read(),q = read(),k = read();
for (re int i = 1;i <= n;i++){
arr[i] = read();
if (arr[i] == k) x = i;
}
T.build(1,1,n);
while (q--){
int op,l,r;
op = read(),l = read(),r = read();
if (op == 1){
int a = T.query(1,l,r);
if (l <= x && x <= r) x = l + a - 1;
T.modify(1,l,l + a - 1,1); T.modify(1,l + a,r,0);
}
else{
int a = (r - l + 1) - T.query(1,l,r);
if (l <= x && x <= r) x = l + a;
T.modify(1,l,l + a - 1,0); T.modify(1,l + a,r,1);
}
}
printf("%d",x);
return 0;
}
标签:Sort,rs,int,题解,mid,ABC237G,read,升序,inline
From: https://www.cnblogs.com/WaterSun/p/18261967