【WC2016】鏖战表达式

考虑建出表达式的表达式树
表达式树的中序遍历结果就是原表达式 且父节点运算符的优先级不高于子节点的优先级
可以看成固定了优先级的treap
然后我几乎没写过非旋treap。。
大概就是分裂的时候要新建节点 合并的时候不需要
pushdown的时候当前节点不需要新建 但是左右儿子需要新建
合并的时候以子树大小的比值为概率决定哪个节点作为祖先
然后从后往前建树才能过 不知道为什么。。

#include"expr.h"
#include<bits/stdc++.h>
using namespace std;
#define fp(i,l,r) for(register int (i)=(l);i<=(r);++(i))
#define fd(i,l,r) for(register int (i)=(l);i>=(r);--(i))
#define fe(i,u) for(register int (i)=front[(u)];(i);(i)=e[(i)].next)
#define mem(a) memset((a),0,sizeof (a))
#define O(x) cerr<<#x<<‘:‘<<x<<endl
const int MAXN=40010;
mt19937 gen(20020328);
int ls[MAXN*300],rs[MAXN*300],op[MAXN*300],sze[MAXN*300],cnt,rt[MAXN];
Data val[MAXN*300];bool tag[MAXN*300];
inline int copynode(int x){
	int y=++cnt;
	val[y]=val[x];tag[y]=tag[x];
	ls[y]=ls[x];rs[y]=rs[x];op[y]=op[x];sze[y]=sze[x];
	return y;
}
inline void mrev(int &o){
	if(!o)return;o=copynode(o);
	tag[o]^=1;swap(ls[o],rs[o]);
}
inline void pushdown(int &o){
	if(!tag[o])return;
	mrev(ls[o]);mrev(rs[o]);tag[o]=0;
}
inline void pushup(int o){
	sze[o]=sze[ls[o]]+sze[rs[o]]+1;
	if(ls[o]&&rs[o])val[o]=F(val[ls[o]],val[rs[o]],op[o]);
	else if(ls[o]||rs[o])val[o]=val[ls[o]?ls[o]:rs[o]];
}
void split(int o,int p,int &x,int &y){
	if(!o){x=y=0;return;}
	pushdown(o);
	if(p<=sze[ls[o]]){
		y=copynode(o);split(ls[o],p,x,ls[y]);pushup(y);
	}
	else{
		x=copynode(o);split(rs[o],p-sze[ls[o]]-1,rs[x],y);pushup(x);
	}
}
int merge(int x,int y){
	if(!x||!y)return x|y;
	pushdown(x);pushdown(y);
	if(op[x]<op[y]||(op[x]==op[y]&&1ll*gen()%(sze[x]+sze[y])<sze[x])){
		int o=copynode(x);rs[o]=merge(rs[x],y);
		pushup(o);return o;
	}
	else{
		int o=copynode(y);ls[o]=merge(x,ls[y]);
		pushup(o);return o;
	}
}
int n,m,K,tot;
void init(int test_id,int nn,int mm,int kk,const Data a[],const int ops[]){
	n=nn;m=mm;K=kk;
	fd(i,n-1,0){
		int o=++cnt;val[o]=a[i];sze[o]=1;op[o]=105;rt[0]=merge(o,rt[0]);
		if(i){
			int o=++cnt;sze[o]=1;op[o]=ops[i];rt[0]=merge(o,rt[0]);
		}
	}
}
Data modify_data(int id,int p,Data x){
	++tot;int rt1,rt2,tt;p=p*2+1;
	split(rt[id],p-1,rt1,rt2);split(rt2,1,tt,rt2);
	int o=++cnt;sze[o]=1;val[o]=x;op[o]=105;rt[tot]=merge(merge(rt1,o),rt2);
	return val[rt[tot]];
}
Data modify_op(int id,int p,int ops){
	++tot;int rt1,rt2,tt;p=p*2;
	split(rt[id],p-1,rt1,rt2);split(rt2,1,tt,rt2);
	int o=++cnt;sze[o]=1;op[o]=ops;rt[tot]=merge(merge(rt1,o),rt2);
	return val[rt[tot]];
}
Data reverse(int id,int l,int r){
	++tot;int rt1,rt2,rt3;l=l*2+1;r=r*2+1;
	split(rt[id],r,rt1,rt3);split(rt1,l-1,rt1,rt2);
	rt2=copynode(rt2);mrev(rt2);
	rt[tot]=merge(merge(rt1,rt2),rt3);
	return val[rt[tot]];
}

【WC2016】鏖战表达式

原文：https://www.cnblogs.com/misaka10047/p/13620214.html