 |
| ||||
Home Page
F.A.Qs
Statistical Charts
Past Contests
Scheduled Contests
Award Contest
| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
再给一个这个问题的伸展树版本吧，好像很搓。。。。5S多过的。。还是SBT强啊。。In Reply To:感谢陈启峰大牛的Size Balanced Tree，贴AC代码，顺便放出模板~~~大家共享吧 Posted by:yzhw at 2009-09-26 13:36:25 Source Code
Problem: 2761 User: yzhw
Memory: 3952K Time: 5954MS
Language: G++ Result: Accepted
Source Code
# include <iostream>
using namespace std;
# include <cstdio>
# include <cstring>
# include <cstdlib>
template <typename key_type>
class SplayTree
{
public:
SplayTree()
{
nil = new node;
nil->size = 0;
nil->lchild = nil;
nil->rchild = nil;
root = nil;
}
~SplayTree()
{
clear();
delete nil;
}
void clear()
{
while (root != nil)
erase(maximum());
}
void erase(const key_type &x);
const key_type &maximum()
{
node *p = root;
while (p->rchild != nil)
p = p->rchild;
splay(root, p->key);
return p->key;
}
const key_type &minimum()
{
node *p = root;
while (p->lchild != nil)
p = p->lchild;
splay(root, p->key);
return p->key;
}
void insert(const key_type &x);
const key_type &select(int rank);
private:
struct node
{
key_type key;
int size;
node *lchild, *rchild;
node() {}
node(const key_type &x) : key(x) {}
}*nil, *root;
void splay(node *&root, const key_type &x);
void splay2(node *&root);
};
template <typename key_type>
void SplayTree<key_type>::erase(const key_type &key)
{
if (root == nil) throw "not found";
splay(root, key);
if (root->key != key) throw "not found";
node *new_root;
int size = root->size;
if (root->lchild == nil)
new_root = root->rchild;
else
{
new_root = root->lchild;
splay2(new_root); //If key < key+1, it is equivalent to "splay(new_root, key+1)".
new_root->rchild = root->rchild;
}
new_root->size = root->size-1;
delete root;
root = new_root;
}
template <typename key_type>
void SplayTree<key_type>::insert(const key_type &key)
{
node *new_root = new node(key);
if (root == nil)
{
new_root->size = 1;
new_root->lchild = nil;
new_root->rchild = nil;
root = new_root;
return;
}
splay(root, key);
new_root->size = root->size+1;
if (key < root->key)
{
new_root->lchild = root->lchild;
root->lchild = nil;
new_root->rchild = root;
root->size = root->rchild->size+1;
}
else
{
new_root->rchild = root->rchild;
root->rchild = nil;
new_root->lchild = root;
root->size = root->lchild->size+1;
}
root = new_root;
}
template <typename key_type>
const key_type &SplayTree<key_type>::select(int rank)
{
node *p = root;
for(;;)
{
int pos=(p->lchild?p->lchild->size:0);
if (rank <=pos)
p = p->lchild;
else if (rank>pos+1)
rank -= pos+1, p = p->rchild;
else break;
}
splay(root, p->key);
return p->key;
}
template <typename key_type>
void SplayTree<key_type>::splay(node *&root, const key_type &key)
{
int lsize = 0, rsize = 0;
node head, *ltree = &head, *rtree = &head;
head.lchild = nil;
head.rchild = nil;
for(;;)
{
if (key < root->key)
{
if (root->lchild != nil && key < root->lchild->key)
{
node *p = root->lchild;
root->lchild = p->rchild;
p->rchild = root;
root->size = root->lchild->size+root->rchild->size+1;
root = p;
}
if (root->lchild == nil)
break;
rtree->lchild = root;
rtree = root;
root = root->lchild;
rsize += rtree->rchild->size+1;
}
else if (root->key < key)
{
if (root->rchild != nil && root->rchild->key < key)
{
node *p = root->rchild;
root->rchild = p->lchild;
p->lchild = root;
root->size = root->lchild->size+root->rchild->size+1;
root = p;
}
if (root->rchild == nil)
break;
ltree->rchild = root;
ltree = root;
root = root->rchild;
lsize += ltree->lchild->size+1;
}
else break;
}
lsize += root->lchild->size;
rsize += root->rchild->size;
root->size = lsize+rsize+1;
ltree->rchild = nil;
rtree->lchild = nil;
for (node *p = head.rchild; p != nil; p = p->rchild)
{
p->size = lsize;
lsize -= p->lchild->size+1;
}
for (node *p = head.lchild; p != nil; p = p->lchild)
{
p->size = rsize;
rsize -= p->rchild->size+1;
}
ltree->rchild = root->lchild;
root->lchild = head.rchild;
rtree->lchild = root->rchild;
root->rchild = head.lchild;
}
template <typename key_type>
void SplayTree<key_type>::splay2(node *&root)
{
int lsize = 0;
node head, *ltree = &head;
head.lchild = nil;
head.rchild = nil;
for(;;)
{
if (root->rchild != nil)
{
node *p = root->rchild;
root->rchild = p->lchild;
p->lchild = root;
root->size = root->lchild->size+root->rchild->size+1;
root = p;
}
if (root->rchild == nil)
break;
ltree->rchild = root;
ltree = root;
root = root->rchild;
lsize += ltree->lchild->size+1;
}
lsize += root->lchild->size;
root->size = lsize+1;
ltree->rchild = nil;
for (node *p = head.rchild; p != nil; p = p->rchild)
{
p->size = lsize;
lsize -= p->lchild->size+1;
}
ltree->rchild = root->lchild;
root->lchild = head.rchild;
}
//start
struct ques
{
int s,e;
int id;
int q;
int ans;
}list[50001];
int cmp(const void *a,const void *b)
{
ques *aa=(ques *)a;
ques *bb=(ques *)b;
if(aa->s!=bb->s) return aa->s-bb->s;
else return aa->e-bb->e;
}
int cmp1(const void *a,const void *b)
{
ques *aa=(ques *)a;
ques *bb=(ques *)b;
return aa->id-bb->id;
}
int main()
{
SplayTree<int> refer;
int num[100001];
int n,m;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",num+i);
}
for(int i=1;i<=m;i++)
{
scanf("%d %d %d",&list[i].s,&list[i].e,&list[i].q);
list[i].id=i;
}
qsort(list+1,m,sizeof(ques),cmp);
for(int j=list[1].s;j<=list[1].e;j++)
refer.insert(num[j]);
list[1].ans=refer.select(list[1].q);
for(int i=2;i<=m;i++)
{
if(list[i].s>=list[i-1].e)//区间错开
{
for(int j=list[i-1].s;j<=list[i-1].e;j++)
refer.erase(num[j]);
for(int j=list[i].s;j<=list[i].e;j++)
refer.insert(num[j]);
}
else if(list[i].s<=list[i-1].e&&list[i].e>list[i-1].e)//区间部分包含
{
for(int j=list[i-1].e+1;j<=list[i].e;j++)
refer.insert(num[j]);
for(int j=list[i-1].s;j<list[i].s;j++)
refer.erase(num[j]);
}
else //子集
{
for(int j=list[i-1].s;j<list[i].s;j++)
refer.erase(num[j]);
for(int j=list[i].e+1;j<=list[i-1].e;j++)
refer.erase(num[j]);
}
list[i].ans=refer.select(list[i].q);
}
qsort(list+1,m,sizeof(ques),cmp1);
for(int i=1;i<=m;i++)
printf("%d\n",list[i].ans);
return 0;
}
Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator
