# 蒟蒻刚学OI，请问本题最后一组数据卡的是什么？

@zhyyng 2019-02-11 22:50 回复

#include<cstdio>
#include<cctype>
#include<vector>
using namespace std;
inline int getint()
{
register int r=0,f=1;
register char c=getchar();
while (!isdigit(c))
f=c=='-'?-f:f,c=getchar();
while (isdigit(c))
r=(r<<3)+(r<<1)+(c^48),c=getchar();
return r*f;
}
const int N=1e5+10;
const double alpha=0.75;
int n;
struct Node;
Node *nil;
struct Node
{
int key,siz,cnt;
bool del;
Node *ch[2];
Node(){key=siz=cnt=del=0,ch[0]=ch[1]=nil;}
Node(int x){key=x,siz=cnt=del=1,ch[0]=ch[1]=nil;}
}*root;
inline void pushup(Node *o){o->siz=o->ch[0]->siz+o->del+o->ch[1]->siz,o->cnt=o->ch[0]->cnt+1+o->ch[1]->cnt;}
void dfs(Node *o,vector<Node*> &v)
{
if (o==nil) return;
dfs(o->ch[0],v);
if (o->del) v.push_back(o);
dfs(o->ch[1],v);
if (!o->del) delete o;
}
Node* build(vector<Node*> v,int l,int r)
{
if (l==r) return nil;
int mid=(l+r)>>1;
Node *o=v[mid];
o->ch[0]=build(v,l,mid),o->ch[1]=build(v,mid+1,r),pushup(o);
return o;
}
vector<Node*> v;
void rebuild(Node* &o){v.clear(),dfs(o,v),o=build(v,0,v.size());}
void insert(Node* &o,int x)
{
if (o==nil) return o=new Node(x),void();
else
{
o->siz++,o->cnt++;
if (x<=o->key) insert(o->ch[0],x);
else insert(o->ch[1],x);
}
}
int rnk(Node *o,int x)
{
int ans=1;
while (o!=nil)
if (x<=o->key) o=o->ch[0];
else ans+=o->ch[0]->siz+o->del,o=o->ch[1];
return ans;
}
int kth(Node *o,int k)
{
while (o!=nil)
if (k<=o->ch[0]->siz) o=o->ch[0];
else if (k>o->ch[0]->siz+o->del) k-=o->ch[0]->siz+o->del,o=o->ch[1];
else return o->key;
}
void erase(Node *o,int rk)
{
if (o->del&&rk==o->ch[0]->siz+1)
return o->del=0,o->siz--,void();
o->siz--;
if (rk<=o->ch[0]->siz+o->del) erase(o->ch[0],rk);
else erase(o->ch[1],rk-o->ch[0]->siz-o->del);
}
int main()
{
root=nil=new Node();
n=getint();
int opt,x;
while (n--)
{
opt=getint(),x=getint();
if (opt==1) insert(root,x);
if (opt==2) erase(root,rnk(root,x));
if (opt==3) printf("%d\n",rnk(root,x));
if (opt==4) printf("%d\n",kth(root,x));
if (opt==5) printf("%d\n",kth(root,rnk(root,x)-1));
if (opt==6) printf("%d\n",kth(root,rnk(root,x+1)));
}
return 0;
}

@zhyyng 2019-02-11 23:06 回复 举报

@Doubleen 修改后的代码在这里

#include<cstdio>
#include<cctype>
#include<vector>
using namespace std;
inline int getint()
{
register int r=0,f=1;
register char c=getchar();
while (!isdigit(c))
f=c=='-'?-f:f,c=getchar();
while (isdigit(c))
r=(r<<3)+(r<<1)+(c^48),c=getchar();
return r*f;
}
const int N=1e5+10,INF=0x7fffffff;
const double alpha=0.75;
int n;
struct Node;
Node *nil;
struct Node
{
int key,siz,cnt;
bool del;
Node *ch[2];
Node(){key=siz=cnt=del=0,ch[0]=ch[1]=nil;}
Node(int x){key=x,siz=cnt=del=1,ch[0]=ch[1]=nil;}
}*root;
inline void pushup(Node *o){o->siz=o->ch[0]->siz+o->del+o->ch[1]->siz,o->cnt=o->ch[0]->cnt+1+o->ch[1]->cnt;}
void dfs(Node *o,vector<Node*> &v)
{
if (o==nil) return;
dfs(o->ch[0],v);
if (o->del) v.push_back(o);
dfs(o->ch[1],v);
if (!o->del) delete o;
}
Node* build(vector<Node*> v,int l,int r)
{
if (l==r) return nil;
int mid=(l+r)>>1;
Node *o=v[mid];
o->ch[0]=build(v,l,mid),o->ch[1]=build(v,mid+1,r),pushup(o);
return o;
}
vector<Node*> v;
void rebuild(Node* &o){v.clear(),dfs(o,v),o=build(v,0,v.size());}
void insert(Node* &o,int x)
{
if (o==nil) return o=new Node(x),void();
else
{
o->siz++,o->cnt++;
if (x<=o->key) insert(o->ch[0],x);
else insert(o->ch[1],x);
}
}
int rnk(Node *o,int x)
{
int ans=1;
while (o!=nil)
if (x<=o->key) o=o->ch[0];
else ans+=o->ch[0]->siz+o->del,o=o->ch[1];
return ans;
}
int kth(Node *o,int k)
{
while (o!=nil)
if (k<=o->ch[0]->siz) o=o->ch[0];
else if (k>o->ch[0]->siz+o->del) k-=o->ch[0]->siz+o->del,o=o->ch[1];
else return o->key;
}
void erase(Node *o,int rk)
{
if (o->del&&rk==o->ch[0]->siz+1)
return o->del=0,o->siz--,void();
o->siz--;
if (rk<=o->ch[0]->siz+o->del) erase(o->ch[0],rk);
else erase(o->ch[1],rk-o->ch[0]->siz-o->del);
}
int main()
{
root=nil=new Node(),insert(root,-INF),insert(root,INF);
n=getint();
int opt,x;
while (n--)
{
opt=getint(),x=getint();
if (opt==1) insert(root,x);
if (opt==2) erase(root,rnk(root,x));
if (opt==3) printf("%d\n",rnk(root,x)-1);
if (opt==4) printf("%d\n",kth(root,x+1));
if (opt==5) printf("%d\n",kth(root,rnk(root,x)-1));
if (opt==6) printf("%d\n",kth(root,rnk(root,x+1)));
}
return 0;
}
@zhyyng 2019-02-11 23:08 回复 举报