SBT -- poj2828
source link: http://abcdxyzk.github.io/blog/2012/01/16/alg-sbt/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
SBT -- poj2828
2012-01-16 21:34:00
#include <stdio.h>
#include <algorithm>
#include <iostream>
#define N 4000005
using namespace std;
int tol=0;
struct SBT
{
int left,right;
int key;
int size;
void init()
{
left=right=0;
size=1;
}
}T[N];
void R_Rotate(int &t)//右旋
{
int k=T[t].left;
T[t].left=T[k].right;
T[k].right=t;
T[k].size=T[t].size;
T[t].size=T[T[t].left].size+T[T[t].right].size+1;
t=k;
return ;
}
void L_Rotate(int &t)//左旋
{
int k=T[t].right;
T[t].right=T[k].left;
T[k].left=t;
T[k].size=T[t].size;
T[t].size=T[T[t].left].size+T[T[t].right].size+1;
t=k;
}
void Maintain(int &t,bool flag)//维护，SBT精华之所在
{
if(flag==false)
{
if(T[T[T[t].left].left].size>T[T[t].right].size)
R_Rotate(t);
else if(T[T[T[t].left].right].size>T[T[t].right].size)
{
L_Rotate(T[t].left);
R_Rotate(t);
}
else
return ;
}
else
{
if(T[T[T[t].right].right].size>T[T[t].left].size)
L_Rotate(t);
else if(T[T[T[t].right].left].size>T[T[t].left].size)
{
R_Rotate(T[t].right);
L_Rotate(t);
}
else
return ;
}
Maintain(T[t].left,false);
Maintain(T[t].right,true);
Maintain(t,false);
Maintain(t,true);
}
void Insert(int &t,int v)//插入
{
if(t==0)
{
t=++tol;
T[t].init();
T[t].key=v;
}
else
{
T[t].size++;
if(v<T[t].key)
Insert(T[t].left,v);
else
Insert(T[t].right,v);
Maintain(t,v>=T[t].key);
}
}
int Delete(int &t,int v)//删除
{
if(!t)
return 0;
T[t].size--;
if(v==T[t].key||v<T[t].key&&!T[t].left||v>T[t].key&&!T[t].right)
{
if(T[t].left&&T[t].right)
{
int p=Delete(T[t].left,v+1);
T[t].key=T[p].key;
return p;
}
else
{
int p=t;
t=T[t].left+T[t].right;
return p;
}
}
else
return Delete(v<T[t].key?T[t].left:T[t].right,v);
}
int Find_k(int t,int k)//找出第k大数
{
if(k<=T[T[t].left].size)
return Find_k(T[t].left,k);
else if(k>T[T[t].left].size+1)
return Find_k(T[t].right,k-T[T[t].left].size-1);
return T[t].key;
}
int Getmin(int t)//取最小值
{
while(T[t].left)
t=T[t].left;
return t;
}
int Getmax(int t)//取最大值
{
while(T[t].right)
t=T[t].right;
return t;
}
int Rank(int t,int key)//排名其实就是它的左子树的size+1
{
if(t==0)
return 0;
if(key<=T[t].key)
return Rank(T[t].left,key);
else
return T[T[t].left].size+1+Rank(T[t].right,key);
}
int eRank(int t,int key)//倒过来排名
{
if(t==0)
return 0;
if(key>=T[t].key)
return eRank(T[t].right,key);
else
return T[T[t].right].size+1+eRank(T[t].left,key);
}
int Exist(int t,int x)//判断这个节点是否存在
{
if(t==0)
return 0;
if(x<T[t].key)
return Exist(T[t].left,x);
else if(x==T[t].key)
return 1;
else
return Exist(T[t].right,x);
}
int Count(int t,int x)//统计出现次数
{
if(!Exist(t,x))
return 0;
else
return Rank(t,x+1)-Rank(t,x);
}
int Pred(int t,int v)//返回比v小的最大的数
{
if(t==0)
return v;
else if(v>T[t].key)
{
int ret=Pred(T[t].right,v);
if(ret==v)
return T[t].key;
return ret;
}
else
return Pred(T[t].left,v);
}
int Succ(int t,int v)//返回比v大的最小的数
{
if(t==0)
return v;
else if(v<T[t].key)
{
int ret=Succ(T[t].left,v);
if(ret==v)
return T[t].key;
return ret;
}
else
return Succ(T[t].right,v);
}
////////////////////////
int n,m, a[200009], b[200009], c[200009];
void dfs(int root)
{
if(root == 0) return;
dfs(T[root].left);
if(m > 0) printf(" ");
printf("%d", T[root].key);
m++;
dfs(T[root].right);
}
int main()
{
int i,j,k;
int root;
while(scanf("%d", &n) != EOF)
{
tol = 0;
root = 0;
for(i=1;i<=n;i++)
{
scanf("%d %d", &a[i], &b[i]);
Insert(root, i);
}
for(i=n;i>0;i--)
{
k = Find_k(root, a[i]+1);
c[k] = b[i];
Delete(root, k);
}
for(i=1;i<n;i++) printf("%d ", c[i]);
printf("%d\n", c[i]);
m = 0;
dfs(root);
}
return 0;
}Recommend
-
94
在Maven核心概念一文中提到，最近的项目中使用了akka与scala，因此选择sbt（Simple Build Tool）做为项目的构建工具。在sbt之前也使用过很多的构建工具，但是sbt是我至今遇到的最复杂的一个，这和它名字里的Simple完全搭不上边。在我看来，sbt的复杂主要在两个方面...
-
33
本来不太想使用sbt，但是公司这边普遍要求使用sbt来进行部署。所以，so！ sbt的语法什么的还好，唯一让人无法忍受的是sbt下载依赖的速度 —— 在国内大环境下实在是慢到了让人抓狂的程度。 要提升sbt下载依赖的速度，方法...
-
11
Dummy Guide to sbt Table of Contents Why sbt In Scala Survey 2019 there was a question: What are the *other pai...
-
10
So, what's wrong with SBT? Posted 2017-11-19SBT is the default build tool for the Scala programming community: you can bu...
-
9
Provisioning a VM with Scala and SBT So I’ve been giving a little more time and attention to both Scala and Vagrant. Vagrant is a nice way to manage development environments via the use of VM’s and Scala, of course, is a great hy...
-
4
POJ2828 Buy Tickets（树状数组高级应用：sumseek）March 06, 2016题目链接 题意：n 个人排队，接下来 n 行每行第一个数是这个人的位置，第二个数是他的 value（没卵用）。后来的人如果他...
-
7
How can I use an SBT key to view the current configuration? advertisements I have the following build.sbt file: ve...
-
7
SBT console to debug application Reading Time: 2 minutesIn this blog post, We will know how to debug application via sbt c...
-
3
Reading Time: 3 minutes In this post, we are going to look into reading sbt dependency tree and resolving one of the scenario using an example.
-
9
Reading Time: 3 minutes Scoverage… what it is, how to use it and for which build tool it is available. So, In this blog we are gonna discussing all these along with its implementation in SBT. What...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK