XOR key「建议收藏」

XOR key「建议收藏」可持久化trie

大家好,又见面了,我是你们的朋友全栈君。

51nod 1295
可持久化trie,其实和可持久化线段树差不多
之前写过一次,现在加深了一点点对于可持久化的理解

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define ROF(i,a,b) for(int i=a;i>=b;i--)
#define mem(i,a) memset(i,a,sizeof(i))
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define ll long long
#define LL long long
using namespace std;
const int maxn = 5e4+7;
int tr[maxn*40][2],sum[maxn*40],root[maxn];
int n,m,cnt=0,x;

void update(int len,int x,int &u,int v) {
    u = ++cnt;
    for(int i = 0;i<2;i++) tr[u][i] = tr[v][i];
    sum[u] = sum[v]+1;
    if(len==0) return;
    update(len-1,x,tr[u][(x>>len-1)&1],tr[v][(x>>len-1)&1]);
}
int query(int len,int u,int v) {
    int now = 1-((x>>(len-1))&1);
    if(len==0) return 0;
    if(sum[tr[u][now]] > sum[tr[v][now]]) 
        return query(len-1,tr[u][now],tr[v][now])+(1<<(len-1));
    return  query(len-1,tr[u][1-now],tr[v][1-now]);
}

int main() {
    scanf("%d%d",&n,&m);
    for(int i = 1;i<=n;i++) {
        scanf("%d",&x);
        update(30,x,root[i],root[i-1]);
    }
    int l,r;
    for(int i = 1;i<=m;i++) {
        scanf("%d%d%d",&x,&l,&r);
        printf("%d\n",query(30,root[r+1],root[l]));
    }
    return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/160207.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • date类和calendar类的区别_java类中可以定义类吗

    date类和calendar类的区别_java类中可以定义类吗Date类在JDK1.0中,Date类是唯一的一个代表时间的类,但是由于Date类不便于实现国际化,所以从JDK1.1版本开始,推荐使用Calendar类进行时间和日期处理。这里简单介绍一下Date类的使用。1、使用Date类代表当前系统时间                  Dated=newDate();                  System.out.pr

  • 如何干净卸载_怎么把360卸载干净

    如何干净卸载_怎么把360卸载干净Oracle大家都知道下载简单,但是想卸载,没那么轻松,会发现自己卸载不干净,导致再次安装就会失败,现在我就一步一步演示如何彻底卸载Oracle,然后再重新安装。(本机win10)1.停止系统中所有的Oracle服务(win+r—-taskmgr—–服务)2.运行UniversalInstallera、点击应用b、卸载产品c、选择Orac…

    2022年10月21日
  • 基础工具之消息队列、线程池、缓冲区抽象、事件循环和日志实现

    正所谓“工欲善其事,必先利其器”,我们在实现通信设计任务的过程中需要一些基础工具来帮助我们搭建部分基础组件,这些基础工具包括消息队列,线程池,缓冲区抽象,事件循环和日志工具。接下来对这部分基础工具进

    2021年12月28日
  • 虚拟机VMware安装苹果系统macOS,超级详细教程,附文件下载,真教程!!

    虚拟机VMware安装苹果系统macOS,超级详细教程,附文件下载,真教程!!1.准备工作1、虚拟机VMware®Workstation15Pro,小编使用的版本是15pro2、Unlocker或MK-Unlocker3、一个MacOS镜像2.资源下载…

  • 常见手机定位方式浅谈图_夹具常见的定位方式

    常见手机定位方式浅谈图_夹具常见的定位方式前段时间在知乎上回答了一个关于手机定位相关的问题,被一个知友问到“加一个人微信聊天之后,收到了人家的一个视频,随后也把这个人及他发的视频都删除了,几天后在网吧上网,被别人定位到了,勒索了一笔钱,说‘再

  • 生物化学与分子生物学分析技术 Analytical Techniques in Biochemistry and Molecular Biology 英文原版[通俗易懂]

    生物化学与分子生物学分析技术 Analytical Techniques in Biochemistry and Molecular Biology 英文原版[通俗易懂]长期以来,生物化学被定义为生命科学的核心学科,现在它使我们能够以十年前甚至做梦都想不到的方式控制生命系统。随着植物生物学和生物技术在科学议程上不可阻挡地向前发展,其相关性也与日俱增。这本综合卷探讨了植物生物学、生物化学和生物技术研究人员必须掌握的众多实验技术。随着人们对调查生理过程的生化和分子方法的兴趣上升,新的、更快、更敏感的实验程序也在同步发展,使我们能够探索动物和植物有机体的内部运作。ebook获取<<<…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号