注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

一个蒟蒻的代码回收站

最后一次省选求rp

 
 
 

日志

 
 

bzoj1056【HAOI2008】&& bzoj1862【ZJOI2006】排名系统解题报告  

2014-04-01 20:53:00|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1056题目链接1862题目链接

这题基本可以算是1861的加强版吧,支持插入,修改,查询排名及输出某区间。

修改的话就是删除+插入

输出某区间的话,就是把l-1旋转到根,r+1旋转到根的右子树,然后对根的右子树的左子树跑一次中序遍历即可。

这个程序跑的非常慢= =,bzoj上跑了3000+ms,目测是map的问题……有兴趣可以自己写一个hash

#include<cstdio>

#include<cstdlib>

#include<string>

#include<map>

#include<iostream>

using namespace std;

 

#define maxn 260000

int n,m,root=0;

map<string,int> Map;

struct Node

{

   int left,right,fa;

   int num,s;

   string name;

} node[maxn];

string s;

bool flag;

 

inline void newnode(int x,int n)

{

   node[n].left=node[n].right=0;

   node[n].num=x;

   node[n].s=1;

}

void maintain(int x)

{

   node[x].s=1;

   if (node[x].left!=0) node[x].s+=node[node[x].left].s;

   if (node[x].right!=0) node[x].s+=node[node[x].right].s;

}

inline void left_rotate(int x)

{

   int y=node[x].fa;

   if (node[y].fa!=0)

   {

       if (y==node[node[y].fa].left) node[node[y].fa].left=x;

       else node[node[y].fa].right=x;

   }

   node[x].fa=node[y].fa;

   node[y].right=node[x].left;

   if (node[x].left!=0)

       node[node[x].left].fa=y;

   node[y].fa=x;

   node[x].left=y;

   maintain(y);

   maintain(x);

}

inline void right_rotate(int x)

{

   int y=node[x].fa;

   if (node[y].fa!=0)

   {

       if (y==node[node[y].fa].left) node[node[y].fa].left=x;

       else node[node[y].fa].right=x;

   }

   node[x].fa=node[y].fa;

   node[y].left=node[x].right;

   if (node[x].right!=0)

       node[node[x].right].fa=y;

   node[y].fa=x;

   node[x].right=y;

   maintain(y);

   maintain(x);

}

void splay(int x,int s)

{

   int father=node[s].fa;

   while (node[x].fa!=father)

   {

       int p=node[x].fa;

       if (node[p].fa==father)

       {

           if (x==node[p].left) right_rotate(x);

           else left_rotate(x);

           break;

       }

       if (x==node[p].left)

       {

           if (p==node[node[p].fa].left)

           {

               right_rotate(p);

               right_rotate(x);

           } else

           {

               right_rotate(x);

               left_rotate(x);

           }

       } else

       {

           if (p==node[node[p].fa].right)

           {

               left_rotate(p);

               left_rotate(x);

           } else

           {

               left_rotate(x);

               right_rotate(x);

           }

       }

   }

   if (father==0) root=x;

}

void insert(int x,int n)

{

   if (root==0)

   {

       newnode(x,n);

       root=n;

       return;

   }

   int tmp=root,p;

   bool flag;

   while (tmp!=0)

   {

       p=tmp;

       if (node[tmp].num>=x) tmp=node[tmp].right,flag=true;

       else tmp=node[tmp].left,flag=false;

   }

   newnode(x,n);

   if (p!=0)

   {

       node[n].fa=p;

       if (flag) node[p].right=n;else node[p].left=n;

   }

   splay(n,root);

}

inline void erase(int n)

{

   splay(n,root);

   if (!node[root].left && !node[root].right) node[root].fa=0,root=0;else

   if (!node[root].left && node[root].right) node[node[root].right].fa=0,root=node[root].right;else

   if (!node[root].right && node[root].left) node[node[root].left].fa=0,root=node[root].left;else

   {

       int tmp=node[root].left;

       while (node[tmp].right!=0) tmp=node[tmp].right;

       splay(tmp,node[root].left);

       node[node[root].right].fa=node[root].left;

       node[node[root].left].right=node[root].right;

       node[node[root].left].fa=0;

       root=node[root].left;

   }

}

inline int find_x(int t)

{

   splay(t,root);

   return node[node[root].left].s+1;

}

void write(int x)

{

   if (node[x].left!=0) write(node[x].left);

   if (!flag) printf(" ");else flag=false;

   for (int i=0;i<node[x].name.length();i++)

       printf("%c",node[x].name[i]);

   if (node[x].right!=0) write(node[x].right);

}

inline int find(int t)

{

   int tmp=root;

   while (t)

   {

       int q=(node[tmp].left!=0?node[node[tmp].left].s:0)+1;

       if (t==q)   return tmp;else

       if (t<q) tmp=node[tmp].left;else

       if (t>q) t-=q,tmp=node[tmp].right;

   }

}

inline void work(int x,int y)

{

   if (x==1 && y==n)

   {

       write(root);

       cout<<endl;

       return;

   }

   if (x==1 && y<n)

   {

       splay(find(y+1),root);

       write(node[root].left);

       cout<<endl;

       return;

   }

   if (x>1 && y==n)

   {

       splay(find(x-1),root);

       write(node[root].right);

       cout<<endl;

       return;

   }

   splay(find(x-1),root);

   splay(find(y+1),node[root].right);

   write(node[node[root].right].left);

   printf("\n");

   return;

}

int main()

{

   scanf("%d",&m);

   for (int i=1;i<=m;i++)

   {

       char ch=getchar();

       while (ch!='+' && ch!='?') ch=getchar();

       if (ch=='+')

       {

           int x;

           s="";

           char c=getchar();

           while (c!=' ' && c!='\n')

           {

               s+=c;

               c=getchar();

           }

           scanf("%d",&x);

           map<string,int>::iterator it;

           it=Map.find(s);

           if (it==Map.end())

           {

               n++;

               node[n].name=s;

               Map[s]=n;

               insert(x,n);

           } else

           {

               erase(Map[s]);

               insert(x,Map[s]);

           }

       }

       if (ch=='?')

       {

           int x=0;

           s="";

           char c=getchar();

           while (c!=' ' && c!='\n')

           {

               s+=c;

               c=getchar();

           }

           if (s[0]<='9' && s[0]>='0')

           {

               flag=true;

               for (int j=0;j<s.length();j++)

               x=x*10+s[j]-'0';

               int y=x+9;

               if (y>n) y=n;

               work(x,y);

           } else

               printf("%d\n",find_x(Map[s]));

       }

   }

   return 0;

}


  评论这张
 
阅读(1)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018