min和max绝对不要宏定义
by UnyieldingTrilobite @ 2020-03-03 13:11:41
哈哈哈
by 汪子涵0207 @ 2020-03-03 13:33:34
@[刘海峰](/user/99506)
这样就能AC了
```cpp
#pragma GCC optimize("Ofast")
#include<ctime>
#include<cstdio>
#include<algorithm>
#define N 200010
#define M 80000000
#define maxint 2147483647
using namespace std;
struct tree{
int l,r,id,pri,cnt,sum;
} tr[M];
int len,n,mx;
struct SGT{
struct Treap{
#define ls tr[x].l
#define rs tr[x].r
int root;
void update(int x)
{
tr[x].sum=tr[ls].sum+tr[rs].sum+tr[x].cnt;
}
void zig(int &x)
{
int y=ls;
ls=tr[ls].r;
tr[y].r=x;
tr[y].sum=tr[x].sum;
update(x);
update(y);
x=y;
}
void zag(int &x)
{
int y=rs;
rs=tr[rs].l;
tr[y].l=x;
tr[y].sum=tr[x].sum;
update(x);
update(y);
x=y;
}
void add(int &x,int a)
{
if(!x) x=++len;
if(tr[x].cnt==0)
{
tr[x].id=a;
tr[x].pri=rand();
tr[x].sum=tr[x].cnt=1;
return;
}
if(tr[x].id==a)
{
tr[x].cnt++;
tr[x].sum++;
return;
}
tr[x].sum++;
if(tr[x].id>a)
{
add(ls,a);
if(tr[ls].pri>tr[x].pri) zig(x);
}
if(tr[x].id<a)
{
add(rs,a);
if(tr[rs].pri>tr[x].pri) zag(x);
}
}
int query_suf(int a)
{
int x=root,ans=maxint;
while(x)
{
if(tr[x].id<=a) x=tr[x].r;
else ans=tr[x].id,x=tr[x].l;
}
return ans;
}
int query_pre(int a)
{
int x=root,ans=-maxint;
while(x)
{
if(tr[x].id>=a) x=tr[x].l;
else ans=tr[x].id,x=tr[x].r;
}
return ans;
}
void del(int &x,int a)
{
if(tr[x].id==a)
{
if(tr[x].cnt>1) tr[x].cnt--,tr[x].sum--;
else if(ls==0||rs==0) x=ls+rs;
else if(tr[ls].pri>tr[rs].pri) zig(x),del(x,a);
else zag(x),del(x,a);
return;
}
tr[x].sum--;
if(tr[x].id>a) del(ls,a);
else del(rs,a);
}
int query_Kth(int k)
{
int x=root;
while(x)
{
if(tr[ls].sum<k&&tr[ls].sum+tr[x].cnt>=k) return tr[x].id;
if(tr[ls].sum>=k) x=ls;
else k-=tr[ls].sum+tr[x].cnt,x=rs;
}
return 0;
}
int query_rank(int k)
{
int x=root,ans=0;
while(x)
{
if(k==tr[x].id) return ans+tr[ls].sum+1;
if(k<tr[x].id) x=ls;
else ans+=tr[ls].sum+tr[x].cnt,x=rs;
}
return ans;
}
int query_num(int a)
{
int x=root,ans=0;
while(x)
{
if(a==tr[x].id) return tr[x].cnt;
if(a<tr[x].id) x=ls;
else x=rs;
}
return 0;
}
}Tr[N];
#define mid ((l+r)/2)
inline void add(int x,int a)
{
int now=1,l=1,r=n;
while(l<r)
{
Tr[now].add(Tr[now].root,a);
if(x<=mid) r=mid,now*=2;
else l=mid+1,now+=now+1;
}
Tr[now].add(Tr[now].root,a);
}
inline void change(int x,int a,int b)
{
int now=1,l=1,r=n;
while(l<r)
{
Tr[now].del(Tr[now].root,a);
Tr[now].add(Tr[now].root,b);
if(x<=mid) r=mid,now*=2;
else l=mid+1,now+=now+1;
}
Tr[now].del(Tr[now].root,a);
Tr[now].add(Tr[now].root,b);
}
int L,R;
inline int query_suf(int l,int r,int now,int a)
{
if(l>R||r<L) return maxint;
if(l>=L&&r<=R) return Tr[now].query_suf(a);
int MID=mid;
return min(query_suf(l,MID,now*2,a),
query_suf(MID+1,r,now*2+1,a));
}
inline int get_suf(int l,int r,int a)
{
L=l,R=r;
return query_suf(1,n,1,a);
}
inline int query_pre(int l,int r,int now,int a)
{
if(l>R||r<L) return -maxint;
if(l>=L&&r<=R) return Tr[now].query_pre(a);
int MID=mid;
return max(query_pre(l,MID,now*2,a),query_pre(MID+1,r,now*2+1,a));
}
inline int get_pre(int l,int r,int a)
{
L=l,R=r;
return query_pre(1,n,1,a);
}
inline int query_num(int l,int r,int now,int a)
{
if(l>R||r<L) return 0;
if(l>=L&&r<=R) return Tr[now].query_num(a);
int MID=mid;
return query_num(l,MID,now*2,a)+query_num(MID+1,r,now*2+1,a);
}
inline int get_num(int l,int r,int a)
{
L=l,R=r;
return query_num(1,n,1,a);
}
inline int query_rank(int l,int r,int now,int a)
{
if(l>R||r<L) return 0;
if(l>=L&&r<=R) return Tr[now].query_rank(a-1);
int MID=mid;
return query_rank(l,MID,now*2,a)+query_rank(MID+1,r,now*2+1,a);
}
inline int get_rank(int l,int r,int a)
{
L=l,R=r;
return query_rank(1,n,1,a)+1;
}
inline int get_Kth(int ll,int rr,int k)
{
int l=0,r=mx,a,b;
while(l<r)
{
a=get_rank(ll,rr,mid);
b=a+get_num(ll,rr,mid);
if(a<=k&&b>k) return mid;
if(b<=k) l=mid+1;
else r=mid;
}
return l;
}
}SGT_Treap;
int op,T,a[N];
int main()
{
srand(time(NULL));
scanf("%d%d",&n,&T);
for(register int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(a[i]>mx) mx=a[i];
SGT_Treap.add(i,a[i]);
}
int x,y,k;
while(T--)
{
scanf("%d%d%d",&op,&x,&y);
switch(op)
{
case 1:{
scanf("%d",&k);
printf("%d\n",SGT_Treap.get_rank(x,y,k));
break;
}
case 2:{
scanf("%d",&k);
printf("%d\n",SGT_Treap.get_Kth(x,y,k));
break;
}
case 3:{
SGT_Treap.change(x,a[x],y);
a[x]=y;
break;
}
case 4:{
scanf("%d",&k);
printf("%d\n",SGT_Treap.get_pre(x,y,k));
break;
}
default:{
scanf("%d",&k);
printf("%d\n",SGT_Treap.get_suf(x,y,k));
break;
}
}
}
return 0;
}
```
by 2020ywj @ 2020-03-04 14:42:04
把一个头文件删掉，再把两个宏定义干了，for循环前面加个register，比刘海峰之后100分的代码还有快12毫秒(最坏情况下)
by 2020ywj @ 2020-03-04 14:47:57
@[2020杨雯杰](/user/243479) Orz，谢谢大佬
by _LHF_ @ 2020-03-04 16:09:12