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)


相关推荐

  • Glassfish4.1安装及配置[通俗易懂]

    Glassfish4.1安装及配置[通俗易懂]安装及配置下载及安装详情见官网。关于文档上述下载的GlassFish为开源版本,文档见GlassFishServerDocumentation。不过,在使用中发现该文档的参数并不全,比如,ReferenceManual中提供了命令create-auth-realm用来手动创建realm,现在要设定realm所在的domain,却没有找到相应的参数。反倒是在GlassFish商业版SunG

  • WebView中的视频全屏的相关操作

    WebView中的视频全屏的相关操作

    2021年11月30日
  • 小弟博客_博客来网址

    小弟博客_博客来网址原来位于Google上的博客在国内基本不能访问了,现在找了个新家,准备发布一些我这些年来编写的东西,主要集中在算法研究和程序设计上,语言主要是.NET(C#)和Delphi,当然,其它软件开发、算法相关的许多东西也会陆续加入,例如:JavaScript、XML、Web技术等等,另外也会有极少量的与IT行业不相关的东西。旧的不去,新的不来,旧博客关了也好,新博客总算是中文的…

  • osx安装失败_OSX

    osx安装失败_OSX目录1.MacPorts是什么2.MacPorts安装方法2.1使用安装器安装2.2源码安装2.3同步repositorytree和获取最新package3.更新失败的解决方法4.ports使用…

  • mysql长轮询_ajax的轮询和长轮询

    mysql长轮询_ajax的轮询和长轮询概念:轮询(polling):客户端按规定时间定时像服务端发送ajax请求,服务器接到请求后马上返回响应信息并关闭连接。概念总是枯燥的,只有代码方能解心头之快前段代码:index.html:vargetting={url:’server.php’,dataType:’json’,success:function(res){console.log(res);}};//关键在这里,Ajax定时…

  • pycharm使用技巧及常用快捷键_键盘怎么自定义改键

    pycharm使用技巧及常用快捷键_键盘怎么自定义改键PyCharm自身提供了大量实用的快捷键,但是由于自己之前其他软件的快捷键使用习惯与此不同,这就需要在PyCharm量身DIY属于自己的快捷键了。快来按照下面的流程操作吧!!!1、File—&gt;Settings【Settings的快捷键大家看到了嘛!!!Ctrl+Alt+S】2、Keymap—&gt;齿轮状设置—&gt;Duplicate建议在设置快捷键之前…

发表回复

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

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