splay真的是一种十分耐吃的植物。啃了三四天终于啃熟了 orz
当然现在还仅限于模板题T T 很多东西还是要努力啊!!!
debug的过程真的是十分的艰辛orz 找了毕克大魔王他说叫我再想想QAQ。。。。。。。。。
好吧反正最终!还是顺利地完成了!两道题都是写了三遍代码啊我已经快上瘾了!!!!(虽然依旧写的丑orz)
然后两道题都写了treap版 = = 都比splay慢不知道为什么。。。
SuperMemo
Time Limit: 5000MS Memory Limit: 65536KTotal Submissions: 10493 Accepted: 3332
Case Time Limit: 2000MS
Description
Your friend, Jackson is invited to a TV show called SuperMemo in which the participant is told to play a memorizing game. At first, the host tells the participant a sequence of numbers, {A1, A2, ... An}. Then the host performs a series of operations and queries on the sequence which consists:
ADD x y D: Add D to each number in sub-sequence {Ax ... Ay}. For example, performing "ADD 2 4 1" on {1, 2, 3, 4, 5} results in {1, 3, 4, 5, 5}
REVERSE x y: reverse the sub-sequence {Ax ... Ay}. For example, performing "REVERSE 2 4" on {1, 2, 3, 4, 5} results in {1, 4, 3, 2, 5}
REVOLVE x y T: rotate sub-sequence {Ax ... Ay} T times. For example, performing "REVOLVE 2 4 2" on {1, 2, 3, 4, 5} results in {1, 3, 4, 2, 5}
INSERT x P: insert P after Ax. For example, performing "INSERT 2 4" on {1, 2, 3, 4, 5} results in {1, 2, 4, 3, 4, 5}
DELETE x: delete Ax. For example, performing "DELETE 2" on {1, 2, 3, 4, 5} results in {1, 3, 4, 5}
MIN x y: query the participant what is the minimum number in sub-sequence {Ax ... Ay}. For example, the correct answer to "MIN 2 4" on {1, 2, 3, 4, 5} is 2
To make the show more interesting, the participant is granted a chance to turn to someone else that means when Jackson feels difficult in answering a query he may call you for help. You task is to watch the TV show and write a program giving the correct answer to each query in order to assist Jackson whenever he calls.
Input
The first line contains n (n ≤ 100000).
The following n lines describe the sequence.
Then follows M (M ≤ 100000), the numbers of operations and queries.
The following M lines describe the operations and queries.
Output
For each "MIN" query, output the correct answer.
Sample Input
5
1
2
3
4
5
2
ADD 2 4 1
MIN 4 5
Sample Output
5
Code(splay)
第一次作死大面积用指针。。(果然是调了很久。。)最开始写的时候没有封装在结构体里。。然后zsl tsy说封进去可以树套树想用几棵用几棵 原来splay这种东西还是单子叶植物丛生或蔓生啊!!! = =哈哈哈 代码还是拖得比较长写了230行不过我写的松啊233333#include <cstdio>
#include <iostream>
using namespace std;
#define lc c[0]
#define rc c[1]
const int inf = 0x3f3f3f3f;
const int Nmax = 201000;
int readint()
{
char c;int sign = 1, n = 0; c = getchar();
while(c > '9' || c < '0'){ if(c == '-')sign = -1; c = getchar(); }
while(c <= '9' && c >= '0'){ n = n*10 + c-'0'; c = getchar();}
return n*sign;
}
int N, M;
int a[Nmax];
int cnt;
struct Splay{
struct node{
node *c[2], *f;
int w, s, minn;
int add, rev;
inline bool right() { return this == f -> rc; }
inline void setch(node *temp, bool r) { c[r] = temp; temp -> f = this; }
inline void flip(){ rev ^= 1; swap(lc, rc); }
inline void Add(int x){add += x; w += x; minn += x;}
}t[Nmax], *root, *null;
void pushup(node *p)
{
p -> s = 1; p -> minn = p -> w;
if(p -> lc != null)
{
p -> s += p -> lc -> s;
if(p -> minn > p -> lc -> minn) p -> minn = p -> lc -> minn;
}
if(p -> rc != null)
{
p -> s += p -> rc -> s;
if(p -> minn > p -> rc -> minn) p -> minn = p -> rc -> minn;
}
}
void pushdown(node *p)
{
if(p -> add)
{
if(p -> lc != null) p -> lc -> Add(p -> add);
if(p -> rc != null) p -> rc -> Add(p -> add);
p -> add = 0;
}
if(p -> rev)
{
if(p -> lc != null) p -> lc -> flip();
if(p -> rc != null) p -> rc -> flip();
p -> rev = 0;
}
}
node *NewNode(int x = 0)
{
t[cnt].lc = t[cnt].rc = t[cnt].f = null;
t[cnt].w = t[cnt].minn = x; t[cnt].s = 1;
t[cnt].add = t[cnt].rev = 0;
return &t[cnt++];
}
void build(node *p, int l, int r, int rank)
{
p -> w = p -> minn = a[rank];
if(l ^ rank)
{
node *lch = NewNode();
p -> setch(lch, 0);
build(lch, l, rank - 1, l+rank-1 >> 1);
}
if(r ^ rank)
{
node *rch = NewNode();
p -> setch(rch, 1);
build(rch, rank + 1, r, rank+1+r >> 1);
}
pushup(p);
}
void init()
{
null = NewNode(); null -> s = 0;
root = NewNode(); build(root, 1, N, 1+N >> 1);
}
void rotate(node *p)
{
node *fa = p -> f; bool r = p -> right();
fa -> f -> setch(p, fa -> right());
fa -> setch(p -> c[r ^ 1], r);
p -> setch(fa, r ^ 1);
pushup(fa);
}
void splay(node *p, node *father)
{
while(p -> f != father)
{
if(p -> f -> f == father) rotate(p);
else if(p -> right() == p -> f -> right())
{
rotate(p -> f);
rotate(p);
}
else
{
rotate(p);
rotate(p);
}
}
pushup(p);
if(p -> f == null) root = p;
}
node *find(int rank)
{
for(node *p = root; ; )
{
pushdown(p);
int ls = p -> lc -> s;
if(rank <= ls) p = p -> lc;
else if(ls + 1 == rank) return p;
else
{
rank -= ls + 1;
p = p -> rc;
}
}
}
node *getrange(int l, int r)
{
--l; ++r;
splay(find(l), null); splay(find(r), root);
return root -> rc -> lc;
}
void add()
{
int l = readint() + 1, r = readint() + 1, x = readint();
node *temp = getrange(l, r);
temp -> Add(x);
}
void insert()
{
int last = readint() + 1, x = readint();
node *temp = getrange(last + 1, last);
temp = NewNode(x);
root -> rc -> setch(temp, 0);
pushup(root -> rc); pushup(root);
}
void del()
{
int rank = readint() + 1;
node *temp = getrange(rank, rank);
root -> rc -> lc = null;
pushup(root -> rc); pushup(root);
}
void getmin()
{
int l = readint() + 1, r = readint() + 1;
node *temp = getrange(l, r);
printf("%d\n", temp -> minn);
}
void reverse()
{
int l = readint() + 1, r = readint() + 1;
node *temp = getrange(l, r);
temp -> flip();
}
void revolve()
{
int l = readint() + 1, r = readint() + 1, k = readint();
k %= (r-l+1);
if(!k) return;
node *temp = getrange(r-k+1, r);
root -> rc -> lc = null;
pushup(root -> rc); pushup(root);
node *p = getrange(l, l-1);
root -> rc -> setch(temp, 0);
pushup(root -> rc); pushup(root);
}
}s;
int main()
{
N = readint();
for(int i = 1; i <= N; ++i)
a[i+1] = readint();
N += 2; a[1] = a[N] = inf;
s.init();
for(M = readint(); M--; )
{
char st[10]; scanf("%s", st);
if(st[0] == 'A') s.add();
else if(st[0] == 'I') s.insert();
else if(st[0] == 'D') s.del();
else if(st[0] == 'M') s.getmin();
else if(st[3] == 'E') s.reverse();
else s.revolve();
}
return 0;
}
Code(treap)
神奇的treap加强版 = =。。带拆分与合并的#include <cstdio>
#include <iostream>
#include <cstdlib>
using namespace std;
int readint()
{
char c;int sign = 1, n = 0; c = getchar();
while(c > '9' || c < '0'){ if(c == '-')sign = -1; c = getchar(); }
while(c <= '9' && c >= '0'){ n = n*10 + c-'0'; c = getchar();}
return n*sign;
}
const int Nmax = 201000;
int N, M;
int cnt;
struct Treap{
struct node{
node *lc, *rc;
int w, r, s, minn;
int add, rev;
void Add(int x) { w += x; minn += x; add += x;}
void flip() { rev ^= 1; swap(lc, rc);}
}T[Nmax], *root, *null;
node *NewNode(int x = 0)
{
T[cnt].lc = T[cnt].rc = null;
T[cnt].w = T[cnt].minn = x; T[cnt].r = rand();
T[cnt].s = 1; T[cnt].add = T[cnt].rev;
return &T[cnt++];
}
void init()
{
null = NewNode(); null -> s = null -> r = 0;
null -> lc = null -> rc = null;
root = null;
}
void pushup(node *p)
{
p -> minn = p -> w; p -> s = 1;
if(p -> lc != null)
{
p -> s += p -> lc -> s;
if(p -> minn > p -> lc -> minn) p -> minn = p -> lc -> minn;
}
if(p -> rc != null)
{
p -> s += p -> rc -> s;
if(p -> minn > p -> rc -> minn) p -> minn = p -> rc -> minn;
}
}
void pushdown(node *p)
{
if(p -> lc != null)
{
if(p -> add) p -> lc -> Add(p -> add);
if(p -> rev) p -> lc -> flip();
}
if(p -> rc != null)
{
if(p -> add) p -> rc -> Add(p -> add);
if(p -> rev) p -> rc -> flip();
}
p -> add = p -> rev = 0;
}
void r_rotate(node *&p)
{
node *temp = p -> lc;
pushdown(temp);
p -> lc = temp -> rc;
temp -> rc = p;
pushup(p);
p = temp;
}
void l_rotate(node *&p)
{
node *temp = p -> rc;
pushdown(temp);
p -> rc = temp -> lc;
temp -> lc = p;
pushup(p);
p = temp;
}
void cut(node *an, node *&p, node *&q, int num)
{
if(num == 0)
{
p = null; q = an;
return;
}
if(num == an -> s)
{
p = an; q = null;
return;
}
pushdown(an); int lsize = an -> lc -> s;
if(num <= lsize)
{
q = an; cut(an -> lc, p, q -> lc, num);
pushup(q);
} else {
p = an; cut(an -> rc, p -> rc, q, num - lsize - 1);
pushup(p);
}
}
void merge(node *&ne,node *p,node *q)
{
if(p == null || q == null)
{
ne = p == null ? q : p;
return;
}
if(p -> r > q -> r)
{
pushdown(p); ne = p;
merge(ne -> rc, p -> rc, q);
} else {
pushdown(q); ne = q;
merge(ne -> lc, p, q -> lc);
}
pushup(ne);
}
void add(node *&p, int l, int r, int x)
{
node *L, *M, *R;
cut(root, L, M, l - 1); cut(M, M, R, r - l + 1);
M -> Add(x);
merge(L, L, M); merge(root, L, R);
}
void insert(node *&p, int x, int k)
{
if(p == null)
{
p = NewNode(x);
return;
}
pushdown(p);
int lsize = p -> lc -> s;
if(k <= lsize)
{
insert(p -> lc, x, k);
if(p -> lc -> r > p -> r) r_rotate(p);
} else {
insert(p -> rc, x, k - lsize - 1);
if(p -> rc -> r > p -> r) l_rotate(p);
}
pushup(p);
}
void del(int k)
{
node *last, *th, *next;
cut(root, last, th, k-1); cut(th, th, next, 1);
merge(root, last, next);
}
void getmin(int l, int r)
{
node *L, *M, *R;
cut(root, L, M, l - 1); cut(M, M, R, r - l + 1);
printf("%d\n", M -> minn);
merge(L, L, M); merge(root, L, R);
}
void reverse(int l, int r)
{
node *L, *M, *R;
cut(root, L, M, l - 1); cut(M, M, R, r - l + 1);
M -> flip();
merge(L, L, M); merge(root, L, R);
}
void revolve(int l, int r, int k)
{
k %= (r - l + 1); if(!k) return;
node *L, *MM, *M, *R;
cut(root, L, MM, l - 1);
cut(MM, MM, M, r - l + 1 - k);
cut(M, M, R, k);
merge(L, L, M);
merge(L, L, MM);
merge(root, L, R);
}
}t;
int main()
{
srand(233); t.init();
N = readint(); int x;
for (int i = 1; i <= N; ++i)
{
x = readint();
t.insert(t.root, x, i);
}
for(M = readint(); M--; )
{
char s[10]; scanf("%s", s);
if (s[0] == 'A'){
int l, r, x; scanf("%d%d%d", &l, &r, &x);
t.add(t.root, l, r, x);
} else if (s[0] == 'I') {
int pos, x; scanf("%d%d", &pos, &x);
t.insert(t.root, x, pos);
} else if (s[0] == 'D'){
int pos; scanf("%d", &pos);
t.del(pos);
} else if (s[0] == 'M'){
int l, r; scanf("%d%d", &l, &r);
t.getmin(l, r);
} else if (s[3] == 'E'){
int l, r; scanf("%d%d", &l, &r);
t.reverse(l, r);
} else {
int l, r, k; scanf("%d%d%d", &l, &r, &k);
t.revolve(l, r, k);
}
}
return 0;
}
1503: [NOI2004]郁闷的出纳员
Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 6841 Solved: 2395
[Submit][Status]
Description
OIER公司是一家大型专业化软件公司,有着数以万计的员工。作为一名出纳员,我的任务之一便是统计每位员工的工资。这本来是一份不错的工作,但是令人郁闷的是,我们的老板反复无常,经常调整员工的工资。如果他心情好,就可能把每位员工的工资加上一个相同的量。反之,如果心情不好,就可能把他们的工资扣除一个相同的量。我真不知道除了调工资他还做什么其它事情。工资的频繁调整很让员工反感,尤其是集体扣除工资的时候,一旦某位员工发现自己的工资已经低于了合同规定的工资下界,他就会立刻气愤地离开公司,并且再也不会回来了。每位员工的工资下界都是统一规定的。每当一个人离开公司,我就要从电脑中把他的工资档案删去,同样,每当公司招聘了一位新员工,我就得为他新建一个工资档案。老板经常到我这边来询问工资情况,他并不问具体某位员工的工资情况,而是问现在工资第k多的员工拿多少工资。每当这时,我就不得不对数万个员工进行一次漫长的排序,然后告诉他答案。好了,现在你已经对我的工作了解不少了。正如你猜的那样,我想请你编一个工资统计程序。怎么样,不是很困难吧?
Input
Output
输出文件的行数为F命令的条数加一。对于每条F命令,你的程序要输出一行,仅包含一个整数,为当前工资第k多的员工所拿的工资数,如果k大于目前员工的数目,则输出-1。输出文件的最后一行包含一个整数,为离开公司的员工的总数。
Sample Input
9 10
I 60
I 70
S 50
F 2
I 30
S 15
A 5
F 1
F 2
Sample Output
10
20
-1
2
HINT
I命令的条数不超过100000 A命令和S命令的总条数不超过100 F命令的条数不超过100000 每次工资调整的调整量不超过1000 新员工的工资不超过100000
Code(splay)
splay#include <cstdio>
#include <iostream>
#define lc c[0]
#define rc c[1]
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 100000 + 10;
int readint()
{
char c;int sign = 1, n = 0; c = getchar();
while(c > '9' || c < '0'){ if(c == '-')sign = -1; c = getchar(); }
while(c <= '9' && c >= '0'){ n = n*10 + c-'0'; c = getchar();}
return n*sign;
}
int M, lim, delta;
int leave, cnt;
struct Splay{
struct node{
node *c[2], *f;
int w, s, num;
inline bool right(){ return this == f -> c[1]; }
inline void setch(node *temp, bool r){ c[r] = temp; temp -> f = this;}
inline void maintain(){ s = lc -> s + rc -> s + num;}
}T[N], *root, *null;
inline node *NewNode(int x = 0)
{
T[cnt].lc = T[cnt].rc = T[cnt].f = null;
T[cnt].w = x; T[cnt].s = T[cnt].num = 1;
return &T[cnt++];
}
inline void init()
{
null = NewNode();
null -> s = null -> num = 0;
root = null;
}
void rotate(node *p)
{
node *fa = p -> f;
bool r = p -> right();
fa -> f -> setch(p, fa -> right());
fa -> setch(p -> c[r ^ 1], r);
p -> setch(fa, r ^ 1);
fa -> maintain();
}
void splay(node *temp, node *father)
{
while(temp -> f != father)
{
if(temp -> f -> f == father) rotate(temp);
else if(temp -> right() == temp -> f -> right())
{
rotate(temp -> f);
rotate(temp);
}
else
{
rotate(temp);
rotate(temp);
}
}
temp -> maintain();
if(temp -> f == null) root = temp;
}
void insert(int x, int n = 1)
{
if(root == null)
{
root = NewNode(x);
root -> num = n;
return;
}
node *p;
for(p = root; p -> c[p -> w < x] != null; )
{
if(p -> w == x)
{
p -> num += n;
splay(p, null);
return;
}
p = p -> c[p -> w < x];
}
node *temp = NewNode(x); temp -> num = n;
p -> setch(temp, p -> w < x);
splay(temp, null);
}
void del(int limit)
{
insert(limit); int c = root -> num - 1;
leave += root -> lc -> s - 1;
root = root -> rc; root -> f = null;
insert(-inf); if(c) insert(limit, c);
}
int kth(int k)
{
for(node *p = root; ; )
{
int lsize = p -> lc -> s;
if(k <= lsize) p = p -> lc;
else if(k > lsize && k <= p -> num + lsize) return p -> w;
else
{
k -= lsize + p -> num;
p = p -> rc;
}
}
}
}s;
int main()
{
s.init(); s.insert(-inf); s.insert(inf);
for(M = readint(), lim = readint(); M--; )
{
char c; int x;
scanf(" %c%d", &c, &x);
switch(c)
{
case 'I' : if(x >= lim) s.insert(x - delta); break;
case 'A' : delta += x; break;
case 'S' : delta -= x; s.del(lim - delta); break;
case 'F' : int size = s.root -> s;
if(size - 2 < x) puts("-1");
else printf("%d\n", s.kth(size - x) + delta);
break;
}
}
printf("%d\n", leave);
return 0;
}
Code (treap)
重写的treap版。。。orz我不懂为什么会比splay还慢 = = 另外bzoj不能用time啊。。。#include <stdio.h>
#include <iostream>
#include <cstdlib>
using namespace std;
const int N = 201000;
int M, lim, delta;
int cnt, leave;
struct Treap{
struct node{
node *lc, *rc;
int s, w, r;
}T[N], *root, *null;
node *NewNode(int x = 0)
{
T[cnt].lc = T[cnt].rc = null;
T[cnt].s = 1; T[cnt].w = x; T[cnt].r = rand();
return &T[cnt++];
}
void init()
{
null = NewNode(); null -> s = 0; null -> r = -1;
root = null;
}
inline void pushup(node *&p)
{
p -> s = p -> lc -> s + p -> rc -> s + 1;
}
inline void r_rotate(node *&p)
{
node *temp = p -> lc;
p -> lc = temp -> rc; pushup(p);
temp -> rc = p; pushup(temp);
p = temp;
}
inline void l_rotate(node *&p)
{
node *temp = p -> rc;
p -> rc = temp -> lc; pushup(p);
temp -> lc = p; pushup(temp);
p = temp;
}
inline void maintain(node *&p)
{
if(p -> r < p -> lc -> r) r_rotate(p);
else if(p -> r < p -> rc -> r) l_rotate(p);
}
void insert(node *&p, int x)
{
if(p == null)
{
p = NewNode(x);
return;
}
if(p -> w > x) insert(p -> lc, x);
else insert(p -> rc, x);
pushup(p); maintain(p);
}
void del(node *&p, int x)
{
if(p == null) return;
if(p -> w < x)
{
leave += p -> lc -> s + 1;
p = p -> rc;
del(p, x);
} else {
del(p -> lc, x);
pushup(p);
}
}
int kth(node *&p, int k)
{
int rank = p -> lc -> s + 1;
if(rank == k) return p -> w;
if(rank < k) return kth(p -> rc, k - rank);
return kth(p -> lc, k);
}
}t;
int main()
{
srand(233); t.init();
for(scanf("%d%d", &M, &lim); M--; )
{
char c; int x;
scanf(" %c%d", &c, &x);
switch (c)
{
case 'I':
if (x >= lim) t.insert(t.root, x - delta);
break;
case 'A':
delta += x;
break;
case 'S':
delta -= x;
t.del(t.root, lim - delta);
break;
case 'F':
int size = t.root -> s;
if(size < x) puts("-1");
else printf("%d\n", t.kth(t.root, size - x + 1) + delta);
break;
}
}
printf("%d\n", leave);
return 0;
}
更多推荐
【Splay|Treap】poj3580 SuperMemo && bzoj1503 [noi2004]郁闷的出纳员
发布评论