首页 > 其他分享 >Luogu P4592 [TJOI2018]异或 做题记录

Luogu P4592 [TJOI2018]异或 做题记录

时间:2023-01-09 15:57:52浏览次数:52  
标签:ch maxid int Luogu top dep 异或 res TJOI2018

随机跳的。

树上维护序列,显然树剖。维护异或,显然 01trie

01trie 维护区间异或,显然可持久化一下。

看到时限很大,显然可以双 log

于是跑一边树剖,再根据 id 暴力建一个 可持久化01trie,单操 \(\mathrm{O(\log n \log w)}\)

(当然可以树上差分优成 \(\mathrm{O(\log w)}\),但是不想写了。)

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#define rep(i, a, b) for (int i = (a); i <= (b); i ++ )
#define rop(i, a, b) for (int i = (a); i < (b); i ++ )
#define dep(i, a, b) for (int i = (a); i >= (b); i -- )
#define dop(i, a, b) for (int i = (a); i > (b); i -- )

using namespace std;

using LL = long long;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;

int read() {
    int f = 1, s = 0; char ch = getchar();
    for (; ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') f = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48);
    return s * f;
}

const int N = 100010, M = N << 1;
const long long INF = 1 << 30;

int h[N], e[M], ne[M], idx;
int n, m, w[N], nw[N], top[N];
int son[N], sz[N], id[N], cnt;
int fa[N], dep[N];

struct node {
    node *s[2]; int maxid;
    node() { s[0] = s[1] = NULL; maxid = 0; }
}*root[N], pool[N << 5], *tail; // 开个内存池会快很多诶

void add(int a, int b) {
    e[ ++ idx] = b, ne[idx] = h[a], h[a] = idx;
}

// ------------ tree cut ----------------
void dfs1(int u, int father, int depth) {
    dep[u] = depth, fa[u] = father, sz[u] = 1;
    for (int i = h[u]; i; i = ne[i]) {
        int j = e[i];
        if (j == father) continue;
        dfs1(j, u, depth + 1);
        sz[u] += sz[j];
        if (sz[son[u]] < sz[j]) son[u] = j;
    }
}
void dfs2(int u, int t) {
    top[u] = t, id[u] = ++ cnt, nw[cnt] = w[u];
    if (son[u]) dfs2(son[u], t);

    for (int i = h[u]; i; i = ne[i]) {
        int j = e[i];
        if (j == fa[u] || j == son[u]) continue;
        dfs2(j, j);
    }
}

// ------------- 01trie ---------------

void build() {
    tail = pool;
    node *u = root[0] = new(tail ++ ) node();
    dep(i, 30, 0) u -> s[0] = new(tail ++ ) node(), u = u -> s[0];
}
void insert(int x) {
    node *u = root[x] = new(tail ++ ) node(), *p = root[x - 1];
    int v = nw[x];
    dep(i, 30, 0) {
        if (p) *u = *p;
        u -> maxid = max(u -> maxid, x);
        int t = (v >> i) & 1; u -> s[t] = new(tail ++ ) node();
        u = u -> s[t]; p = p ? p -> s[t] : NULL;
    }
    u -> maxid = max(u -> maxid, x);
}
LL query(node *u, int x, int lim) {
    dep(i, 30, 0) {
        int t = (x >> i) & 1;
        if (u -> s[t ^ 1] && u -> s[t ^ 1] -> maxid >= lim) u = u -> s[t ^ 1];
        else u = u -> s[t];
    }
    return (LL)x ^ nw[u -> maxid];
}
LL query(int u, int v, int z) {
    LL res = -INF;
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        res = max(res, query(root[id[u]], z, id[top[u]]));
        u = fa[top[u]];
    }
    if (dep[u] < dep[v]) swap(u, v);
    res = max(res, query(root[id[u]], z, id[v]));
    return res;
}

int main() {
    n = read(), m = read();
    for (int i = 1; i <= n; i ++ )
        w[i] = read();
    for (int i = 1, a, b; i < n; i ++ ) {
        a = read(), b = read();
        add(a, b), add(b, a);
    }

    dfs1(1, -1, 1), dfs2(1, 1); build();
    for (int i = 1; i <= n; i ++ )
        insert(i);

    while (m -- ) {
        int op = read(), x = read(), y, z;
        if (op == 1) {
            z = read();
            printf("%lld\n", query(root[id[x] + sz[x] - 1], z, id[x]));
        }
        else {
            y = read(), z = read();
            printf("%lld\n", query(x, y, z));
        }
    }
    return 0;
}

标签:ch,maxid,int,Luogu,top,dep,异或,res,TJOI2018
From: https://www.cnblogs.com/LcyRegister/p/17037256.html

相关文章

  • ACWING 4645. 选数异或
    url:4645.选数异或-AcWing题库题意:给n个数,再给m次查询,给一个数x每次询问给一个区间l,r,问是否能从$[l,r]$中选出两个下标不同的数使得它们的异或值等于x 思路......
  • 选数异或
    选数异或给定一个长度为$n$的数列$A_1,A_2,\ldots,A_n$和一个非负整数$x$,给定$m$次查询,每次询问能否从某个区间$[l,r]$中选择两个下标不同的数使得他们的异或等......
  • luogu P5037 抓捕
    ##题意有$n$个点的图,任意一点$x$到可去另外一点$y$必须互质,即$\gcd(x,y)=1$。图无边权,但是拥有点权。求到终点$en$的最短距离。---##思路此题需使用Dijks......
  • Luogu P4591 [TJOI2018] 碱基序列
    链接难度:\(\texttt{省选/NOI-}\)有\(k\)组,每一组有\(a_i\)个字符串\(t_{k,a_i}\),询问分别在每一组选一个字符串拼成的字符串在文本串\(s\)出现的个数的所有情况......
  • LibreOJ L2576 「TJOI2018」str
    链接难度:\(\texttt{?}\)有\(k\)组,每一组有\(a_i\)个字符串\(t_{k,a_i}\),询问分别在每一组选一个字符串拼成的字符串在文本串\(s\)出现的个数的所有情况的总和对......
  • 4645. 选数异或
    4645.选数异或给定一个长度为n的数列A1,A2,⋅⋅⋅,An和一个非负整数x,给定m次查询,每次询问能否从某个区间[l,r]中选择两个下标不同的数使得他们的异或等于x。......
  • 题解: Luogu P8894 「UOI-R1」求和
    题目链接:link前言我的一个学长在一次比赛中出了这道题,然后,我就把这道题切了其实这道题还是比较简单的,然后我就介绍一下我的比赛时的思路和做法30分做法根据标签我......
  • 统计异或值在范围内的数对有多少(01字典树)
    1803.统计异或值在范围内的数对有多少-力扣(Leetcode)题意:   思路:很经典的方法,01字典树,同时在树上多维护一个数据,有多少个节点经过当前节点,记为cnt我们可以......
  • Luogu P2082 区间覆盖(加强版)
    链接难度:普及/提高-有\(n\)个区间\([s_i,t_i]\),求被这\(n\)个区间覆盖的长度。数据范围:\(n\le10^5,1\les_i<t_i\le10^17\)。把每个区间都换成一组匹配的括......
  • luogu P2757 [国家集训队]等差子序列
    Link题解降智了。。。首先我们不需要关心\(Len\)是多少,只需要找到长度为\(3\)的等差子序列就行了。然后就枚举中点\(mid\),看看存不存在\(l<mid<r\)使得\(a_{mi......