[关闭]
@zhangche0526 2017-04-17T04:31:37.000000Z 字数 12901 阅读 1508

伸展树讲义 20170407

讲义

Splay Tree

模板

样例输入

10 5 7
1 2 3 4 5 6 7 8 9 10
1 3 5 7 9
2 3 4 5 6 7 10

样例输出

YES
NO
YES
NO
YES

标准程序

  1. #include<iostream>
  2. #include<cstdio>
  3. #define x node[x_p]
  4. #define y node[y_p]
  5. #define z node[z_p]
  6. #define p node[p_p]
  7. #define u node[u_p]
  8. #define v node[v_p]
  9. using namespace std;
  11. const int MAXN=1000;
  13. struct splayTree
  14. {
  15. //private
  17.     int root,size;
  19.     struct N
  20.     {
  21.         int lc,rc,fa;
  22.         int val;
  23.         N(){lc=rc=fa=val=0;}
  24.     }node[MAXN+1];int ncnt;
  26.     void lRotate(int x_p)
  27.     {
  28.         int y_p=x.rc;
  29.         x.rc=y.lc;
  30.         if(y.lc) node[y.lc].fa=x_p;
  31.         y.fa=x.fa;
  32.         if(!x.fa) root=y_p;
  33.         else if(x_p==node[x.fa].lc) node[x.fa].lc=y_p;
  34.         else node[x.fa].rc=y_p;
  35.         y.lc=x_p,x.fa=y_p;
  36.     }
  38.     void rRotate(int x_p)
  39.     {
  40.         int y_p=x.lc;
  41.         x.lc=y.rc;
  42.         if(y.rc) node[y.rc].fa=x_p;
  43.         y.fa=x.fa;
  44.         if(!x.fa) root=y_p;
  45.         else if(x_p==node[x.fa].lc) node[x.fa].lc=y_p;
  46.         else node[x.fa].rc=y_p;
  47.         y.rc=x_p,x.fa=y_p;
  48.     }
  50.     void splay(int x_p)
  51.     {
  52.         while(x.fa)
  53.         {
  54.             if(!node[x.fa].fa)
  55.             {
  56.                 if(node[x.fa].lc==x_p) rRotate(x.fa);
  57.                 else lRotate(x.fa);
  58.             }else if(node[x.fa].lc==x_p&&node[node[x.fa].fa].lc==x.fa)
  59.             {
  60.                 rRotate(node[x.fa].fa);
  61.                 rRotate(x.fa);
  62.             }else if(node[x.fa].rc==x_p&&node[node[x.fa].fa].rc==x.fa)
  63.             {
  64.                 lRotate(node[x.fa].fa);
  65.                 lRotate(x.fa);
  66.             }else if(node[x.fa].lc==x_p&&node[node[x.fa].fa].rc==x.fa)
  67.             {
  68.                 rRotate(x.fa);
  69.                 lRotate(x.fa);
  70.             }else
  71.             {
  72.                 lRotate(x.fa);
  73.                 rRotate(x.fa);
  74.             }
  75.         }
  76.     }
  78.     void replace(int u_p,int v_p)
  79.     {
  80.         if(!u.fa) root=v_p;
  81.         else if(u_p==node[u.fa].lc) node[u.fa].lc=v_p;
  82.         else node[u.fa].rc=v_p;
  83.         if(v_p) v.fa=u.fa;
  84.     }
  86.     int subtreeMin(int u_p)
  87.     {
  88.         while(u.lc) u_p=u.lc;
  89.         return u_p;
  90.     }
  92.     int subtreeMax(int u_p)
  93.     {
  94.         while(u.rc) u_p=u.rc;
  95.         return u_p;
  96.     }
  98. //public
  100.     splayTree(){root=0,size=0,ncnt=0;}
  102.     void insert(int val)
  103.     {
  104.         int z_p=root;
  105.         int p_p=0;
  106.         while(z_p)
  107.         {
  108.             p_p=z_p;
  109.             if(node[z_p].val<val) z_p=node[z_p].rc;
  110.             else z_p=node[z_p].lc;
  111.         }
  112.         z_p=++ncnt;
  113.         z.val=val;
  114.         z.fa=p_p;
  115.         if(!p_p) root=z_p;
  116.         else if(p.val<z.val) p.rc=z_p;
  117.         else p.lc=z_p;
  118.         splay(z_p);
  119.         ++size;
  120.     }
  122.     int find(int val)
  123.     {
  124.         int z_p=root;
  125.         while(z_p)
  126.         {
  127.             z=node[z_p];
  128.             if(z.val<val) z_p=z.rc;
  129.             else if(val<z.val) z_p=z.lc;
  130.             else return z_p;
  131.         }
  132.         return 0;
  133.     }
  135.     void erase(int val)
  136.     {
  137.         int z_p=find(val);
  138.         if(!z_p) return;
  139.         splay(z_p);
  140.         if(!z.lc) replace(z_p,z.rc);
  141.         else if(!z.rc) replace(z_p,z.lc);
  142.         else
  143.         {
  144.             int y_p=subtreeMin(z.rc);
  145.             if(y.fa!=z_p)
  146.             {
  147.                 replace(y_p,y.rc);
  148.                 y.rc=z.rc;
  149.                 node[y.rc].fa=y_p;
  150.             }
  151.             replace(z_p,y_p);   
  152.             y.lc=z.lc;
  153.             node[y.lc].fa=y_p;
  154.         }
  155.         --size;
  156.     }
  158.     int getMin() {return node[subtreeMin(root)].val;}
  159.     int getMax() {return node[subtreeMax(root)].val;}
  161.     bool isEmpty() {return root==0;}
  162.     int getSize() {return size;}
  163. } spT; 
  165. int main()
  166. {
  167.     int i;
  168.     int n,m,q;
  169.     scanf("%d%d%d",&n,&m,&q);
  170.     for(i=1;i<=n;i++)
  171.     {
  172.         int r;scanf("%d",&r);
  173.         spT.insert(r);
  174.     }
  175.     for(i=1;i<=m;i++)
  176.     {
  177.         int r;scanf("%d",&r);
  178.         spT.erase(r);
  179.     }
  180.     for(i=1;i<=m;i++)
  181.     {
  182.         int r;scanf("%d",&r);
  183.         if(spT.find(r)) printf("YES\n");
  184.         else printf("NO\n");
  185.     }
  186.     return 0;
  187. }

例题

HNOI2004 宠物收养所

时空限制

时间限制：10s
空间限制：162MB

题目背景
最近，阿Q开了一间宠物收养所。收养所提供两种服务：收养被主人遗弃的宠物和让新的主人领养这些宠物。每个领养者都希望领养到自己满意的宠物，阿Q根据领养者的要求通过他自己发明的一个特殊的公式，得出该领养者希望领养的宠物的特点值 a （ a 是一个正整数， a< ），而他也给每个处在收养所的宠物一个特点值。这样他就能够很方便的处理整个领养宠物的过程了，宠物收养所总是会有两种情况发生：被遗弃的宠物过多或者是想要收养宠物的人太多，而宠物太少。

  1. 被遗弃的宠物过多时，假若到来一个领养者，这个领养者希望领养的宠物的特点值为 a ，那么它将会领养一只目前未被领养的宠物中特点值最接近a的一只宠物。（任何两只宠物的特点值都不可能是相同的，任何两个领养者的希望领养宠物的特点值也不可能是一样的）如果有两只满足要求的宠物，即存在两只宠物他们的特点值分别为 a-b 和 a+b ，那么领养者将会领养特点值为 a-b 的那只宠物。
  2. 收养宠物的人过多，假若到来一只被收养的宠物，那么哪个领养者能够领养它呢？能够领养它的领养者，是那个希望被领养宠物的特点值最接近该宠物特点值的领养者，如果该宠物的特点值为 a ，存在两个领养者他们希望领养宠物的特点值分别为 a-b 和 a+b ，那么特点值为 a-b 的那个领养者将成功领养该宠物。

一个领养者领养了一个特点值为 a 的宠物，而它本身希望领养的宠物的特点值为b，那么这个领养者的不满意程度为 abs(a-b) 。

任务描述

你得到了一年当中，领养者和被收养宠物到来收养所的情况，希望你计算所有收养了宠物的领养者的不满意程度的总和。这一年初始时，收养所里面既没有宠物，也没有领养者。

输入格式

第一行为一个正整数 n，n<=80000 ，表示一年当中来到收养所的宠物和领养者的总数。接下来的n行，按到来时间的先后顺序描述了一年当中来到收养所的宠物和领养者的情况。每行有两个正整数 a, b ，其中 a=0 表示宠物， a=1 表示领养者， b 表示宠物的特点值或是领养者希望领养宠物的特点值。（同一时间呆在收养所中的，要么全是宠物，要么全是领养者，这些宠物和领养者的个数不会超过 10000 个）

输出格式

仅有一个正整数，表示一年当中所有收养了宠物的领养者的不满意程度的总和 mod 1000000 以后的结果。

样例输入

5
0 2
0 4
1 3
1 2
1 5

样例输出

3

样例解释

abs(3-2) + abs(2-4)=3，最后一个领养者没有宠物可以领养

标准程序1 by张澈

  1. #include<iostream>
  2. #include<cstdio>
  3. #define x node[x_p]
  4. #define y node[y_p]
  5. #define z node[z_p]
  6. #define u node[u_p]
  7. #define v node[v_p]
  8. #define p node[p_p]
  9. using namespace std;
  11. const int MAXN=80000,INF=~0U>>1,P=1000000;
  13. struct splayTree
  14. {
  15.     int root,size;
  16.     int type;
  17.     struct N
  18.     {
  19.         int lc,rc,fa;
  20.         int val;
  21.         N(){lc=rc=fa=val=0;}
  22.     }node[MAXN+1];int ncnt;
  23.     void lRotate(int x_p)
  24.     {
  25.         int y_p=x.rc;
  26.         x.rc=y.lc;
  27.         if(y.lc) node[y.lc].fa=x_p;
  28.         y.fa=x.fa;
  29.         if(!x.fa) root=y_p;
  30.         else if(x_p==node[x.fa].lc) node[x.fa].lc=y_p;
  31.         else node[x.fa].rc=y_p;
  32.         y.lc=x_p,x.fa=y_p;
  33.     }
  34.     void rRotate(int x_p)
  35.     {
  36.         int y_p=x.lc;
  37.         x.lc=y.rc;
  38.         if(y.rc) node[y.rc].fa=x_p;
  39.         y.fa=x.fa;
  40.         if(!x.fa) root=y_p;
  41.         else if(x_p==node[x.fa].lc) node[x.fa].lc=y_p;
  42.         else node[x.fa].rc=y_p;
  43.         y.rc=x_p,x.fa=y_p;
  44.     }
  45.     void splay(int x_p)
  46.     {
  47.         while(x.fa)
  48.         {
  49.             if(!node[x.fa].fa)
  50.             {
  51.                 if(node[x.fa].lc==x_p) rRotate(x.fa);
  52.                 else lRotate(x.fa);
  53.             }else if(node[x.fa].lc==x_p&&node[node[x.fa].fa].lc==x.fa)
  54.             {
  55.                 rRotate(node[x.fa].fa);
  56.                 rRotate(x.fa);
  57.             }else if(node[x.fa].rc==x_p&&node[node[x.fa].fa].rc==x.fa)
  58.             {
  59.                 lRotate(node[x.fa].fa);
  60.                 lRotate(x.fa);
  61.             }else if(node[x.fa].lc==x_p&&node[node[x.fa].fa].rc==x.fa)
  62.             {
  63.                 rRotate(x.fa);
  64.                 lRotate(x.fa);
  65.             }else
  66.             {
  67.                 lRotate(x.fa);
  68.                 rRotate(x.fa);
  69.             }
  70.         }
  71.     }
  72.     void replace(int u_p,int v_p)
  73.     {
  74.         if(!u.fa) root=v_p;
  75.         else if(u_p==node[u.fa].lc) node[u.fa].lc=v_p;
  76.         else node[u.fa].rc=v_p;
  77.         if(v_p) v.fa=u.fa;
  78.     }
  79.     int subtreeMin(int u_p)
  80.     {
  81.         while(u.lc) u_p=u.lc;
  82.         return u_p;
  83.     }
  84.     splayTree(){root=size=ncnt=type=0;}
  85.     void insert(int val)
  86.     {
  87.         int z_p=root;
  88.         int p_p=0;
  89.         while(z_p)
  90.         {
  91.             p_p=z_p;
  92.             if(node[z_p].val<val) z_p=node[z_p].rc;
  93.             else z_p=node[z_p].lc;
  94.         }
  95.         z_p=++ncnt;
  96.         z.val=val;
  97.         z.fa=p_p;
  98.         if(!p_p) root=z_p;
  99.         else if(p.val<z.val) p.rc=z_p;
  100.         else p.lc=z_p;
  101.         splay(z_p);
  102.         ++size;
  103.     }
  104.     void erase(int z_p)
  105.     {
  106.         splay(z_p);
  107.         if(!z.lc) replace(z_p,z.rc);
  108.         else if(!z.rc) replace(z_p,z.lc);
  109.         else
  110.         {
  111.             int y_p=subtreeMin(z.rc);
  112.             if(y.fa!=z_p)
  113.             {
  114.                 replace(y_p,y.rc);
  115.                 y.rc=z.rc;
  116.                 node[y.rc].fa=y_p;
  117.             }
  118.             replace(z_p,y_p);   
  119.             y.lc=z.lc;
  120.             node[y.lc].fa=y_p;
  121.         }
  122.         --size;
  123.     }
  124.     int work(int val,int rtype)
  125.     {
  126.         if(!size) {type=rtype;insert(val);return 0;}
  127.         if(rtype==type) {insert(val);return 0;}
  128.         int x_p=-1,y_p=-1,u_p=root;
  129.         while(u_p)
  130.             if(u.val<=val)
  131.             {
  132.                 x_p=u_p;
  133.                 u_p=u.rc;
  134.             }else u_p=u.lc;
  135.         u_p=root;
  136.         while(u_p)
  137.             if(u.val>=val)
  138.             {
  139.                 y_p=u_p;
  140.                 u_p=u.lc;
  141.             }else u_p=u.rc;
  142.         if(x_p==-1) x_p=y_p;
  143.         else if(y_p!=-1)
  144.             if(y.val-val<val-x.val) x_p=y_p;
  145.         erase(x_p);
  146.         return x.val>val?x.val-val:val-x.val;
  147.     }
  148. } spT;
  150. int main()
  151. { 
  152.     int i;int n;int ans=0;
  153.     scanf("%d",&n);
  154.     for(i=1;i<=n;i++)
  155.     {
  156.         int rtype,val;
  157.         scanf("%d%d",&rtype,&val);
  158.         ans=(ans+spT.work(val,rtype))%P;
  159.     }
  160.     printf("%d\n",ans);
  161.     return 0;
  162. }

标准程序2 by hzwer

  1. #include<iostream>
  2. #include<cstdio>
  3. using namespace std;
  4. const int MAXN=80000,P=1000000;
  5. int n,size,root,t1,t2;
  6. long long ans;
  7. int ch[MAXN+1][2],num[MAXN+1],fa[MAXN+1];
  9. void rotate(int x,int &k)
  10. {
  11.     int y=fa[x],z=fa[y],l,r;
  13.     if(ch[y][0]==x) l=0;
  14.     else l=1;
  15.     r=l^1;
  17.     if(y==k) k=x;
  18.     else
  19.     {
  20.         if(ch[z][0]==y) ch[z][0]=x;
  21.         else ch[z][1]=x;
  22.     }
  23.     fa[x]=z;fa[y]=x;fa[ch[x][r]]=y;
  24.     ch[y][l]=ch[x][r];ch[x][r]=y;
  25. }
  27. void splay(int x,int &k)
  28. {
  29.     int y,z;
  30.     while(x!=k)
  31.     {
  32.         y=fa[x],z=fa[y];
  33.         if(y!=k)
  34.         {
  35.             if((ch[y][0]==x)^(ch[z][0]==y))
  36.                 rotate(x,k);
  37.             else rotate(y,k);
  38.         }
  39.         rotate(x,k);
  40.     }
  41. }
  43. void insert(int &k,int x,int last)
  44. {
  45.     if(k==0){size++;k=size;num[k]=x;fa[k]=last;splay(k,root);return;}
  46.     if(x<num[k]) insert(ch[k][0],x,k);
  47.     else insert(ch[k][1],x,k);
  48. }
  49. void del(int x)
  50. {
  51.     splay(x,root);
  52.     if(ch[x][0]*ch[x][1]==0)
  53.         root=ch[x][0]+ch[x][1];
  54.     else 
  55.     {
  56.         int k=ch[x][1];
  57.         while(ch[k][0]) k=ch[k][0];
  58.         ch[k][0]=ch[x][0];fa[ch[x][0]]=k;
  59.         root=ch[x][1];
  60.     }
  61.     fa[root]=0;
  62. }
  63. void ask_before(int k,int x)
  64. {
  65.     if(k==0) return;
  66.     if(num[k]<=x)
  67.     {
  68.         t1=k;
  69.         ask_before(ch[k][1],x);
  70.     }
  71.     else ask_before(ch[k][0],x);
  72. }
  74. void ask_after(int k,int x)
  75. {
  76.     if(k==0) return;
  77.     if(num[k]>=x)
  78.     {
  79.         t2=k;
  80.         ask_after(ch[k][0],x);
  81.     }
  82.     else ask_after(ch[k][1],x);
  83. }
  85. int main()
  86. {
  87.     scanf("%d",&n);
  88.     int rtype,atype,x;
  89.     for(int i=1;i<=n;i++)
  90.     {
  91.         scanf("%d%d",&rtype,&x);
  92.         if(!root)
  93.         {
  94.             atype=rtype;
  95.             insert(root,x,0);
  96.         }
  97.         else if(rtype==atype) insert(root,x,0);
  98.         else
  99.         {
  100.             t1=t2=-1;
  101.             ask_before(root,x);ask_after(root,x);
  102.             if(t1==-1)
  103.             {
  104.                 ans+=num[t2]-x;
  105.                 ans%=P;del(t2);
  106.             }
  107.             else if(t2==-1)
  108.             {
  109.                 ans+=x-num[t1];
  110.                 ans%=P;del(t1);
  111.             }
  112.             else
  113.             {
  114.                 if(x-num[t1]>num[t2]-x)
  115.                 {
  116.                     ans+=num[t2]-x;
  117.                     ans%=P;del(t2);
  118.                 }
  119.                 else
  120.                 {
  121.                     ans+=x-num[t1];
  122.                     ans%=P;del(t1);
  123.                 }
  124.             }
  125.         }   
  126.     }
  127.     cout<<ans<<endl;
  128.     return 0;
  129. }

习题

[HNOI2002]营业额统计

题目描述

Tiger 最近被公司升任为营业部经理，他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。Tiger 拿出了公司的账本，账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日，大减价或者是其他情况的时候，营业额会出现一定的波动，当然一定的波动是能够接受的，但是在某些时候营业额突变得很高或是很低，这就证明公司此时的经营状况出现了问题。经济管理学上定义了一种最小波动值来衡量这种情况： 该天的最小波动值。

当最小波动值越大时，就说明营业情况越不稳定。

而分析整个公司的从成立到现在营业情况是否稳定，只需要把每一天的最小波动值加起来就可以了。你的任务就是编写一个程序帮助 Tiger 来计算这一个值。 第一天的最小波动值为第一天的营业额。

输入格式

第一行为正整数，表示该公司从成立一直到现在的天数，接下来的n行每行有一个整数(有可能有负数)，表示第i天公司的营业额。

天数n<=32767，每天的营业额ai <= 1,000,000。

最后结果

输出格式

输出文件仅有一个正整数，即 Sigma (每天最小的波动值)。结果小于 。

样例输入

6
5
1
2
5
4
6

样例输入

12

样例解释

这道题纯属是给大家练手的，因为此题与例题相似而且还要简单，因为对这道题不必想如何统计前面树中的最小值，因为此题是要每个数都要插入的，插入完之后此节点一定是根节点，那么只要取右子树中的最小值和左子树中的最大值与此节点的差值即可。最难的删除操作在此题也不涉及。

唯一的不同点就是这道题的数据不保证没有重复，所以插入的时候如果发现此数值已经在树中就不必插入了。

标准程序 by 张澈

  1. #include<iostream>
  2. #include<cstdio>
  3. #define x node[x_p]
  4. #define y node[y_p]
  5. #define z node[z_p]
  6. #define p node[p_p]
  7. #define u node[u_p]
  8. #define v node[v_p]
  9. #define min(a,b) (a<b?a:b)
  10. using namespace std;
  12. const int MAXN=32767,INF=~0U>>1;
  14. struct splayTree
  15. {
  16.     int root,size;
  17.     struct N
  18.     {
  19.         int lc,rc,fa;
  20.         int val;
  21.         N(){lc=rc=fa=val=0;}
  22.     }node[MAXN+10];int ncnt;
  23.     void lRotate(int x_p)
  24.     {
  25.         int y_p=x.rc;
  26.         x.rc=y.lc;
  27.         if(y.lc) node[y.lc].fa=x_p;
  28.         y.fa=x.fa;
  29.         if(!x.fa) root=y_p;
  30.         else if(x_p==node[x.fa].lc) node[x.fa].lc=y_p;
  31.         else node[x.fa].rc=y_p;
  32.         y.lc=x_p,x.fa=y_p;
  33.     }
  34.     void rRotate(int x_p)
  35.     {
  36.         int y_p=x.lc;
  37.         x.lc=y.rc;
  38.         if(y.rc) node[y.rc].fa=x_p;
  39.         y.fa=x.fa;
  40.         if(!x.fa) root=y_p;
  41.         else if(x_p==node[x.fa].lc) node[x.fa].lc=y_p;
  42.         else node[x.fa].rc=y_p;
  43.         y.rc=x_p,x.fa=y_p;
  44.     }
  45.     void splay(int x_p)
  46.     {
  47.         while(x.fa)
  48.         {
  49.             if(!node[x.fa].fa)
  50.             {
  51.                 if(node[x.fa].lc==x_p) rRotate(x.fa);
  52.                 else lRotate(x.fa);
  53.             }else if(node[x.fa].lc==x_p&&node[node[x.fa].fa].lc==x.fa)
  54.             {
  55.                 rRotate(node[x.fa].fa);
  56.                 rRotate(x.fa);
  57.             }else if(node[x.fa].rc==x_p&&node[node[x.fa].fa].rc==x.fa)
  58.             {
  59.                 lRotate(node[x.fa].fa);
  60.                 lRotate(x.fa);
  61.             }else if(node[x.fa].lc==x_p&&node[node[x.fa].fa].rc==x.fa)
  62.             {
  63.                 rRotate(x.fa);
  64.                 lRotate(x.fa);
  65.             }else
  66.             {
  67.                 lRotate(x.fa);
  68.                 rRotate(x.fa);
  69.             }
  70.         }
  71.     }
  72.     int subtreeMin(int u_p)
  73.     {
  74.         while(u.lc) u_p=u.lc;
  75.         return u_p;
  76.     }
  77.     int subtreeMax(int u_p)
  78.     {
  79.         while(u.rc) u_p=u.rc;
  80.         return u_p;
  81.     }
  82.     splayTree(){root=0,size=0,ncnt=0;}
  83.     int insert(int val)
  84.     {
  85.         int z_p=root;
  86.         int p_p=0;
  87.         while(z_p)
  88.         {
  89.             p_p=z_p;
  90.             if(z.val==val) return 1;
  91.             if(z.val<val) z_p=node[z_p].rc;
  92.             else z_p=node[z_p].lc;
  93.         }
  94.         z_p=++ncnt;
  95.         z.val=val;
  96.         z.fa=p_p;
  97.         if(!p_p) root=z_p;
  98.         else if(p.val<z.val) p.rc=z_p;
  99.         else p.lc=z_p;
  100.         splay(z_p);
  101.         ++size;
  102.         return 0;
  103.     }
  104.     int work(int val)
  105.     {
  106.         if(insert(val)) return 0;
  107.         if(size==1) return val;
  108.         int tmp=subtreeMin(node[root].rc);
  109.         if(!node[root].lc)
  110.             return node[subtreeMin(node[root].rc)].val-val;
  111.         if(!node[root].rc)
  112.             return val-node[subtreeMax(node[root].lc)].val;
  113.         return min(node[subtreeMin(node[root].rc)].val-val,
  114.                 val-node[subtreeMax(node[root].lc)].val);
  115.     }
  116. } spT;
  118. int main()
  119. {
  120.     int i;
  121.     int n;
  122.     int ans=0;
  123.     scanf("%d",&n);
  124.     for(i=1;i<=n;i++)
  125.     {
  126.         int rn;scanf("%d",&rn);
  127.         ans+=spT.work(rn);
  128.     }
  129.     printf("%d\n",ans);
  130.     return 0;
  131. }

Efficient Solutions

题目描述

有 n 个人，每个人有两个属性 x 和 y 。如果对于一个人 ，不存在另外一个人 ，使得 ，或者 ，我们说 P 是有有事的。每次给出一个人的信息，要求输出在只考虑当前一伙的的信息的前提下，多少人是有优势的。

输入格式

输入第一行位测试数据组数 T 。每组数据第一行为整数 n (0<=n<=15000) ，以下 n 行每行两个整数 x,y ，分别为每个人的两个属性（不超过 的非负整数）。

输出格式
对于每组数据，输出获得每条信息后，有优势的人数。

这道题依旧不难，主要思路为：

对于每个人，判断其有没有优势（可通过判断小于他的最大的那个人的 y 坐标是否大于他的 y 坐标）。若没有优势就完事了；若有优势，加入平衡树，并删除所有因其加入而变得没有优势的人（即为横纵坐标都大于他的人）。

有两点需要注意：

本题我还没调完

  1. #include<iostream>
  2. #include<cstdio>
  3. #define x node[x_p]
  4. #define y node[y_p]
  5. #define z node[z_p]
  6. #define p node[p_p]
  7. #define u node[u_p]
  8. #define v node[v_p]
  9. using namespace std;
  11. const int MAXN=1000;
  13. struct P
  14. {
  15.     int a,b;
  16.     bool operator < (const P & ot) const
  17.     {return a<ot.a||(a==ot.a&&b<ot.b);}
  18. };
  20. struct splayTree
  21. {
  22.     int root,size;
  24.     struct N
  25.     {
  26.         int lc,rc,fa;
  27.         P val;
  28.         int num;
  29.         N(){lc=rc=fa=num=0;}
  30.     }node[MAXN+1];int ncnt;
  32.     void lRotate(int x_p)
  33.     {
  34.         int y_p=x.rc;
  35.         x.rc=y.lc;
  36.         if(y.lc) node[y.lc].fa=x_p;
  37.         y.fa=x.fa;
  38.         if(!x.fa) root=y_p;
  39.         else if(x_p==node[x.fa].lc) node[x.fa].lc=y_p;
  40.         else node[x.fa].rc=y_p;
  41.         y.lc=x_p,x.fa=y_p;
  42.     }
  44.     void rRotate(int x_p)
  45.     {
  46.         int y_p=x.lc;
  47.         x.lc=y.rc;
  48.         if(y.rc) node[y.rc].fa=x_p;
  49.         y.fa=x.fa;
  50.         if(!x.fa) root=y_p;
  51.         else if(x_p==node[x.fa].lc) node[x.fa].lc=y_p;
  52.         else node[x.fa].rc=y_p;
  53.         y.rc=x_p,x.fa=y_p;
  54.     }
  56.     void splay(int x_p)
  57.     {
  58.         while(x.fa)
  59.         {
  60.             if(!node[x.fa].fa)
  61.             {
  62.                 if(node[x.fa].lc==x_p) rRotate(x.fa);
  63.                 else lRotate(x.fa);
  64.             }else if(node[x.fa].lc==x_p&&node[node[x.fa].fa].lc==x.fa)
  65.             {
  66.                 rRotate(node[x.fa].fa);
  67.                 rRotate(x.fa);
  68.             }else if(node[x.fa].rc==x_p&&node[node[x.fa].fa].rc==x.fa)
  69.             {
  70.                 lRotate(node[x.fa].fa);
  71.                 lRotate(x.fa);
  72.             }else if(node[x.fa].lc==x_p&&node[node[x.fa].fa].rc==x.fa)
  73.             {
  74.                 rRotate(x.fa);
  75.                 lRotate(x.fa);
  76.             }else
  77.             {
  78.                 lRotate(x.fa);
  79.                 rRotate(x.fa);
  80.             }
  81.         }
  82.     }
  84.     void replace(int u_p,int v_p)
  85.     {
  86.         if(!u.fa) root=v_p;
  87.         else if(u_p==node[u.fa].lc) node[u.fa].lc=v_p;
  88.         else node[u.fa].rc=v_p;
  89.         if(v_p) v.fa=u.fa;
  90.     }
  92.     splayTree(){root=0,size=0,ncnt=0;}
  94.     void insert(P val)
  95.     {
  96.         int z_p=root;
  97.         int p_p=0;
  98.         while(z_p)
  99.         {
  100.             p_p=z_p;
  101.             if(z.val==val) {++z.num;return;}
  102.             if(z.val<val) z_p=z.rc;
  103.             else z_p=z.lc;
  104.         }
  105.         z_p=++ncnt;
  106.         z.val=val;z.fa=p_p;z.num=1;
  107.         if(!p_p) root=z_p;
  108.         else if(p.val<z.val) p.rc=z_p;
  109.         else p.lc=z_p;
  110.         splay(z_p);
  111.         ++size;
  112.     }
  114.     void erase(int z_p)
  115.     {
  116.         if(!z_p) return;
  117.         if(z.num>1) {--z.num;return;}
  118.         splay(z_p);
  119.         if(!z.lc) replace(z_p,z.rc);
  120.         else if(!z.rc) replace(z_p,z.lc);
  121.         else
  122.         {
  123.             int y_p=subtreeMin(z.rc);
  124.             if(y.fa!=z_p)
  125.             {
  126.                 replace(y_p,y.rc);
  127.                 y.rc=z.rc;
  128.                 node[y.rc].fa=y_p;
  129.             }
  130.             replace(z_p,y_p);   
  131.             y.lc=z.lc;
  132.             node[y.lc].fa=y_p;
  133.         }
  134.         --size;
  135.     }
  136.     int lower(P val)
  137.     {
  138.         int x_p=0,u_p=root;
  139.         while(u_p)
  140.             if(u.val<=val)
  141.             {
  142.                 x_p=u_p;
  143.                 u_p=u.rc;
  144.             }else u_p=u.lc;
  145.         return u_p;
  146.     }
  147.     int upper(P val)
  148.     {
  149.         int x_p=0,u_p=root;
  150.         while(u_p)
  151.             if(u.val>=val)
  152.             {
  153.                 x_p=u_p;
  154.                 u_p=u.lc;
  155.             }else u_p=u.rc;
  156.         return u_p;
  157.     }
  158.     void work(P val)
  159.     {
  160.         int x_p=lower(val);
  161.         if(x.val.b<val.b) return;
  162.         insert(val);
  163.         int y_p=upper(val);
  164.         while(y.val.b>val.b)
  165.         {
  166.             erase(y_p);
  167.             val=y.val;
  168.             y_p=upper(val);
  169.         }
  170.     }
  171.     int getSize() {return size;}
  172. } spT;
  173. int main()
  174. {
  175.     freopen("xt.in","r",stdin);
  176.     freopen("xt.out","w",stdout);
  177.     int T,cNum;
  178.     scanf("%d",&T);
  179.     for(cNum=1;cNum<=T;cNum++)
  180.     {
  181.         if(cNum>1) printf("\n");
  182.         printf("Case #%d:\n",cNum);
  183.         int n;scanf("%d",&n);
  184.         spT=splayTree();
  185.         while(n--)
  186.         {
  187.             int a,b;scanf("%d%d",&a,&b);
  188.             P val=(P){a,b};
  189.             spT.work(val);
  190.             printf("%d\n",spT.getSize());
  191.         }
  192.     }
  193. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注