浅谈\(splay\)：https://www.cnblogs.com/AKMer/p/9979592.html

浅谈\(fhq\)_\(treap\)：https://www.cnblogs.com/AKMer/p/9981274.html

题目传送门：https://www.luogu.org/problemnew/show/P4883

讲个笑话：\(mzf\)的考验卡了\(mzf\)俩小时。

要写这题，首先你得知道以下两件事：

1、你需要用一棵平衡树，然后每个结点开个长\(20\)的数组分别记录子树内这一位有多少个\(1\)，而不是开\(20\)个平衡树。否则你会

TLE

2、在提交时必须要开\(O2\)优化，至今没有人可以不开\(O2\)而用平衡树通过这道题，如果你对自己非常有信心，那么你将会

TLE

因为数据是随机造的，很多人用暴力+\(O2\)就\(A\)穿了，所以出题人不得不加强数据并且降低时限，丧心病狂到标算都必须开\(O2\)才能过了。

说实话，除开这些因素，这题跟序列终结者没啥大区别了。

\(splay\)版代码如下：

// luogu-judger-enable-o2

#include <cstdio>

#include <algorithm>

using namespace std;

#define ll long long

const int maxn=1e5+5;

int n,m;

int a[maxn];

int read() {

    int x=0,f=1;char ch=getchar();

    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

    for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

    return x*f;

}

struct Splay {

    int tot,root;

    ll sum[maxn];

    bool re[maxn];

    int tmp[maxn],xo[maxn];

    int siz[maxn],val[maxn];

    int fa[maxn],son[maxn][2],cnt[maxn][20];

    void Extract(int *a,int v) {

        for(int i=0;i<20;i++)

            a[i]=(v>>i)&1;

    }

    void update(int p) {

        siz[p]=siz[son[p][0]]+1+siz[son[p][1]];

        sum[p]=sum[son[p][0]]+val[p]+sum[son[p][1]];

        for(int i=0;i<20;i++)

            cnt[p][i]=cnt[son[p][0]][i]+((val[p]>>i)&1)+cnt[son[p][1]][i];

    }

    void build(int l,int r,int lst) {

        if(r<l)return;

        if(l==r) {

            siz[l]=1,fa[l]=lst;

            son[lst][l>lst]=l;

            sum[l]=val[l]=a[l];

            Extract(cnt[l],a[l]);

            return;

        }

        int mid=(l+r)>>1;

        fa[mid]=lst,son[lst][mid>lst]=mid;

        sum[mid]=val[mid]=a[mid];

        build(l,mid-1,mid),build(mid+1,r,mid);

        update(mid);

    }

    void prepare() {

        tot=n+2;build(1,n+2,0);root=(n+3)>>1;

    }

    void add_rev_tag(int u) {

        if(!u)return;

        re[u]^=1,swap(son[u][0],son[u][1]);

    }

    void add_xor_tag(int u,int v) {

        if(!u)return;

        val[u]^=v,xo[u]^=v;

        Extract(tmp,v);

        ll res=0;

        for(int i=0;i<20;i++) {

            if(tmp[i])cnt[u][i]=siz[u]-cnt[u][i];

            res+=1ll*cnt[u][i]*(1<<i);

        }

        sum[u]=res;

    }

    void push_down(int u) {

        if(re[u]) {

            add_rev_tag(son[u][0]);

            add_rev_tag(son[u][1]);

            re[u]=0;

        }

        if(xo[u]) {

            add_xor_tag(son[u][0],xo[u]);

            add_xor_tag(son[u][1],xo[u]);

            xo[u]=0;

        }

    }

    int find(int u,int rk) {

        push_down(u);

        if(siz[son[u][0]]+1==rk)return u;

        if(siz[son[u][0]]>=rk)return find(son[u][0],rk);

        return find(son[u][1],rk-siz[son[u][0]]-1);

    }

    int t(int u) {

        return son[fa[u]][1]==u;

    }

    void rotate(int u) {

        int ret=t(u),f=fa[u],s=son[u][ret^1];

        son[f][ret]=s;if(s)fa[s]=f;son[u][ret^1]=f;

        fa[u]=fa[f];if(fa[f])son[fa[f]][t(f)]=u;

        fa[f]=u;update(f);update(u);

    }

    void splay(int goal,int u) {

        int tmp=fa[goal];

        while(fa[u]!=tmp) {

            if(fa[fa[u]]!=tmp) {

                if(t(fa[u])==t(u))rotate(fa[u]);

                else rotate(u);

            }

            rotate(u);

        }

        if(!tmp)root=u;

    }

    void rever(int l,int r) {

        int u=find(root,l-1),v=find(root,r+1);

        splay(root,u);splay(son[root][1],v);

        add_rev_tag(son[v][0]);

    }

    void change(int l,int r,int d) {

        int u=find(root,l-1),v=find(root,r+1);

        splay(root,u),splay(son[root][1],v);

        add_xor_tag(son[v][0],d);

        update(v);update(u);

    }

    ll query(int l,int r) {

        int u=find(root,l-1),v=find(root,r+1);

        splay(root,u),splay(son[root][1],v);

        return sum[son[v][0]];

    }

}T;

int main() {

    n=read(),m=read();

    for(int i=2;i<=n+1;i++)

        a[i]=read();

    T.prepare();

    for(int i=1;i<=m;i++) {

        int opt=read(),l=read()+1,r=read()+1;

        if(opt==1) T.rever(l,r);

        if(opt==2) {

            int d=read();

            T.change(l,r,d);

        }

        if(opt==3)printf("%lld\n",T.query(l,r));

    }

    return 0;

}

\(fhq\)_\(treap\)版代码如下：

// luogu-judger-enable-o2

#include <ctime>

#include <cstdio>

#include <algorithm>

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

const int maxn=1e5+5;

int n,m;

int a[maxn];

int read() {

    int x=0,f=1;char ch=getchar();

    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

    for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

    return x*f;

}

struct fhq_treap {

    int tot,root;

    ll sum[maxn];bool Rev[maxn];

    int son[maxn][2],fix[maxn],siz[maxn];

    int cnt[maxn][20],val[maxn],tmp[maxn],Xor[maxn];

    void Extract(int *a,int v) {

        for(int i=0;i<20;i++)

            a[i]=(v>>i)&1;

    }

    void update(int p) {

        siz[p]=siz[son[p][0]]+1+siz[son[p][1]];

        sum[p]=sum[son[p][0]]+val[p]+sum[son[p][1]];

        for(int i=0;i<20;i++)

            cnt[p][i]=cnt[son[p][0]][i]+((val[p]>>i)&1)+cnt[son[p][1]][i];

    }

    void build(int l,int r,int lst) {

        if(r<l)return;

        if(l==r) {

            siz[l]=1,val[l]=sum[l]=a[l];

            fix[l]=rand(),son[lst][l>lst]=l;

            Extract(cnt[l],a[l]);return;

        }

        int mid=(l+r)>>1;

        fix[mid]=rand();

        val[mid]=a[mid];

        son[lst][mid>lst]=mid;

        build(l,mid-1,mid);build(mid+1,r,mid);

        update(mid);

    }

    void prepare() {

        tot=n;build(1,n,0);root=(n+1)>>1;

    }

    void add_rev_tag(int p) {

        if(!p)return;

        Rev[p]^=1;swap(son[p][0],son[p][1]);

    }

    void add_xor_tag(int p,int v) {

        if(!p)return;

        val[p]^=v,Xor[p]^=v;

        ll res=0;Extract(tmp,v);

        for(int i=0;i<20;i++) {

            if(tmp[i])cnt[p][i]=siz[p]-cnt[p][i];

            res+=1ll*(1<<i)*cnt[p][i];

        }

        sum[p]=res;

    }

    void push_down(int p) {

        if(Rev[p]) {

            add_rev_tag(son[p][0]);

            add_rev_tag(son[p][1]);

            Rev[p]=0;

        }

        if(Xor[p]) {

            add_xor_tag(son[p][0],Xor[p]);

            add_xor_tag(son[p][1],Xor[p]);

            Xor[p]=0;

        }

    }

    pii split(int u,int rk) {

        if(!rk)return make_pair(0,u);

        if(rk==siz[u])return make_pair(u,0);

        push_down(u);

        if(siz[son[u][0]]>=rk) {

            pii tmp=split(son[u][0],rk);

            son[u][0]=tmp.second,update(u);

            return make_pair(tmp.first,u);

        }

        else {

            pii tmp=split(son[u][1],rk-siz[son[u][0]]-1);

            son[u][1]=tmp.first,update(u);

            return make_pair(u,tmp.second);

        }

    }

    int merge(int a,int b) {

        if(!a||!b)return a+b;

        push_down(a),push_down(b);

        if(fix[a]>fix[b])return son[a][1]=merge(son[a][1],b),update(a),a;

        else return son[b][0]=merge(a,son[b][0]),update(b),b;

    }

    void rever(int l,int r) {

        pii tmp1=split(root,r);

        pii tmp2=split(tmp1.first,l-1);

        add_rev_tag(tmp2.second);

        root=merge(merge(tmp2.first,tmp2.second),tmp1.second);

    }

    void change(int l,int r,int v) {

        pii tmp1=split(root,r);

        pii tmp2=split(tmp1.first,l-1);

        add_xor_tag(tmp2.second,v);

        root=merge(merge(tmp2.first,tmp2.second),tmp1.second);

    }

    ll query(int l,int r) {

        pii tmp1=split(root,r);

        pii tmp2=split(tmp1.first,l-1);

        ll res=sum[tmp2.second];

        root=merge(merge(tmp2.first,tmp2.second),tmp1.second);

        return res;

    }

}T;

int main() {

    n=read(),m=read();

    for(int i=1;i<=n;i++)

        a[i]=read();

    T.prepare();

    for(int i=1;i<=m;i++) {

        int opt=read(),l=read(),r=read();

        if(opt==1)T.rever(l,r);

        if(opt==2) {

            int d=read();

            T.change(l,r,d);

        }

        if(opt==3)printf("%lld\n",T.query(l,r));

    }

    return 0;

}

最新文章

1. echo命令
2. spring 事务回滚
3. hdu5651 xiaoxin juju needs help (多重集的全排列+逆元)
4. MyBatis源码分析-SQL语句执行的完整流程
5. 《虚拟伙伴》AR增强现实应用开发总结
6. R语言进阶
7. linux 打造man中文帮助手册
8. 在Xcode5和Android Studio添加工程间的依赖
9. javascript 三个 对话框
10. 【linux】rpm常见命令
11. Poj 2887-Big String Splay
12. 【Git】Git教程
13. 查找jar包的站点
14. php打包文件为ZIP包后下载到本地
15. Android双击Home键返回桌面
16. js开发模式
17. BZOJ5291/洛谷P4458/LOJ#2512 [Bjoi2018]链上二次求和 线段树
18. 到达一个数 Reach a Number
19. Dubbo(1)简介和Zookeeper安装
20. centos 升级python2.6 到python3.3(实测可行)

热门文章

1. Android中BaseAdapter使用基础点
2. oracle序列sequence
3. iOS对象（字典或数组）转化为JSon字符串
4. 九度OJ 1048：判断三角形类型 （基础题）
5. mysql系列之8.mysql高可用 (mha4mysql)
6. [TroubleShooting]Neither the partner nor the witness server instance for database is availble
7. subline 的常用命令
8. java ClassLoader类加载器
9. StreamWriter结合UTF-8编码使用不当，会造成BOM（Byte Order Mark ）问题生成乱码（转载）
10. Android中m、mm、mmm、mma、mmma的区别