关于splay的分裂与合并问题

Question

请教一下各位大佬~
嗯就是说在实现splay的分裂与合并时，lazy tag似乎会对结果产生影响，这样的问题应如何处理呢？
如图：

求教~
详见UVA11922
附上本人巨丑的c++代码：

#include<bits/stdc++.h>
using namespace std;

#define maxn 100000

struct Node {
    int fa,ch[2];
    int sz,lzy;
    void init() {
        fa=ch[0]=ch[1]=lzy=0;
        sz=1;
    }
};

int n,m;
Node a[maxn+5]= {0};
int rt=0;

void debug() {
    printf("rt %d\n",rt);
    for(int i=1; i<=n+2; i++) {
        printf("%d fa %d ch0 %d ch1 %d sz %d lzy %d\n",i,a[i].fa,a[i].ch[0],a[i].ch[1],a[i].sz,a[i].lzy);
    }
}

void push_down(int o) {
    if(a[o].lzy==0) return ;
    a[o].lzy=0;
    swap(a[o].ch[0],a[o].ch[1]);
    a[a[o].ch[0]].lzy^=1;
    a[a[o].ch[1]].lzy^=1;
}

void print(int u) {
    push_down(u);
    if(a[u].ch[0]) print(a[u].ch[0]);
    if(u!=1&&u!=n+2)printf("%d\n",u-1);
    if(a[u].ch[1]) print(a[u].ch[1]);
}

void push_up(int o) {
    a[o].sz=a[a[o].ch[0]].sz+a[a[o].ch[1]].sz+1;
}

void make_tree(int o,int l,int r) {
    if(l>r) return ;
    int mid=l+(r-l)/2;
    a[mid].fa=o,a[mid].sz=1;
    if(mid<o) a[o].ch[0]=mid;
    else a[o].ch[1]=mid;
    if(l==r) return ;
    make_tree(mid,l,mid-1),make_tree(mid,mid+1,r);
    push_up(mid);
}

void rotate(int x) {
    int y=a[x].fa,z=a[y].fa;
    int k=(a[y].ch[1]==x);
    a[z].ch[a[z].ch[1]==y]=x,a[x].fa=z;
    a[y].ch[k]=a[x].ch[k^1],a[a[x].ch[k^1]].fa=y;
    a[x].ch[k^1]=y,a[y].fa=x;
    push_up(y),push_up(x);
}

void splay(int x,int k) {
    while(a[x].fa!=k) {
        int y=a[x].fa,z=a[y].fa;
        if(k!=z) {
            if((a[y].ch[0]==x)^(a[z].ch[0]==y)) rotate(x);
            else rotate(y);
        }
        rotate(x);
    }
    if(!k) rt=x;
}

int find(int x,int k) {
    push_down(x);
    push_up(x);
    int s=a[a[x].ch[0]].sz;
    if(k==s+1) return x;
    if(k<=s) return find(a[x].ch[0],k);
    else return find(a[x].ch[1],k-s-1);
}

void rev(int p,int q) {
    int x=find(rt,p-1),y=find(rt,q+1);
    splay(x,0);
    splay(y,rt);
    a[a[y].ch[0]].lzy^=1;
}

int findright(int u) {
    push_down(u);
    if(a[u].ch[1]==0) return u;
    else return findright(a[u].ch[1]);
}

void divide(int fa,int son) {
    a[fa].ch[0]=0,a[fa].sz-=a[son].sz;
    a[son].fa=0;
}

void merge(int fa,int son) {
    a[fa].ch[0]=son;
    a[son].fa=fa;
    a[fa].sz+=a[son].sz;
}

void Move(int p,int q) {
    push_down(rt);
    int fa=a[rt].ch[1];
    push_down(fa);
    int son=a[fa].ch[0];
    divide(fa,son);
//  cout<<fa<<' '<<son<<endl;
    int r=findright(rt);
    if(a[r].ch[0]) splay(a[r].ch[0],0);
//  debug();
    merge(r,son);
}

int main() {
//  freopen("3.5 19922.out","w",stdout);
    scanf("%d%d",&n,&m);
    rt=(n+3)/2;
    make_tree(rt,1,n+2);
    a[0].ch[1]=rt;
    a[rt].fa=0;
    while(m--) {
        int p,q;
        scanf("%d%d",&p,&q);
        p++,q++;
        rev(p,q);
//      debug();
        Move(p,q);
//      debug();
    }
    print(rt);
    return 0;
}

Answer 1

http://www.mamicode.com/info-detail-1212321.html