题目大意：

给出N个点 点的顺序是按y非递减给出的

level是这个点左下方点的个数

求各个level的数量

思路：

由于给的点有顺序 所以就简单了

一般用树状数组或线段树就可以

我用了平衡树 是为了练习啦 写的相当烂

用平衡树 不断地插入更新就可以了

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;const int N=15100;struct node{ int x;//x坐标 int l,r,f;//左右孩子 和父节点 int sum; int h;}mem[N];int treehead;//树的头结点int ans[N];//答案void Leftturn(int i)//左旋转{ int f=mem[i].f; int r=mem[i].r; if(f==-1) { mem[r].f=-1;treehead=r; } else { mem[r].f=f; if(mem[f].l==i) mem[f].l=r; else mem[f].r=r; } mem[i].r=mem[r].l; mem[mem[r].l].f=i; mem[r].l=i; mem[i].f=r; mem[i].h=max(mem[mem[i].l].h,mem[mem[i].r].h)+1; mem[i].sum=mem[mem[i].l].sum+mem[mem[i].r].sum+1; mem[r].h=max(mem[mem[r].l].h,mem[mem[r].r].h)+1; mem[r].sum=mem[mem[r].l].sum+mem[mem[r].r].sum+1;}void Rightturn(int i)//右旋转{ int f=mem[i].f; int l=mem[i].l; if(f==-1) { mem[l].f=-1;treehead=l; } else { mem[l].f=f; if(mem[f].l==i) mem[f].l=l; else mem[f].r=l; } mem[i].l=mem[l].r; mem[mem[l].r].f=i; mem[l].r=i; mem[i].f=l; mem[i].h=max(mem[mem[i].l].h,mem[mem[i].r].h)+1; mem[i].sum=mem[mem[i].l].sum+mem[mem[i].r].sum+1; mem[l].h=max(mem[mem[l].l].h,mem[mem[l].r].h)+1; mem[l].sum=mem[mem[l].l].sum+mem[mem[l].r].sum+1;}void update(int i)//对不平衡点的更新{ if(mem[mem[i].l].h
            
             mem[mem[x].r].h) { Rightturn(i); } else { Leftturn(mem[i].l); Rightturn(i); } }}void insert(int i,int k,int s)//插入新的点{ if(mem[i].x<=mem[k].x) { if(mem[i].r!=0) { insert(mem[i].r,k,s+mem[mem[i].l].sum+1);//继续向右插入 注意记录有多少比他小的点 } else { ++ans[s+mem[mem[i].l].sum+1]; mem[i].r=k; mem[k].f=i; } } else { if(mem[i].l!=0) { insert(mem[i].l,k,s); } else { ++ans[s]; mem[i].l=k; mem[k].f=i; } } mem[i].h=max(mem[mem[i].l].h,mem[mem[i].r].h)+1;//对路径上的点要更新 mem[i].sum=mem[mem[i].l].sum+mem[mem[i].r].sum+1; if(abs(mem[mem[i].l].h-mem[mem[i].r].h)>1) { update(i); }}int main(){ int n; scanf("%d",&n); memset(ans,0,sizeof(ans)); mem[0].l=mem[0].r=-1;//把0这个点设成假的所以叶子节点 mem[0].sum=0; mem[0].h=-1; int y; scanf("%d %d",&mem[1].x,&y); mem[1].h=0; mem[1].l=mem[1].r=0; mem[1].sum=1;mem[1].f=-1; treehead=1;//头结点 ++ans[0]; for(int i=2;i<=n;++i) { scanf("%d %d",&mem[i].x,&y); mem[i].l=mem[i].r=0; mem[i].sum=1;mem[i].h=0; insert(treehead,i,0); } for(int i=0;i