【WC2016】鏖战表达式 | Mrsrz's blog

可持久化平衡树

题目大意：

交互题。

给定一个表达式，有 $k$ 种运算符，优先级按标号从小到大。

每种运算符都是二元运算符，且都满足交换律和结合律。

要支持以下操作：

1. 修改一个操作数。
2. 修改一个运算符。
3. 区间翻转。

每次修改都是基于之前某个版本。

要求每次修改完后，输出表达式的值。

通过交互的方式强制在线。

每次你需要求 $(a\ \mathrm{op}\ b)$ 的时候，都需要调用一次 F 函数。该函数最多调用 $10^7$ 次。

题解：

基本操作是用平衡树维护运算符。

运算符是有优先级的，同级的需要在同层中维护。

而 Treap 本身就存在一个“优先级”。因此一个简单的思路是用 Treap 直接维护表达式，按照运算符为其优先级进行比较。

对于同级的，根据子树大小来随机合并。

至于从历史版本上休息，把 Treap 可持久化一下即可。

这样的树高期望可能是 $O(k+\log n)$ 的。

但是如果建树的时候是一个一个合并的话，可以给一段 $1$，一段 $2$，等等，就能把树高卡到 $O(k\log n)$。

建树的时候可以使用分治的方法，每次找当前层中最接近中点的那个就好。

修改操作数可以直接递归到底层来改，保证树高不变。

另外两个操作不怎么会分析复杂度，或许有可能使树高变为 $O(k\log n)$。

官方数据最大的点约 $4.5\times 10^6$ 次函数调用。

希望有人教我优秀的复杂度分析方法/kk

Code：

#ifdef LOCAL
#include"grader.cpp"
#endif
#include<random>
#include<vector>
#include"expr.h"
using namespace std;
const int N=40005;
random_device sd;
mt19937 mt(sd());
struct node{
    int sz,op,ls,rs;
    bool rev;
    Data res;
}d[13000000];
int nod,rt[N],ver;
vector<int>pos[102];
inline int clone(int x){d[++nod]=d[x];return nod;}
inline void flip(int x){d[x].rev^=1,swap(d[x].ls,d[x].rs);}
inline void pushdown(int x){
    if(d[x].rev){
        if(d[x].ls)d[x].ls=clone(d[x].ls),flip(d[x].ls);
        if(d[x].rs)d[x].rs=clone(d[x].rs),flip(d[x].rs);
        d[x].rev=0;
    }
}
inline void update(int x){
    if(d[x].op<=100){
        if(d[x].ls&&d[x].rs)d[x].res=F(d[d[x].ls].res,d[d[x].rs].res,d[x].op);
    }
    d[x].sz=d[d[x].ls].sz+d[d[x].rs].sz+1;
}
int merge(int x,int y){
    if(!x||!y)return x|y;
    pushdown(x),pushdown(y);
    if(d[x].op<d[y].op||d[x].op==d[y].op&&mt()%(d[x].sz+d[y].sz)<d[x].sz){
        int u=clone(x);
        d[u].rs=merge(d[u].rs,y);
        update(u);
        return u;
    }
    int u=clone(y);
    d[u].ls=merge(x,d[u].ls);
    update(u);
    return u;
}
void split(int u,int k,int&x,int&y){
    if(d[u].sz==k)x=clone(u),y=0;
    else if(!k)x=0,y=clone(u);
    else{
        pushdown(u);
        if(d[d[u].ls].sz>=k)y=clone(u),split(d[y].ls,k,x,d[y].ls),update(y);
        else x=clone(u),split(d[x].rs,k-1-d[d[u].ls].sz,d[x].rs,y),update(x);
    }
}
inline int find(int k,int l,int r,int x){
    int _r=lower_bound(pos[k].begin(),pos[k].end(),x)-pos[k].begin();
    int _l=_r-1;
    if(_r<(int)pos[k].size()&&_l>=0&&l<=pos[k][_l]&&pos[k][_r]<=r){
        _l=pos[k][_l],_r=pos[k][_r];
        if(x-_l<=_r-x)return _l;else return _r;
    }else if(_r<(int)pos[k].size()&&pos[k][_r]<=r)return pos[k][_r];
    else if(_l>=0&&l<=pos[k][_l])return pos[k][_l];
    return 0;
}
void build(int l,int r,int k,int&o){
    if(l>r)return;
    if(l==r)o=l;else{
        const int mid=(l+r)>>1;
        int x=find(k,l,r,mid);
        while(!x)x=find(++k,l,r,mid);
        o=x;
        build(l,x-1,k,d[o].ls),build(x+1,r,k,d[o].rs);
        update(o);
    }
}
void init_(int n){
    for(int i=1;i<=n;++i)
    pos[d[i].op].push_back(i);
    build(1,n,1,rt[0]);
}
void init(int,int n,int m,int,const Data*a,const int*ops){
    for(int i=0;i<n-1;++i){
        d[++nod]=(node){1,101,0,0,0,a[i]};
        d[++nod]=(node){1,ops[i+1],0,0,0,0};
    }
    d[++nod]=(node){1,101,0,0,0,a[n-1]};
    init_(2*n-1);
}
void modify(int&x,int pos,Data v){
    pushdown(x);
    if(pos==d[d[x].ls].sz+1)d[x].res=v;
    else if(pos<=d[d[x].ls].sz)
    modify(d[x].ls=clone(d[x].ls),pos,v);
    else modify(d[x].rs=clone(d[x].rs),pos-d[d[x].ls].sz-1,v);
    update(x);
}
Data modify_data(int id,int pos,Data x){
    int z=2*pos+1;
    modify(rt[++ver]=clone(rt[id]),z,x);
    return d[rt[ver]].res;
}
Data modify_op(int id,int pos,int new_op){
    int z=2*pos;
    int a,b,c;
    split(rt[id],z-1,a,b);
    split(b,1,b,c);
    d[b].op=new_op;
    rt[++ver]=merge(merge(a,b),c);
    return d[rt[ver]].res;
}
Data reverse(int id,int l,int r){
    l=2*l+1,r=2*r+1;
    int a,b,c;
    split(rt[id],r,b,c);
    split(b,l-1,a,b);
    flip(b);
    rt[++ver]=merge(merge(a,b),c);
    return d[rt[ver]].res;
}