题面
题解
2019年AC的第一道题~~
函数名命名为rank竟然会ce
我写的是树状数组套值域线段树(动态开点)
操作1:询问(k)在([l-r])这段区间有多少数比它小,再加(1)
操作2:前缀和思想得到([l-r])区间的线段树,然后类似平衡树找第(k)大
操作3:直接修改
操作4/5:操作1+操作2
Code
#include<bits/stdc++.h>
#define LL long long
#define RG register
const int N = 50010;
using namespace std;
inline int gi() {
RG int x = 0; RG char c = getchar(); bool f = 0;
while (c != '-' && (c < '0' || c > '9')) c = getchar();
if (c == '-') c = getchar(), f = 1;
while (c >= '0' && c <= '9') x = x*10+c-'0', c = getchar();
return f ? -x : x;
}
int tot, A[N<<1], a[N], cnt, n;
int t1, t2, tmp1[N], tmp2[N];
struct question {
int op, l, r, k;
}q[N];
struct node {
int ls, rs, v;
}t[N<<7];
int rt[N];
#define lowbit(x) (x&(-x))
void Update(int &now, int l, int r, int pos, int k) {
if (!now) now = ++cnt;
t[now].v += k;
if (l == r) return ;
int mid = (l + r) >> 1;
if (pos <= mid) Update(t[now].ls, l, mid, pos, k);
else Update(t[now].rs, mid+1, r, pos, k);
}
void update(int x, int k) {
for (int i = x; i <= n; i += lowbit(i)) Update(rt[i], 1, tot, a[x], k);
}
int query(int now, int l, int r, int pos) {
if (l == r) return t[now].v;
int mid = (l + r) >> 1;
if (pos <= mid) return query(t[now].ls, l, mid, pos);
return t[t[now].ls].v+query(t[now].rs, mid+1, r, pos);
}
int Rank(int l, int r, int k) {
if (l > r) return 0;
l--;
int s = 0;
for (int i = r; i; i -= lowbit(i)) s += query(rt[i], 1, tot, k);
for (int i = l; i; i -= lowbit(i)) s -= query(rt[i], 1, tot, k);
return s;
}
int Kth(int l, int r, int k) {
if (l == r) return l;
int mid = (l + r) >> 1, s = 0;
for (int i = 1; i <= t1; i++) s += t[t[tmp1[i]].ls].v;
for (int i = 1; i <= t2; i++) s -= t[t[tmp2[i]].ls].v;
if (s >= k) {
for (int i = 1; i <= t1; i++) tmp1[i] = t[tmp1[i]].ls;
for (int i = 1; i <= t2; i++) tmp2[i] = t[tmp2[i]].ls;
return Kth(l, mid, k);
}
else {
for (int i = 1; i <= t1; i++) tmp1[i] = t[tmp1[i]].rs;
for (int i = 1; i <= t2; i++) tmp2[i] = t[tmp2[i]].rs;
return Kth(mid+1, r, k-s);
}
}
int kth(int l, int r, int k) {
l--; t1 = t2 = 0;
for (int i = r; i; i -= lowbit(i)) tmp1[++t1] = rt[i];
for (int i = l; i; i -= lowbit(i)) tmp2[++t2] = rt[i];
return A[Kth(1, tot, k)];
}
int main() {
//freopen(".in", "r", stdin);
//freopen(".out", "w", stdout);
n = gi();
int m = gi();
for (int i = 1; i <= n; i++) A[++tot] = a[i] = gi();
for (int i = 1; i <= m; i++) {
q[i].op = gi();
if (q[i].op != 3) {
q[i].l = gi(); q[i].r = gi(); q[i].k = gi();
if (q[i].op != 2) A[++tot] = q[i].k;
}
else {
q[i].l = q[i].r = gi();
A[++tot] = q[i].k = gi();
}
}
sort(A+1, A+1+tot);
tot = unique(A+1, A+1+tot) - A - 1;
for (int i = 1; i <= n; i++) a[i] = lower_bound(A+1, A+1+tot, a[i])-A;
for (int i = 1; i <= n; i++) update(i, 1);
for (int i = 1; i <= m; i++)
if (q[i].op != 2)
q[i].k = lower_bound(A+1, A+1+tot, q[i].k)-A;
for (int i = 1; i <= m; i++) {
if (q[i].op == 1)
printf("%d
", Rank(q[i].l, q[i].r, q[i].k-1)+1);
else if (q[i].op == 2) printf("%d
", kth(q[i].l, q[i].r, q[i].k));
else if (q[i].op == 3) {
update(q[i].l, -1);
a[q[i].l] = q[i].k;
update(q[i].l, 1);
}
else if (q[i].op == 4) {
int g = Rank(q[i].l, q[i].r, q[i].k-1);
if (!g) puts("-2147483647");
else printf("%d
", kth(q[i].l, q[i].r, g));
}
else {
int g = Rank(q[i].l, q[i].r, q[i].k);
if (g == q[i].r-q[i].l+1) puts("2147483647");
else printf("%d
", kth(q[i].l, q[i].r, g+1));
}
}
return 0;
}