妈呀,我裂开了啊,调了一天,终于出了
总结一下:
1:add懒标记是用+不是=！！！(如果本来就有标记的就覆盖了),反转也是,一定要注意懒标记不能=
2:splay用来进行区间操作的话,建树的时候可以像(BST)splay一样加入两个哨兵,一个代表下标0,一个代表下标n+1,写函数的时候就不用考虑边界了
3:splay可以像线段树一样进行区间操作,push_up,push_down,但是一定要注意,先push_down自己,再push_down孩子,先push_up孩子,再push_up自己!
4:二叉树建树以及加点多用引用,好处是真的多
代码:
#include
#include[span style="color: rgba(0, 0, 255, 1)">string.h>
using namespace std;
const int maxn = 2e5 + 100;
inline int read()
{
int s = 0, w = 1; char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') w = -1; ch = getchar(); }
while (ch >= '0' ch <= '9') s = s 10 + ch - '0', ch = getchar();
return s w;
}
#define ls(x) tree【x】【0】
#define rs(x) tree【x】【1】//良好习惯,不加的话下面用到太多了,容易出错
int tree【maxn】【2】, siz【maxn】, val【maxn】, add【maxn】, rev【maxn】, fa【maxn】;
int root, tot;
void //代码效果参考：http://www.zidongmutanji.com/bxxx/283530.html
new_node(int x, int f, int valu)//引用大法好,以后要经常用QAQ{
x = ++tot;
fa【x】 = f;
val【x】 = valu;
siz【x】 = 1; rev【x】 = add【x】 = 0;
ls(x) = rs(x) = 0;
}
void push_up(int rt) {
siz【rt】 = siz【ls(rt)】 + siz【rs(rt)】 + 1;
}
void push_down(int rt) {
if (rev【rt】) {
swap(ls(rt), rs(rt));//传递
rev【ls(rt)】 ^= 1;
rev【rs(rt)】 ^= 1;
rev【rt】 = 0;//重置
}
if (add【rt】) {//add【rt】是关于其孩子的效果
val【rs(rt)】 += add【rt】;
val【ls(rt)】 += add【rt】;
add【ls(rt)】 += add【rt】;
add【rs(rt)】 += add【rt】;
add【rt】 = 0;//一定要记得重置
}
}
void rotate(int x) {//这里出错就没办法了,记得更新子节点同时更新子节点的父节点,两两配对
int y = fa【x】, z = fa【y】, f = (rs(y) == x);
push_down(x); push_down(y);//先自己再父亲,我淦!
tree【y】【f】 = tree【x】【f ^ 1】;
fa【tree【x】【f ^ 1】】 = y;
if (z) {
tree【z】【rs(z) == y】 = x;
}
fa【x】 = z;
tree【x】【f ^ 1】 = y;
fa【y】 = x;
push_up(y);
}
void splay(int x, int top) {
push_down(x);//每次tree下标作为参数的都push_down
while (fa【x】 != top) {
int y = fa【x】, z = fa【y】;
///先祖再父后自己????????
if (z != top) {
if ((ls(z) == y) ^ (ls(y) == x)) {
rotate(x);
}
else {
rotate(y);
}
}
rotate(x);
}
push_up(x);//可以放这里,因为每次旋转后x都是父亲节点,没必要更新,最后旋转完成来更新就行
if (top == 0)root = x;//旋转到根记得修正
}
void rotto(int k, int top) {//把排名当作其在数组中的位置,这样就能轻松完成区间操作
int p = root;
push_down(p);
while (siz【ls(p)】 != k) {//由于增加了两个点,一个最小点,一个最大点,所以查找的时候左孩子的siz就是位置
if (siz【ls(p)】 > k)p = ls(p);
else k -= (siz【ls(p)】 + 1), p = rs(p);
push_down(p);
}
splay(p, top);
}
void insert(int valu, int pos) {
rotto(pos, 0); rotto(pos + 1, root);
new_node(ls(rs(root)), rs(root), valu);
push_up(rs(root));//一般插入后需要旋转到根,但是这里我们只是插入到离根位置为2的点,距离比较近,直接更新即可,记得先更新孩子,再更新根
push_up(root);
}
void add_val(int L, int R, int x) {
rotto(L - 1, 0); rotto(R + 1, root);//把L-R区间内的数都赶到右子树的左子树上,然后给个懒标记即可
add【ls(rs(root))】 += x;//2 卧槽!!!!
val【ls(rs(root))】 += x;
}
void reverse(int L, int R) {
rotto(L - 1, 0); rotto(R + 1, root);//没有两个哨兵,你这个操作要多判断多少东西,想一想
rev【ls(rs(root))】 ^= 1;
}
void del(int pos) {
rotto(pos - 1, 0); rotto(pos + 1, root);//还是把pos位置的数赶到右子树的左子树,删除即可.
ls(rs(root)) = 0;
push_up(rs(root));
push_up(root);
}
void cut(int len, int last) {//把长度为len的区间接到最后面去
rotto(len + 1, 0); rotto(0, root);//由于增加了两个点,第一个点的位置永远为0,最后一个点的位置为n+1
int rt = rs(ls(root));//再通过将第一个数旋转到根的儿子位置,这样就能轻松将需要的前几个数赶到一棵树上,
rs(ls(root)) = 0;//删除前面len长度的数组成的树,并用rt保存根节点位置
push_up(ls(root));
push_up(root);
rotto(last - len, 0);//最后一个点在右侧,把刚拆出来的树区间rt加入到右边去,刚好就是旋转过来的样子
ls(rs(root)) = rt;
push_up(rs(root));
push_up(root);//记得及时更新
}
int a【maxn】;
void build(int l, int r, int rt, int fa) {//引用大法好
if (l > r) { return; }
int mid = (l + r) ] 1;
new_node(rt, fa, a【mid】);
build(l, mid - 1, ls(rt), rt);//虽然和线段树很像,但是只有n个节点,所以减一啊!!!!
build(mid + 1, r, rs(rt), rt);
push_up(rt);
}
void init(int n) {
for (int i = 1; i <= n; i++) {
a【i】 = read();
}
ls(0) = rs(0) = fa【0】 = siz【0】 = val【0】 = rev【0】 = add【0】 = 0;
root = tot = 0;//初始化注意!!!
new_node(root, 0, 0);
new_node(rs(root), root, 0);//先开两个点,用来切区间的时候方便处理,一个是左区间端点,一个是友区间端点
//就是哨兵,只不过这里面为了区间操作是按照位置排序的,而常规的splay是按照权值排序的BST树,二者作用不同.
build(1, n, ls(rs(root)), rs(root));
//这种方式建成的树的中序遍历结果就是1-n,所以叫中序建树(自己起的)
push_up(rs(root));
push_up(root);
}
int main() {
//freopen("test.txt", "r", stdin);
int now, num = 1;
int n, m, k1, k2;
while (~scanf("%d%d%d%d", n, m, k1, k2)) {
if (n == 0 m == 0 k1 == 0 k2 == 0)break;
now = 1;
init(n);
printf("Case #%d:\n", num++);
while (m--) {
string t; cin ] t;
char c = t【0】;
if (c == 'a') {
int x = read(), s = now + k2 - 1;
if (s <= n) {
add_val(now, s, x);
}
else {
add_val(now, n, x);//如果超界了就两边加上就好了
add_val(1, s - n, x);
}
}
else if (c == 'r') {
int R = now + k1 - 1;
if (R <= n) {
reverse(now, R);
}
else {
cut(R - n, n);
now = n - k1 + 1;
reverse(now, n);
}
}
else if (c == 'i') {
int x = read();
insert(x, now);
n++;
}
else if (c == 'd') {
del(now);
if (now == n)now = 1;
n--;
}
else if (c == 'm') {
int x = read();
if (x == 1)now--;
else now++;
if (now == 0)now = n;
if (now == n + 1)now = 1;
}
else if (c == 'q') {
rotto(now, 0);
printf("%d\n", val【root】);
//代码效果参考：http://www.zidongmutanji.com/bxxx/28768.html
}}
}
return 0;
}
