我的代码其他部分都没问题,但是函数中 return 的正负 2147483647 都返回的是 1e9,你们有什么头猪吗?
代码如下:
#include<bits/stdc++.h>
#define fo(x,y,z) for(int (x)=(y);(x)<=(z);(x)++)
#define fu(x,y,z) for(int (x)=(y);(x)>=(z);(x)--)
#define fuck printf("####~~~&*&*&~~~####\n");
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
#define lx int
inline lx qr()
{
char ch=getchar();lx x=0,f=1;
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
return x*f;
}
#undef lx
#define qr qr()
const int Ratio=0;
const int N=2e6+5;
const int maxx=1e9;
int son[N][2],v[N],siz[N],fa[N];
int T[N],w[N];
int tot,root;
namespace Wisadel
{
#define ls(x) son[x][0]
#define rs(x) son[x][1]
void Wpushup(int x)
{
siz[x]=siz[ls(x)]+siz[rs(x)]+1;
}
void Wrotate(int x)
{
int y=fa[x],z=fa[y],fla=rs(y)==x;
son[z][rs(z)==y]=x,fa[x]=z;
son[y][fla]=son[x][!fla],fa[son[x][!fla]]=y;
son[x][!fla]=y,fa[y]=x;
Wpushup(y),Wpushup(x);
}
void Wsplay(int &root,int x,int k)
{
while(fa[x]!=k)
{
int y=fa[x],z=fa[y];
if(z!=k)
((rs(y)==x)^(rs(z)==y))?Wrotate(x):Wrotate(y);
Wrotate(x);
}
if(!k) root=x;
}
void Wins(int &root,int x)
{
int c=root,f=0;
while(c) f=c,c=son[c][x>v[c]];
c=++tot;
if(f) son[f][x>v[f]]=c;
v[c]=x,fa[c]=f;
siz[c]=1;
Wsplay(root,c,0);
}
int Wqshu(int root,int x)
{
int c=root,res=0;
while(c)
if(x<=v[c]) c=ls(c);
else res+=siz[ls(c)]+1,c=rs(c);
return res;
}
void Wupd(int &root,int x,int y)
{
int c=root;
while(c)
{
if(v[c]==x) break;
if(v[c]>x) c=ls(c);
else c=rs(c);
}
Wsplay(root,c,0);
int l=ls(c),r=rs(c);
while(rs(l)) l=rs(l);
while(ls(r)) r=ls(r);
Wsplay(root,l,0),Wsplay(root,r,l);
ls(r)=0;
Wpushup(r),Wpushup(l);
Wins(root,y);
}
#define lson (rt<<1)
#define rson (rt<<1|1)
#define mid ((l+r)>>1)
void Wbuild(int rt,int l,int r)
{
Wins(T[rt],-maxx),Wins(T[rt],maxx);
fo(i,l,r) Wins(T[rt],w[i]);
if(l==r) return;
Wbuild(lson,l,mid),Wbuild(rson,mid+1,r);
}
int Wq(int rt,int l,int r,int x,int y,int k)
{
if(x<=l&&r<=y) return Wqshu(T[rt],k)-1;
int res=0;
if(x<=mid) res+=Wq(lson,l,mid,x,y,k);
if(y>mid) res+=Wq(rson,mid+1,r,x,y,k);
return res;
}
void Wchange(int rt,int l,int r,int x,int k)
{
Wupd(T[rt],w[x],k);
if(l==r) return;
if(x<=mid) Wchange(lson,l,mid,x,k);
else Wchange(rson,mid+1,r,x,k);
}
int Wquepre(int root,int x)
{
int c=root,res=-maxx;
while(c)
if(x<=v[c]) c=ls(c);
else res=max(res,v[c]),c=rs(c);
return res;
}
int Wquesuc(int root,int x)
{
int c=root,res=maxx;
while(c)
if(x>=v[c]) c=rs(c);
else res=min(res,v[c]),c=ls(c);
return res;
}
ll Wqpre(int rt,int l,int r,int x,int y,int k)
{
if(l>y||r<x) return -2147483647;
if(x<=l&&r<=y) return Wquepre(T[rt],k);
return max(Wqpre(rson,mid+1,r,x,y,k),Wqpre(lson,l,mid,x,y,k));
}
ll Wqsuc(int rt,int l,int r,int x,int y,int k)
{
if(l>y||r<x) return 2147483647;
if(x<=l&&r<=y) return Wquesuc(T[rt],k);
return min(Wqsuc(rson,mid+1,r,x,y,k),Wqsuc(lson,l,mid,x,y,k));
}
#undef mid
short main()
{
// freopen("P3380_1.in","r",stdin),freopen("1.out","w",stdout);
int n=qr,m=qr;
fo(i,1,n) w[i]=qr;
Wbuild(1,1,n);
while(m--)
{
int op=qr;int a,b,c,l,r;
switch(op)
{
case 1:
a=qr,b=qr,c=qr;
printf("%d\n",Wq(1,1,n,a,b,c)+1);
break;
case 2:
a=qr,b=qr,c=qr;
l=0,r=1e8;
while(l<r)
{
int mid=(l+r+1)>>1;
if(Wq(1,1,n,a,b,mid)+1<=c) l=mid;
else r=mid-1;
}
printf("%d\n",r);
break;
case 3:
a=qr,b=qr;
Wchange(1,1,n,a,b);
w[a]=b;
break;
case 4:
a=qr,b=qr,c=qr;
printf("%lld\n",Wqpre(1,1,n,a,b,c)==(int)-1e9?-2147483647:Wqpre(1,1,n,a,b,c));
break;
case 5:
a=qr,b=qr,c=qr;
printf("%lld\n",Wqsuc(1,1,n,a,b,c)==(int)1e9?2147483647:Wqsuc(1,1,n,a,b,c));
}
}
return Ratio;
}
}
int main(){return Wisadel::main();}