```cpp
/*
Author: EnderDeer
Online Judge: Luogu
*/
#include<bits/stdc++.h>
#define int long long
#define mem(x) memset(x,0,sizeof(x))
using namespace std;
int read(){
int s = 0,w = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-')w = -1;ch = getchar();}
while(ch >= '0' && ch <= '9')s = s * 10 + ch - '0',ch = getchar();
return s * w;
}
mt19937 rnd(time(0));
struct nodeee{
int l;
int r;
}ee[1000010];
struct node{
int l;
int r;
int w;
int key;
int siz;
}e[50010 * 40];
struct nodee{
int cnt,rt;
int newnode(int w){
cnt ++;
e[cnt].w = w;
e[cnt].key = rnd();
e[cnt].siz = 1;
return cnt;
}
void update(int i){
e[i].siz = e[e[i].l].siz + e[e[i].r].siz + 1;
}
void split(int i,int w,int &x,int &y){
if(!i){
x = y = 0;
return ;
}
if(e[i].w <= w){
x = i;
split(e[i].r,w,e[i].r,y);
}
else {
y = i;
split(e[i].l,w,x,e[i].l);
}
update(i);
}
int merge(int x,int y){
if(!x || !y)return x + y;
if(e[x].key > e[y].key){
e[x].r = merge(e[x].r,y);
update(x);
return x;
}
else {
e[y].l = merge(x,e[y].l);
update(y);
return y;
}
}
int x,y,z;
void ins(int w){
split(rt,w,x,y);
rt = merge(merge(x,newnode(w)),y);
}
void del(int w){
split(rt,w,x,z);
split(x,w - 1,x,y);
y = merge(e[y].l,e[y].r);
rt = merge(merge(x,y),z);
}
int getrank(int w){
split(rt,w - 1,x,y);
int ans = e[x].siz + 1;
rt = merge(x,y);
return ans;
}
int getnum(int rk){
int now = rt;
while(now){
if(e[e[now].l].siz + 1 == rk)break;
else if(e[e[now].l].siz >= rk)now = e[now].l;
else {
rk -= e[e[now].l].siz + 1;
now = e[now].r;
}
}
return e[now].w;
}
int pre(int w){
split(rt,w - 1,x,y);
int now = x;
while(e[now].r)now = e[now].r;
int ans = e[now].w;
rt = merge(x,y);
return ans;
}
int nxt(int w){
split(rt,w,x,y);
int now = y;
while(e[now].l)now = e[now].l;
int ans = e[now].w;
rt = merge(x,y);
return ans;
}
}t[100010];
int n,m;
int a[1000010];
void build(int i,int l,int r){
for(int ii = l;ii <= r;ii ++)t[i].ins(a[ii]);
ee[i].l = l;
ee[i].r = r;
if(l == r)return ;
int mid = (l + r) / 2;
build(i * 2,l,mid);
build(i * 2 + 1,mid + 1,r);
}
int queryrk(int i,int l,int r,int w){
if(l <= ee[i].l && ee[i].r <= r)return t[i].getrank(w) - 1;
int ans = 0;
int mid = (l + r) / 2;
if(r <= mid)ans = queryrk(i * 2,l,r,w);
else if(l > mid)ans = queryrk(i * 2 + 1,l,r,w);
else ans = queryrk(i * 2,l,mid,w) + queryrk(i * 2 + 1,mid + 1,r,w);
return ans;
}
int queryw(int l,int r,int w){
int ll = 0,rr = 2147483647,ans = -1;
int mid;
while(ll < rr){
mid = (ll + rr) / 2;
if(queryrk(1,l,r,mid) + 1 <= w){
ans = mid;
ll = mid + 1;
}
else rr = mid - 1;
}
return ans;
}
void update(int i,int pos,int w){
t[i].del(a[pos]);
t[i].ins(w);
if(ee[i].l == ee[i].r){
a[pos] = w;
return ;
}
int mid = (ee[i].l + ee[i].r) / 2;
if(pos <= mid)update(i * 2,pos,w);
else update(i * 2 + 1,pos,w);
}
int querypre(int i,int l,int r,int w){
if(l >= ee[i].l && ee[i].r >= r)return t[i].pre(w);
int ans = -2147483647;
int mid = (l + r) / 2;
if(r <= mid)ans = max(ans,querypre(i * 2,l,r,w));
else if(l > mid)ans = max(ans,querypre(i * 2 + 1,l,r,w));
else ans = max(ans,max(querypre(i * 2,l,mid,w),querypre(i * 2 + 1,mid + 1,r,w)));
return ans;
}
int querynxt(int i,int l,int r,int w){
if(ee[i].l >= l && ee[i].r <= r)return t[i].nxt(w);
int ans = 2147483647;
int mid = (l + r) / 2;
if(r <= mid)ans = min(ans,querynxt(i * 2,l,r,w));
else if(l > mid)ans = min(ans,querynxt(i * 2 + 1,l,r,w));
else ans = min(ans,min(querynxt(i * 2,l,mid,w),querynxt(i * 2 + 1,mid + 1,r,w)));
return ans;
}
signed main(){
cin>>n>>m;
for(int i = 1;i <= n;i ++)a[i] = read();
build(1,1,n);
while(m --){
int op;
int x,y,w;
op = read();
if(op == 1){
x = read(),y = read(),w = read();
printf("%lld\n",queryrk(1,x,y,w));
}
if(op == 2){
x = read(),y = read(),w = read();
printf("%lld\n",queryw(x,y,w));
}
if(op == 3){
x = read(),w = read();
update(1,x,w);
}
if(op == 4){
x = read(),y = read(),w = read();
printf("%lld\n",querypre(1,x,y,w));
}
if(op == 5){
x = read(),y = read(),w = read();
printf("%lld\n",querynxt(1,x,y,w));
}
}
return 0;
}
```
by EDqwq @ 2021-03-05 20:11:51
@[林深时x见鹿](/user/294562) 草，这题当时我从中午写到晚上
by Diaоsi @ 2021-03-05 21:57:04
@[Diaоsi](/user/137242) 有兴趣调下吗
by EDqwq @ 2021-03-05 22:12:26
@[林深时x见鹿](/user/294562) 你平衡树新建结点炸了
e 是公共的，但是 cnt 不是
by Rui_R @ 2021-03-06 11:44:25
导致新建节点很有可能会拿走之前已经分配掉的结点，就炸了
by Rui_R @ 2021-03-06 11:45:16
@[林深时x见鹿](/user/294562)
queryrk 里面
```
int mid = (l + r) / 2;
if (r <= mid)ans = queryrk(i * 2, l, r, w);
else if (l > mid)ans = queryrk(i * 2 + 1, l, r, w);
else ans = queryrk(i * 2, l, mid, w) + queryrk(i * 2 + 1, mid + 1, r, w);
```
这段你仔细看看
by Rui_R @ 2021-03-06 11:48:35
@[Rui_R](/user/101984) 啊，完蛋，我新的代码没发上来
by EDqwq @ 2021-03-06 11:48:40
```cpp
/*
Author: EnderDeer
Online Judge: Luogu
*/
#include<bits/stdc++.h>
#define int long long
#define mem(x) memset(x,0,sizeof(x))
using namespace std;
int read(){
int s = 0,w = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-')w = -1;ch = getchar();}
while(ch >= '0' && ch <= '9')s = s * 10 + ch - '0',ch = getchar();
return s * w;
}
mt19937 rnd(time(0));
struct nodeee{
int l;
int r;
}ee[1000010];
struct node{
int l;
int r;
int w;
int key;
int siz;
}e[50010 * 40];
int cnt,rt;
int newnode(int w){
cnt ++;
e[cnt].w = w;
e[cnt].key = rnd();
e[cnt].siz = 1;
return cnt;
}
void update(int i){
e[i].siz = e[e[i].l].siz + e[e[i].r].siz + 1;
}
void split(int i,int w,int &x,int &y){
if(!i){
x = y = 0;
return ;
}
if(e[i].w <= w){
x = i;
split(e[i].r,w,e[i].r,y);
}
else {
y = i;
split(e[i].l,w,x,e[i].l);
}
update(i);
}
int merge(int x,int y){
if(!x || !y)return x + y;
if(e[x].key > e[y].key){
e[x].r = merge(e[x].r,y);
update(x);
return x;
}
else {
e[y].l = merge(x,e[y].l);
update(y);
return y;
}
}
struct nodee{
int x,y,z;
void ins(int w){
split(rt,w,x,y);
rt = merge(merge(x,newnode(w)),y);
}
void del(int w){
split(rt,w,x,z);
split(x,w - 1,x,y);
y = merge(e[y].l,e[y].r);
rt = merge(merge(x,y),z);
}
int getrank(int w){
split(rt,w - 1,x,y);
int ans = e[x].siz + 1;
rt = merge(x,y);
return ans;
}
int getnum(int rk){
int now = rt;
while(now){
if(e[e[now].l].siz + 1 == rk)break;
else if(e[e[now].l].siz >= rk)now = e[now].l;
else {
rk -= e[e[now].l].siz + 1;
now = e[now].r;
}
}
return e[now].w;
}
int pre(int w){
split(rt,w - 1,x,y);
int now = x;
while(e[now].r)now = e[now].r;
int ans = e[now].w;
rt = merge(x,y);
return ans;
}
int nxt(int w){
split(rt,w,x,y);
int now = y;
while(e[now].l)now = e[now].l;
int ans = e[now].w;
rt = merge(x,y);
return ans;
}
}t[100010];
int n,m;
int a[1000010];
void build(int i,int l,int r){
for(int ii = l;ii <= r;ii ++)t[i].ins(a[ii]);
ee[i].l = l;
ee[i].r = r;
if(l == r)return ;
int mid = (l + r) / 2;
build(i * 2,l,mid);
build(i * 2 + 1,mid + 1,r);
}
int queryrk(int i,int l,int r,int w){
if(l <= ee[i].l && ee[i].r <= r)return t[i].getrank(w) - 1;
int ans = 0;
int mid = (l + r) / 2;
if(r <= mid)ans = queryrk(i * 2,l,r,w);
else if(l > mid)ans = queryrk(i * 2 + 1,l,r,w);
else ans = queryrk(i * 2,l,mid,w) + queryrk(i * 2 + 1,mid + 1,r,w);
return ans;
}
int queryw(int l,int r,int w){
int ll = 0,rr = 2147483647,ans = -1;
int mid;
while(ll < rr){
mid = (ll + rr) / 2;
if(queryrk(1,l,r,mid) + 1 <= w){
ans = mid;
ll = mid + 1;
}
else rr = mid - 1;
}
return ans;
}
void update(int i,int pos,int w){
t[i].del(a[pos]);
t[i].ins(w);
if(ee[i].l == ee[i].r){
a[pos] = w;
return ;
}
int mid = (ee[i].l + ee[i].r) / 2;
if(pos <= mid)update(i * 2,pos,w);
else update(i * 2 + 1,pos,w);
}
int querypre(int i,int l,int r,int w){
if(l >= ee[i].l && ee[i].r >= r)return t[i].pre(w);
int ans = -2147483647;
int mid = (l + r) / 2;
if(r <= mid)ans = max(ans,querypre(i * 2,l,r,w));
else if(l > mid)ans = max(ans,querypre(i * 2 + 1,l,r,w));
else ans = max(ans,max(querypre(i * 2,l,mid,w),querypre(i * 2 + 1,mid + 1,r,w)));
return ans;
}
int querynxt(int i,int l,int r,int w){
if(ee[i].l >= l && ee[i].r <= r)return t[i].nxt(w);
int ans = 2147483647;
int mid = (l + r) / 2;
if(r <= mid)ans = min(ans,querynxt(i * 2,l,r,w));
else if(l > mid)ans = min(ans,querynxt(i * 2 + 1,l,r,w));
else ans = min(ans,min(querynxt(i * 2,l,mid,w),querynxt(i * 2 + 1,mid + 1,r,w)));
return ans;
}
signed main(){
cin>>n>>m;
for(int i = 1;i <= n;i ++)a[i] = read();
build(1,1,n);
while(m --){
int op;
int x,y,w;
op = read();
if(op == 1){
x = read(),y = read(),w = read();
printf("%lld\n",queryrk(1,x,y,w));
}
if(op == 2){
x = read(),y = read(),w = read();
printf("%lld\n",queryw(x,y,w));
}
if(op == 3){
x = read(),w = read();
update(1,x,w);
}
if(op == 4){
x = read(),y = read(),w = read();
printf("%lld\n",querypre(1,x,y,w));
}
if(op == 5){
x = read(),y = read(),w = read();
printf("%lld\n",querynxt(1,x,y,w));
}
}
return 0;
}
```
by EDqwq @ 2021-03-06 11:48:54
你说的这个问题已经解决了，但是仍然错误
怀疑是平衡树问题，但我没有证据
by EDqwq @ 2021-03-06 11:49:38
哦你好像所有地方都是这么写的，你用力改一下
by Rui_R @ 2021-03-06 11:50:08