相关链接
题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1895
数据生成器：http://paste.ubuntu.com/24163947/
神犇题解：http://blog.csdn.net/willinglive/article/details/41488487
原题链接：http://poj.org/problem?id=3580
解题报告
这就是个操作比较全的Splay的板
然而这个上一次写Splay是去年这时候的纸张写了一个下午，调了一个晚上QwQ
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int INF = 0x7fffffff;
const int N = 200009;
inline int read() {
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}
class Splay{
struct Node{int ch[2],val,mn,sz,fa,delta,rev;}p[N]; int cnt;
public:
inline Splay() {
cnt = 2; p[1].ch[1] = 2;
p[1].val = p[1].mn = INF;
p[2].val = p[2].mn = INF;
p[1].sz = 2; p[2].sz = 1;
p[1].fa = p[2].fa = 1;
}
inline void insert(int pos, int v) { ++pos;
int w; splay(w=rank(1, pos), 1);
int nw; splay(nw=rank(1, pos+1), w);
p[nw].ch[0] = ++cnt; p[cnt].fa = nw;
p[cnt].mn = p[cnt].val = v; p[cnt].sz = 1;
maintain(nw); maintain(w); maintain(1);
}
inline void add(int l, int r, int v) { ++l; ++r;
int w; splay(w=rank(1, l-1), 1);
int nw; splay(nw=rank(1, r+1), w);
p[p[nw].ch[0]].delta += v;
PushDown(p[nw].ch[0]); maintain(nw);
maintain(w); maintain(1);
}
inline int query(int l, int r) { ++l; ++r;
int w; splay(w=rank(1, l-1), 1);
int nw; splay(nw=rank(1, r+1), w);
return PushDown(p[nw].ch[0]), p[p[nw].ch[0]].mn;
}
inline void remove(int r) { ++r;
int w; splay(w=rank(1, r-1), 1);
int nw; splay(nw=rank(1, r+1), w);
p[nw].ch[0] = 0; maintain(nw);
maintain(w); maintain(1);
}
inline void reverse(int l, int r) { ++l; ++r;
int w; splay(w=rank(1, l-1), 1);
int nw; splay(nw=rank(1, r+1), w);
p[p[nw].ch[0]].rev ^= 1;
}
inline void Rotate(int l, int r, int t) {
if (l==r||!(t%=((++r) - (++l) + 1))) return;
int w; splay(w=rank(1, l-1), 1);
int nw; splay(nw=rank(1, r+1), w);
int nnw; splay(nnw=rank(p[nw].ch[0], r-l-t+1), nw);
int nnnw; splay(nnnw=rank(p[nnw].ch[1], t), nnw);
p[nw].ch[0] = nnnw; p[nnnw].ch[1] = nnw; p[nnw].ch[1] = 0;
p[nnw].fa = nnnw; p[nnnw].fa = nw;
maintain(nnw); maintain(nnnw);
}
inline void build(int r) {
build(p[2].ch[0], 2, 1, r);
}
private:
inline void PushDown(int w) {
if (p[w].delta) {
p[w].mn += p[w].delta; p[w].val += p[w].delta;
p[p[w].ch[1]].delta += p[w].delta;
p[p[w].ch[0]].delta += p[w].delta;
p[w].delta = 0;
}
if (p[w].rev) {
swap(p[w].ch[0], p[w].ch[1]); p[w].rev = 0;
p[p[w].ch[0]].rev ^= 1; p[p[w].ch[1]].rev ^= 1;
}
}
inline void maintain(int w) {
p[w].mn = p[w].val; p[w].sz = p[p[w].ch[0]].sz + p[p[w].ch[1]].sz + 1;
if (p[w].ch[0]) PushDown(p[w].ch[0]), p[w].mn = min(p[w].mn, p[p[w].ch[0]].mn);
if (p[w].ch[1]) PushDown(p[w].ch[1]), p[w].mn = min(p[w].mn, p[p[w].ch[1]].mn);
}
inline void rotate(int w) {
int f=p[w].fa,t=p[f].ch[1]==w,ff=p[f].fa;
p[f].ch[t] = p[w].ch[t^1]; p[p[w].ch[t^1]].fa = f;
p[w].ch[t^1] = f; p[w].fa = p[f].fa; p[f].fa = w;
if (ff != f) p[ff].ch[p[ff].ch[1]==f] = w;
maintain(f); maintain(w);
}
inline void splay(int w, int pur) {
if (w == pur) return;
for (int f,ff;f=p[w].fa,p[w].fa!=pur;) {
((ff=p[f].fa) == pur)? rotate(w):
(((p[f].ch[1]==w)^(p[ff].ch[1]==f))?rotate(w),rotate(f):rotate(f),rotate(w));
}
}
int rank(int w, int t) {
PushDown(w); if (t<=0) return w; int szt = p[p[w].ch[0]].sz;
if (szt >= t) return rank(p[w].ch[0], t);
else if (szt + 1 == t) return w;
else return rank(p[w].ch[1], t-1-szt);
}
void build(int &w, int f, int l, int r) {
int mid = l + r >> 1; p[w=++cnt].fa = f; p[w].sz = 1; p[w].mn = INF;
if (l < mid) build(p[w].ch[0], w, l, mid-1), p[w].sz += p[p[w].ch[0]].sz, p[w].mn = min(p[w].mn, p[p[w].ch[0]].mn);
p[w].mn = min(p[w].mn, p[w].val = read());
if (mid < r) build(p[w].ch[1], w, mid+1, r), p[w].sz += p[p[w].ch[1]].sz, p[w].mn = min(p[w].mn, p[p[w].ch[1]].mn);
}
}SP;
int main() {
int n = read(); char opt[10]; SP.build(n);
for (int m=read(),l,r,x;m;--m) {
scanf("%s",opt+1);
if (opt[1] == 'A') {
l = read(); r = read();
SP.add(l, r, read());
} else if (opt[1] == 'R' && opt[4] == 'E') {
l = read(); r = read();
SP.reverse(l, r);
} else if (opt[1] == 'R') {
l = read(); r = read();
SP.Rotate(l, r, read());
} else if (opt[1] == 'I') {
l = read(); r = read();
SP.insert(l, r);
} else if (opt[1] == 'D') {
SP.remove(read());
} else {
l = read(); r = read();
printf("%d\n",SP.query(l,r));
}
}
return 0;
}
Excellent blog you have got here.. It’s difficult to find excellent writing like yours these days.
I truly appreciate individuals like you! Take care!!
Hey there! I’ve been following your site for a long time now and finally got the courage to go ahead and give you a shout out from Huffman Tx!
Just wanted to tell you keep up the great job!
Hello there! Quick question that’s completely off topic.
Do you know how to make your site mobile friendly? My weblog looks
weird when viewing from my iphone4. I’m trying to find a template or plugin that might be able to correct this problem.
If you have any suggestions, please share. Many thanks!
I blog often and I seriously thank you for your
information. The article has truly peaked my interest. I’m going to bookmark your site and
keep checking for new information about once
a week. I subscribed to your RSS feed too.
Greetings! Very helpful advice within this post!
It’s the little changes that produce the most important changes.
Thanks for sharing!
What’s up Dear, are you actually visiting this web site daily, if
so after that you will without doubt take pleasant experience.
Appreciating the commitment you put into your website and detailed
information you provide. It’s great to come across a blog every once in a while that isn’t the same outdated rehashed information. Wonderful read!
I’ve saved your site and I’m including your RSS feeds to my Google account.
Whats up this is kinda of off topic but I was wondering if blogs use WYSIWYG editors or if you have to manually code with HTML.
I’m starting a blog soon but have no coding knowledge so I wanted to
get guidance from someone with experience. Any help would be greatly
appreciated!
These are really fantastic ideas in regarding blogging.
You have touched some fastidious factors here.
Any way keep up wrinting.
This is really interesting, You’re a very skilled blogger.
I’ve joined your feed and look forward to seeking more of your fantastic post.
Also, I’ve shared your website in my social networks!
My partner and I stumbled over here coming from a different web
address and thought I might check things out. I like what I
see so now i am following you. Look forward to exploring your web
page again.
Hey there would you mind letting me know which webhost you’re using?
I’ve loaded your blog in 3 different browsers and I must say this blog loads a lot
faster then most. Can you suggest a good web hosting provider at
a fair price? Many thanks, I appreciate it!
Wohh just what I was searching for, thanks for posting.
May I simply say what a relief to discover a person that genuinely
understands what they are discussing on the net. You actually realize how to bring a problem to light and make it important.
More people have to read this and understand this side of the story.
It’s surprising you’re not more popular given that you certainly possess the gift.
Hi to every , because I am truly eager of reading this web site’s
post to be updated on a regular basis. It carries pleasant information.
Great web site you have here.. It’s difficult to find high-quality writing like yours
nowadays. I really appreciate people like you! Take care!!
I absolutely love your blog and find the majority of your post’s to be exactly what I’m looking
for. can you offer guest writers to write content for you?
I wouldn’t mind composing a post or elaborating on a few of the subjects you write regarding here.
Again, awesome web site!
I visited multiple websites but the audio quality for audio songs existing
at this web page is truly marvelous.
It’s really very complicated in this full of activity life to listen news on Television, therefore I
only use world wide web for that reason, and obtain the newest news.
What a stuff of un-ambiguity and preserveness of valuable knowledge concerning unpredicted feelings.
I do not even know how I ended up right here, however I believed this submit
used to be good. I do not know who you might be however definitely you’re going
to a famous blogger if you happen to aren’t already. Cheers!
I’m amazed, I must say. Rarely do I encounter a blog
that’s both equally educative and interesting, and without a doubt, you have hit the nail on the head.
The problem is something not enough men and women are speaking intelligently about.
Now i’m very happy that I stumbled across this in my search for
something regarding this.
For the reason that the admin of this web page is working,
no uncertainty very rapidly it will be renowned, due to its
feature contents.
Wow, incredible blog layout! How long have you been blogging for? you made blogging look easy. The overall look of your site is wonderful, let alone the content!