专栏首页数据结构与算法洛谷P4592 [TJOI2018]异或(可持久化01Trie)

洛谷P4592 [TJOI2018]异或(可持久化01Trie)

题意

题目链接

可持久化01Trie板子题

对于两个操作分别开就行了

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 4e5 + 10, SS = MAXN * 42 + 10;
const int B = 31;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, Q, a[MAXN], siz[MAXN], son[MAXN], top[MAXN], fa[MAXN], dep[MAXN], dfn[MAXN], cnt, rev[MAXN];
vector<int> v[MAXN];
struct Trie {
    int ch[SS][2], siz[SS], tot, root[SS];
    void insert(int &k, int pre, int v) {
        k = ++tot; int now = k;
        for(int i = B; ~i; i--) {
            int nxt = v >> i & 1;
            ch[now][nxt ^ 1] = ch[pre][nxt ^ 1];
            now = ch[now][nxt] = ++tot; pre = ch[pre][nxt];
            siz[now] = siz[pre] + 1;
        }
    }
    int Query1(int pre, int now, int v) {
        int ans = 0;
        for(int i = B; ~i; i--) {
            int nxt = v >> i & 1;
            if(siz[ch[now][nxt ^ 1]] - siz[ch[pre][nxt ^ 1]]) ans += (1 << i), now = ch[now][nxt ^ 1], pre = ch[pre][nxt ^ 1];
            else now = ch[now][nxt], pre = ch[pre][nxt];
        }
        return ans;
    }
    int Query2(int x, int y, int lca, int fafa, int v) {
        int ans = 0;
        for(int i = B; ~i; i--) {
            int nxt = v >> i & 1;
            if(siz[ch[x][nxt ^ 1]] + siz[ch[y][nxt ^ 1]] - siz[ch[lca][nxt ^ 1]] - siz[ch[fafa][nxt ^ 1]]) 
                ans += (1 << i), x = ch[x][nxt ^ 1], y = ch[y][nxt ^ 1], lca = ch[lca][nxt ^ 1], fafa = ch[fafa][nxt ^ 1];
            else x = ch[x][nxt], y = ch[y][nxt], lca = ch[lca][nxt], fafa = ch[fafa][nxt];
        }
        return ans;
    }
} T[2];
void dfs1(int x, int _fa) {
    siz[x] = 1; T[1].insert(T[1].root[x], T[1].root[_fa], a[x]); dep[x] = dep[_fa] + 1;
    dfn[x] = ++cnt; rev[cnt] = x; fa[x] = _fa;
    for(auto &to : v[x]) {
        if(to == _fa) continue;
        dfs1(to, x);
        siz[x] += siz[to];
        if(siz[to] > siz[son[x]]) son[x] = to;
    }
}
void dfs2(int x, int topf) {
    top[x] = topf;
    if(!son[x]) return ;
    dfs2(son[x], topf);
    for(auto &to : v[x]) {
        if(top[to]) continue;
        dfs2(to, to);
    }
}
int LCA(int x, int y) {
    while(top[x] ^ top[y]) {
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        x = fa[top[x]];
    }
    return dep[x] < dep[y] ? x : y;
}
signed main() {
    N = read(); Q = read();
    for(int i = 1; i <= N; i++) a[i] = read();
    for(int i = 1; i <= N - 1; i++) {
        int x = read(), y = read();
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs1(1, 0);
    dfs2(1, 1);
    for(int i = 1; i <= N; i++) 
        T[0].insert(T[0].root[i], T[0].root[i - 1], a[rev[i]]);
    while(Q--) {
        int opt = read(), x = read(), y = read(), z;
        if(opt == 1) cout << T[0].Query1(T[0].root[dfn[x] - 1], T[0].root[dfn[x] + siz[x] - 1], y) << '\n';
        else {
            int lca = LCA(x, y);
            z = read(), cout << T[1].Query2(T[1].root[x], T[1].root[y], T[1].root[lca], T[1].root[fa[lca]], z) << '\n';
        }
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • PHP扩展开发(七)Zend 线程安全

    在PHP诞生的初期,它总是以单线程的CGI方式运行的,因此,根本不需要考虑多线程问题,因为进程的处理不会超过单个请求。

    用户2131907
  • Infor Baan ERP LN里的On Case用法

    对于程序员来讲,if,elseif这种判断语句肯定用的比较多,在asp里有select case,在.net里面有switch case的用法,在Baan里面有...

    崔文远TroyCui
  • 【译】JWT – Json Web Token

    JWT是一种用于双方之间传递安全信息的简洁的、URL安全的表述性声明规范。JWT作为一个开放的标准(RFC 7519),定义了一种简洁的,自包含的方法用于通信双...

    用户2131907
  • PHP扩展开发(六)PHP扩展生命周期

    上述代码经过宏替换之后,实际上是声明了一个名为zend_sample4_globals的结构体。

    用户2131907
  • 分享几个Flowportal.Net BPM中的几个有用的Sql语句

    第一个要分享的是获取当前的申请状态以及当前的处理人,虽然我们很容易通过BPMInstProcSteps这张表找到FinishAt is Null的记录,但是如果...

    崔文远TroyCui
  • Php扩展开发(四)Php扩展开发相关问题

    在./configure的时候,增加选项enable-maintainer-zts将会按照线程安全的方式进行 编译时检查,即使在Cli模式下使用,也会检查是否...

    用户2131907
  • 一段从Infor ERP LN(Baan)的Oracle数据库中导出数据到SQL Server的SQL语句

    保存一段从Baan ERP LN的Oracle数据库中导出数据到SQL Server的SQL语句,前提是在MSSQL 2005中建立Link Server。

    崔文远TroyCui
  • Vagrant使用技巧

    在使用Vagrant过程中,难免会出现一些不稳定的因素而造成一些使用上的bug,因此,Vagrant提供了Debug日志的方式用于调试,可以方便的查找错误的原因...

    用户2131907
  • 【译】YAML格式入门

    根据官方的YAML站点所述,YAML是面向所有编程语言的对人类友好的数据序列化标准。

    用户2131907
  • 我的ODP.NET开发之路3-Oracle Package/Procedure/Function

    上周的项目进展比较大,完成了几个重大的功能。这其中涉及到在Oracle中创建新表、序列、索引、触发器、包、存储过程、函数,当然了也在实战中学习了几个.Net的D...

    崔文远TroyCui

扫码关注云+社区

领取腾讯云代金券