题目（BZOJ）
题目（LibreOJ）
题目（洛谷）
裸的树套树......我写的是线段树套splay，常数是比较大......
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template <class _E> inline void read(_E &e){
e=0;int ck=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')ck=-1;ch=getchar();}
while(isdigit(ch)){e=(e<<1)+(e<<3)+(ch^48);ch=getchar();}
e*=ck;
}
const int N=50050;
const int M=1600050;
int n,Q,head,tail;
int a[N],ans;
int ch[M][2],siz[M],key[M],fa[M],rt[M],cnt[M],idx;
inline int getx(int x){return ch[fa[x]][1]==x;}
inline void pushup(int x){if(x){siz[x]=cnt[x];if(ch[x][0])siz[x]+=siz[ch[x][0]];if(ch[x][1])siz[x]+=siz[ch[x][1]];}}
inline void roll(int x){
int y=fa[x],z=fa[y],l,r;
l=(ch[y][1]==x)^1;r=l^1;
ch[y][r]=ch[x][l];fa[ch[y][r]]=y;ch[x][l]=y;fa[y]=x;
if(z)ch[z][ch[z][1]==y]=x;fa[x]=z;
pushup(y);pushup(x);
}
inline void splay(int x){for(int f;f=fa[x];roll(x))if(fa[f])roll((getx(x)==getx(f))?f:x);}
inline void make_tree(int id,int val){
siz[id]=cnt[id]=1;fa[id]=0;key[id]=val;
ch[id][0]=ch[id][1]=0;
}
inline void clear_tree(int x){siz[x]=fa[x]=ch[x][0]=ch[x][1]=cnt[x]=key[x]=0;}
inline void insert(int id,int val){
if (!rt[id]){++idx;make_tree(idx,val);rt[id]=idx;return;}
int now=rt[id],f=0;
while(true){
if (val==key[now]){
cnt[now]++;pushup(f);splay(now);
rt[id]=now;return;
}
f=now;now=ch[now][key[now]<val];
if (!now){
++idx;make_tree(idx,val);fa[idx]=f;
ch[f][key[f]<val]=idx;
pushup(f);splay(idx);rt[id]=idx;return;
}
}
}
inline int find_pre(int id){int now=ch[rt[id]][0];while(ch[now][1])now=ch[now][1];return now;}
inline int find_suc(int id){int now=ch[rt[id]][1];while(ch[now][0])now=ch[now][0];return now;}
inline void find_pos(int id,int val){
int now=rt[id];
while(true){
if(key[now]==val){splay(now);rt[id]=now;return;}
else if(key[now]>val)now=ch[now][0];else if(key[now]<val)now=ch[now][1];
}
}
inline void del(int id){
int now=rt[id],y=now;
if(cnt[now]>1){cnt[now]--;pushup(now);return;}
if(!ch[now][0]&&!ch[now][1]){clear_tree(rt[id]);rt[id]=0;return;}
if(!ch[now][0]){rt[id]=ch[y][1];fa[rt[id]]=0;clear_tree(y);return;}
if(!ch[now][1]){rt[id]=ch[y][0];fa[rt[id]]=0;clear_tree(y);return;}
int pre=find_pre(id);y=rt[id];splay(pre);rt[id]=pre;
ch[rt[id]][1]=ch[y][1];fa[ch[y][1]]=rt[id];
clear_tree(y);pushup(rt[id]);
}
inline int find_rank(int id,int val){
int now=rt[id],ans=0;
while(true){
if(!now)return ans;
if(key[now]==val)return ((ch[now][0])?siz[ch[now][0]]:0)+ans;
if(key[now]<val){ans+=((ch[now][0])?siz[ch[now][0]]:0)+cnt[now];now=ch[now][1];}
else if(key[now]>val)now=ch[now][0];
}
}
inline int find_pre_val(int id,int k){
int now=rt[id];
while(now){if(key[now]<k){ans=max(ans,key[now]);now=ch[now][1];}else now=ch[now][0];}
return ans;
}
inline int find_suc_val(int id,int k){
int now=rt[id];
while(now){if(key[now]>k){ans=min(ans,key[now]);now=ch[now][0];}else now=ch[now][1];}
return ans;
}
#define ls id<<1
#define rs id<<1|1
void build(int l,int r,int id,int pos,int val){
insert(id,val);
if (l==r) return;
int mid=(l+r)>>1;
if (pos<=mid) build(l,mid,ls,pos,val);
else build(mid+1,r,rs,pos,val);
}
void change(int l,int r,int id,int pos,int val){
find_pos(id,a[pos]);del(id);insert(id,val);
if(l==r)return;
int mid=(l+r)>>1;
if (pos<=mid) change(l,mid,ls,pos,val);
else change(mid+1,r,rs,pos,val);
}
void qrank(int l,int r,int id,int L,int R,int k){
if (L<=l&&R>=r){
ans+=find_rank(id,k);
return;
}
int mid=(l+r)>>1;
if (L<=mid) qrank(l,mid,ls,L,R,k);
if (R>=mid+1) qrank(mid+1,r,rs,L,R,k);
}
void qpre(int l,int r,int id,int L,int R,int val){
if (L<=l&&R>=r){
ans=max(ans,find_pre_val(id,val));
return;
}
int mid=(l+r)>>1;
if (L<=mid) qpre(l,mid,ls,L,R,val);
if (R>=mid+1) qpre(mid+1,r,rs,L,R,val);
}
void qsuc(int l,int r,int id,int L,int R,int val){
if (L<=l&&R>=r){
ans=min(ans,find_suc_val(id,val));
return;
}
int mid=(l+r)>>1;
if (L<=mid) qsuc(l,mid,ls,L,R,val);
if (R>=mid+1) qsuc(mid+1,r,rs,L,R,val);
}
inline void sol1(){
int l,r,k;read(l),read(r),read(k);qrank(1,n,1,l,r,k);
printf(
}
inline void sol2(){
int l,r,k;read(l),read(r),read(k);
int L=head,R=tail+1;
while(L<R){
int mid=(L+R)>>1;ans=0;
qrank(1,n,1,l,r,mid);
if (ans<k) L=mid+1;
else R=mid;
}
printf(
}
inline void sol3(){
int pos,k;read(pos),read(k);
tail=max(tail,k);
change(1,n,1,pos,k);
a[pos]=k;
}
inline void sol4(){
int l,r,k;read(l),read(r),read(k);ans=-2147483647;qpre(1,n,1,l,r,k);
printf(
}
inline void sol5(){
int l,r,k;read(l),read(r),read(k);ans=2147483647;qsuc(1,n,1,l,r,k);
printf(
}
int main(){
read(n),read(Q);
for (int i=1;i<=n;++i) read(a[i]),tail=max(tail,a[i]);
for (int i=1;i<=n;++i) build(1,n,1,i,a[i]);
while(Q--){
int opt;read(opt);ans=0;
switch (opt){
case 1:{sol1();break;}
case 2:{sol2();break;}
case 3:{sol3();break;}
case 4:{sol4();break;}
case 5:{sol5();break;}
default:{break;}
}
}
return 0;
}
Comments NOTHING