[HNOI2004]宠物收养所
Doubi Gao3
posted @ 2014年9月12日 21:36
in DataStructure
with tags
Splay
, 2062 阅读
Splay求前驱与后继，然后累加和即可。
书上的Splay求x的前驱与后继需要插入x之后才能求得前驱与后继。删除操作时把x与前驱或者后继删除即可。
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <string>
using namespace std;
typedef int Comparable;
struct Node
{
Node *left, *right;
int element;
Node(int v=0, Node *lt=0, Node *rt=0):element(v),left(lt),right(rt) {}
};
Node *null = new Node();
void rotateWithLeftChild(Node *&t)
{
Node *k = t->left;
t->left = k->right;
k->right = t;
t = k;
}
void rotateWithRightChild(Node *&t)
{
Node *k = t->right;
t->right = k->left;
k->left = t;
t = k;
}
void splay(Node *&t, const Comparable &x)
{
Node *leftTreeMax, *rightTreeMin;
static Node head;
head.left = head.right = null;
leftTreeMax = rightTreeMin = &head;
null->element = x;
for(;;)
{
if(x < t->element)
{
if(x < t->left->element)
rotateWithLeftChild(t);
if(t->left == null) break;
//Link Right
rightTreeMin->left = t;
rightTreeMin = t;
t = t->left;
}
else if(x > t->element)
{
if(x > t->right->element)
rotateWithRightChild(t);
if(t->right == null) break;
//Link left
leftTreeMax->right = t;
leftTreeMax = t;
t = t->right;
}
else break;
}
leftTreeMax->right = t->left;
rightTreeMin->left = t->right;
t->left = head.right;
t->right = head.left;
}
int insert(Node *&root, const Comparable &x)
{
Node* newNode = new Node(x);
if(root == null)
{
newNode->left = newNode->right = null;
root = newNode;
return 0;
}
splay(root, x);
if(x < root->element)
{
newNode->left = root->left;
newNode->right = root;
root->left = null;
root = newNode;
}
else if(x > root->element)
{
newNode->right = root->right;
newNode->left = root;
root->right = null;
root = newNode;
}
else return -1;
newNode = NULL;
return 1;
}
void printTree(Node *o)
{
if(o != null)
{
printf("%d ", o->element);
printTree(o->left);
printTree(o->right);
}
}
void remove(Node *&o, int x)
{
splay(o, x);
if(o->element != x) return ;
Node *newTree;
if(o->left == null)
newTree = o->right;
else
{
newTree = o->left;
splay(newTree, x);
newTree->right = o->right;
}
delete o;
o = newTree;
}
Node *findMin(Node *o)
{
if(o == null) return null;
while(o->left != null)
o = o->left;
return o;
}
Node *findMax(Node *o)
{
if(o == null) return null;
while(o->right != null)
o = o->right;
return o;
}
Node *predecessor(Node *o, int x)
{
splay(o, x);
return findMax(o->left);
}
Node *successor(Node *o, int x)
{
return findMin(o->right);
}
///////////////////////
int n;
const int INF = 0x3f3f3f3f;
void readint(int &x)
{
char c = getchar();
while(!isdigit(c)) c = getchar();
x = 0;
while(isdigit(c))
{
x = x*10+c-'0';
c = getchar();
}
}
int main()
{
while(~scanf("%d", &n))
{
Node *root = null; root->left = null; root->right = null;
int ans = 0, flag = -1;
for(int i = 1; i <= n; i++)
{
int cmd, x; scanf("%d%d", &cmd, &x);
if(flag == -1)
{
insert(root, x);
flag = cmd;
}
else if(flag == cmd)
{
insert(root, x);
}
else
{
int p = insert(root, x);
if(p == -1)
{
remove(root, x);
}
else
{
Node *pre = predecessor(root, x);
Node *next = successor(root, x);
int t1 = pre != null? pre->element:INF;
int t2 = next != null? next->element:INF;
if(abs(t1-x) <= abs(t2-x))
{
ans = (ans+abs(t1-x))%1000000;
remove(root, t1);
remove(root, x);
}
else
{
ans = (ans+abs(t2-x))%1000000;
remove(root, t2);
remove(root, x);
}
}
if(root == null) flag = -1;
}
}
printf("%d\n", ans%1000000);
}
return 0;
}
2018年11月01日 21:38
nice blog
2022年9月09日 22:31 Social Study is most important students to all students of AP 10th Class, here we have provided the study material with solved question bank for all government and private school TM, EM, UM and HM students in chapter wise from past years old exams and we have provided the AP 10th Social Model Paper 2023 Pdf suggested by subject experts. AP 10th Social Model Paper All BSEAP 10th class regular and private course students can follow the list of chapters under SSC Social Study to practice study material with previous question bank to get a better score in summative assessment (SA) and formative assessment (FA) SA-1, SA-2, FA-1, FA-2, FA-3, FA-4 along with Assignments exams previously called Unit Test-1, Unit Test-2, Unit Test-3, Unit Test-4 and Three Months.
2023年12月26日 20:40
I’m going to read this. I’ll be sure to come back. thanks for sharing. and also This article gives the light in which we can observe the reality. this is very nice one and gives indepth information. thanks for this nice article
2024年1月08日 14:17
i am out of the blue here. I discovered this board and I in discovering It genuinely supportive and it helped me out a ton. I want to introduce something back and help other people, for example, you helped me I think this is an informative post and it is very useful and knowledgeable. therefore. I would like to thank you for the efforts you have made in writing this article.
2024年1月08日 14:48
I am always searching online for articles that can help me. There is obviously a lot to know about this. I think you made some good points in Features also. Keep working, great job! My friend mentioned to me your blog, so I thought I’d read it for myself. Very interesting insights, will be back for more!
2024年1月08日 15:03
Verygood nice paost. I just stumbled upon ayour weblog and wished to say that I’ve really enjoyed surfing around your blog posts. After all I will be subscribing to your feed and I hope you write again very soon!Some times its a pain in the ass to read wh
2024年1月08日 15:18
I think this is an instructive post and it is extremely valuable and proficient. along these lines, I might want to thank you for the endeavors you have made recorded as a hard copy this article. I love the blog. Great post. It is very true, people must learn how to learn before they can learn. lol i know it sounds funny but its very true. .
2024年1月08日 15:23
I would like to thank you for the efforts you have made in writing this article. I am hoping the same best work from you in the future as well. In fact your creative writing abilities has inspired me to start my own BlogEngine blog now. Really the blogging is spreading its wings rapidly. Your write up is a fine example of it.
2024年1月08日 15:34
Hello there, There’s no doubt that your site could be having web browser compatibility problems. Whenever I take a look at your site in Safari, it looks fine however, when opening in Internet Explorer, it has some overlapping issues. I just wanted to provide you with a quick heads up! Aside from that, excellent blog!
2024年1月08日 15:42
I would like to thank you for the efforts you have made in writing this article. I am hoping the same best work from you in the future as well. In fact your creative writing abilities has inspired me to start my own BlogEngine blog now. Really the blogging is spreading its wings rapidly. Your write up is a fine example of it.
2024年1月08日 15:52
Yes i am totally agreed with this article and i just want say that this article is very nice and very informative article.I will make sure to be reading your blog more. You made a good point but I can't help but wonder, what about the other side? !!!!!!THANKS!!!!! ntegrate AI-driven characters and dialogues to enhance user experiences in gaming applications
2024年1月08日 16:03
I was very pleased to find this site.I wanted to thank you for this great read!! I definitely enjoying every little bit of it and I have you bookmarked to check out new stuff you post.So luck to come across your excellent blog. Your blog brings me a great deal of fun.. Good luck with the site.
2024年1月08日 16:09
I just want to tell you that I am very new to blogging and definitely savored your page. Very likely I’m want to bookmark your website . You certainly have incredible articles. Thanks a bunch for revealing your web site.Appreciate it. Plenty of postings! https://canadiantoprxstore.com/# canada pharmacies without script
2024年1月08日 16:14
In each article on our website, product reviews are always placed real reviews, positive and negative about a particular product, as well as links to authoritative sources, where customer feedback is left and recommendations of doctors, experts and specialists in the field of medicine, cosmetology and pharmaceutics are present
2024年1月08日 16:25
We are playground guard without advertising agency of Toto site.Please come to Playground Guard and enjoy betting on various sites such as Toto Site Safety Playground and Major Playground.The list of sites posted on our safe playground list is a list of sites where our watchdog has completed currency exchange and betting checks with multiple accounts for at least one month. is.
2024年1月08日 16:30
Everyone loves many of the discussions, I actually experienced, I'd prefer additional information in regards to this, for the reason that it is awesome., With thanks to get spreading Why not remain this unique amazing give good results not to mention I just await further with the fantastic blog posts
2024年1月08日 16:31
I just want to tell you that I am very new to blogging and definitely savored your page. Very likely I’m want to bookmark your website . You certainly have incredible articles. Thanks a bunch for revealing your web site.Appreciate it. Plenty of postings! https://canadiantoprxstore.com/# canada pharmacies without script
2024年1月08日 16:53
I would like to thank you for the efforts you have made in writing this article. I am hoping the same best work from you in the future as well. In fact your creative writing abilities has inspired me to start my own BlogEngine blog now. Really the blogging is spreading its wings rapidly. Your write up is a fine example of it.
2024年1月08日 16:59
The next time I read a blog, I hope that it doesnt disappoint me as much as this one. I mean, I know it was my choice to read, but I actually thought youd have something interesting to say. All I hear is a bunch of whining about something that you could fix if you werent too busy looking for attention.
2024年1月08日 17:02
I was very pleased to find this site.I wanted to thank you for this great read!! I definitely enjoying every little bit of it and I have you bookmarked to check out new stuff you post.So luck to come across your excellent blog. Your blog brings me a great deal of fun.. Good luck with the site.
2024年1月08日 17:14
I am always searching online for articles that can help me. There is obviously a lot to know about this. I think you made some good points in Features also. Keep working, great job! My friend mentioned to me your blog, so I thought I’d read it for myself. Very interesting insights, will be back for more!
2024年1月08日 17:15
I am always searching online for articles that can help me. There is obviously a lot to know about this. I think you made some good points in Features also. Keep working, great job! My friend mentioned to me your blog, so I thought I’d read it for myself. Very interesting insights, will be back for more!
2024年1月08日 17:21
Everyone loves many of the discussions, I actually experienced, I'd prefer additional information in regards to this, for the reason that it is awesome., With thanks to get spreading Why not remain this unique amazing give good results not to mention I just await further with the fantastic blog posts
2024年1月08日 17:25
First off I want to say excellent blog! I had a quick question in which I’d like to ask if you don’t mind. I was curious to know how you center yourself and clear your thoughts before writing. I’ve had a tough time clearing my thoughts in getting my ideas out. I truly do take pleasure in writing but it just seems like the first 10 to 15 minutes tend to be lost just trying to figure out how to begin. Any ideas or hints? Appreciate it!
2024年1月08日 17:39
I would like to thank you for the efforts you have made in writing this article. I am hoping the same best work from you in the future as well. In fact your creative writing abilities has inspired me to start my own BlogEngine blog now. Really the blogging is spreading its wings rapidly. Your write up is a fine example of it.
2024年1月08日 17:47
Nice blog right here! Additionally your website loads up fast! What web host are you the use of? Can I get your associate hyperlink in your host? I desire my web site loaded up as quickly as yours I feel a lot more people need to read this, very good info
2024年1月08日 17:50
We are playground guard without advertising agency of Toto site.Please come to Playground Guard and enjoy betting on various sites such as Toto Site Safety Playground and Major Playground.The list of sites posted on our safe playground list is a list of sites where our watchdog has completed currency exchange and betting checks with multiple accounts for at least one month. is.
2024年1月08日 17:58
I would like to thank you for the efforts you have made in writing this article. I am hoping the same best work from you in the future as well. In fact your creative writing abilities has inspired me to start my own BlogEngine blog now. Really the blogging is spreading its wings rapidly. Your write up is a fine example of it.
2024年1月08日 18:02
First off I want to say excellent blog! I had a quick question in which I’d like to ask if you don’t mind. I was curious to know how you center yourself and clear your thoughts before writing. I’ve had a tough time clearing my thoughts in getting my ideas out. I truly do take pleasure in writing but it just seems like the first 10 to 15 minutes tend to be lost just trying to figure out how to begin. Any ideas or hints? Appreciate it!
2024年1月08日 18:10
i am out of the blue here. I discovered this board and I in discovering It genuinely supportive and it helped me out a ton. I want to introduce something back and help other people, for example, you helped me I think this is an informative post and it is very useful and knowledgeable. therefore. I would like to thank you for the efforts you have made in writing this article.
2024年1月08日 18:20
It's strikingly a marvelous and satisfying piece of information. I am satisfied that you in a general sense enabled this strong data to us. On the off chance that it's not all that much burden stay us sway forward thusly. Thankful to you for sharing
2024年1月08日 18:25
Confusing information, immense and outlandish structure, as offer especially finished with sharp examinations and thoughts, heaps of striking information and inspiration, the two of which I require, because of offer such an incredible information here
2024年1月08日 18:32
This is extremely intriguing substance! I have altogether delighted in perusing your focuses and have arrived at the resolution that you are ideal about a significant number of them. You are extraordinary What a good blog you have here. Please update it more often. This topics is my interest. Thank you. . .
2024年1月08日 18:40
Confusing information, immense and outlandish structure, as offer especially finished with sharp examinations and thoughts, heaps of striking information and inspiration, the two of which I require, because of offer such an incredible information here
2024年1月08日 18:51
Fantastic beat ! I would like to apprentice at the same time as you amend your web site, how can i subscribe for a blog web site? The account aided me a acceptable deal. I were a little bit acquainted of this your broadcast offered brilliant transparent idea|
2024年1月08日 18:54
My spouse and am enjoy your blog and locate the vast majority of your post’s to be able to be what exactly I’m searching for. can you present guest writers to compose content for you? We wouldn’t mind producing the post or elaborating upon some the subjects jots down concerning here. Once again, awesome weblog!
2024年1月08日 19:04
Awesome site you have here but I was curious if you knew of any message boards that cover the same topics talked about here? I’d really like to be a part of group where I can get opinions from other experienced people that share the same interest. If you have any suggestions, please let me know. Bless you!
2024年1月08日 19:09
Verygood nice paost. I just stumbled upon ayour weblog and wished to say that I’ve really enjoyed surfing around your blog posts. After all I will be subscribing to your feed and I hope you write again very soon!Some times its a pain in the ass to read wh
2024年1月08日 19:16
Fantastic beat ! I would like to apprentice at the same time as you amend your web site, how can i subscribe for a blog web site? The account aided me a acceptable deal. I were a little bit acquainted of this your broadcast offered brilliant transparent idea|
2024年1月20日 14:38
I want you to thank for your time of this wonderful read!!
2024年1月20日 15:38
definitely enjoying every little bit of it. It is a great website and nice share. I want to thank you. Good job! You guys do a great blog, and have some great contents. Keep up the good work
2024年1月20日 16:09
You have performed a great job on this article. It’s very precise and highly qualitative. You have even managed to make it readable and easy to read. You have some real writing talent. Thank you so muc
2024年1月20日 16:55
Your blog has chock-a-block of useful information. I liked your blog's content as well as its look. In my opinion, this is a perfect blog in all aspects.
2024年1月20日 17:11
Thanks for the valuable information and insights you have so provided here
2024年1月20日 17:43
Great articles and great layout. Your blog post deserves all of the positive feedback it's been getting.
2024年1月20日 18:22
Thanks for the valuable information and insights you have so provided here
2024年1月20日 19:15
I think that thanks for the valuabe information and insights you have so provided here
2024年1月20日 19:56
Appreciating the time and energy you put into your website and detailed information you present. It’s great to come across a blog every once in a while that isn’t the same outdated rehashed information. Excellent read!
2024年1月20日 20:34
Hi buddies, it is great written piece entirely defined, continue the good work constantl
2024年1月20日 21:06
very interesting keep posting.
2024年1月21日 13:30
It proved to be Very helpful to me and I am sure to all the commentators here!
2024年1月21日 14:01
Interesting and amazing how your post is! It Is Useful and helpful for me That I like it very much, and I am looking forward to Hearing from your next..
2024年1月21日 15:48
Wow, this is really interesting reading. I am glad I found this and got to read it. Great job on this content. I like it.
2024年1月21日 16:33
"Appreciating the dedication you put into your blog and detailed information you provide.
It’s awesome to come across a blog every once in a
while that isn’t the same old rehashed material. Fantastic read!"
2024年1月24日 19:39
Hi there, I discovered your blog per Google bit searching for such kinda educational advise moreover your inform beholds very remarkable for me.
2024年1月26日 12:24
하노이 꼭 가봐야 할 베스트 업소 추천 안내 및 예약, 하노이 밤문화 에 대해서 정리해 드립니다. 하노이 가라오케, 하노이 마사지, 하노이 풍선바, 하노이 밤문화를 제대로 즐기시기 바랍니다. 하노이 밤문화 베스트 업소 요약 베스트 업소 추천 및 정리.
2024年1月26日 12:27
카지노사이트 바카라사이트 우리카지노 카지노는 바카라, 블랙잭, 룰렛 및 슬롯 등 다양한 게임을 즐기실 수 있는 공간입니다. 게임에서 승리하면 큰 환호와 함께 많은 당첨금을 받을 수 있고, 패배하면 아쉬움과 실망을 느끼게 됩니다.
2024年1月29日 11:35
No.1 먹튀검증 사이트, 먹튀사이트, 검증사이트, 토토사이트, 안전사이트, 메이저사이트, 안전놀이터 정보를 제공하고 있습니다. 먹튀해방으로 여러분들의 자산을 지켜 드리겠습니다. 먹튀검증 전문 커뮤니티 먹튀클린만 믿으세요!!
2024年1月29日 11:41
베트남 남성전용 커뮤니티❣️ 베트남 하이에나 에서 베트남 밤문화를 추천하여 드립니다. 베트남 가라오케, 베트남 VIP마사지, 베트남 이발관, 베트남 황제투어 남자라면 꼭 한번은 경험 해 봐야할 화끈한 밤문화로 모시겠습니다.