XOR key「建议收藏」
建议 收藏 Key XOR
2023-06-13 09:12:26 时间
大家好,又见面了,我是你们的朋友全栈君。
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;
}
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/160207.html原文链接:https://javaforall.cn
相关文章
- Java项目毕业设计:基于springboot+vue的电影视频网站系统「建议收藏」
- 如何用anaconda下载python_如何安装配置anaconda与Pycharm「建议收藏」
- python – 关于pycharm选择运行环境「建议收藏」
- 自动化运维平台搭建(一)「建议收藏」
- LoadRunner教程(16)-LoadRunner SLA分析「建议收藏」
- 深入浅出 超详细 从 线程锁 到 redis 实现分布式锁(篇节 2)「建议收藏」
- 仿朋友圈相册图片选择以及画廊效果「建议收藏」
- VBoxManage 命令详解 (有用)「建议收藏」
- OpenCV—python 边缘检测(Canny)「建议收藏」
- 从零开始学习UCOSII操作系统3–UCOSII启动过程「建议收藏」
- DropDownList的常用属性和事件「建议收藏」
- js把HTML转成对象,将js对象转换为html「建议收藏」
- Flume与Kafka对接「建议收藏」
- 马赛克还原神器—Depix,真的有那么神吗?「建议收藏」
- Oracle数据恢复顾问(Data Recovery Advisor)「建议收藏」
- 成功解决AttributeError: ‘str‘ object has no attribute ‘decode‘「建议收藏」
- Oracle 创建表空间和用户「建议收藏」
- 第九章第四节 流体压强与流速的关系「建议收藏」
- matlab 查看函数,如何查看MATLAB函数的源代码 | 学步园「建议收藏」
- 记 – PC视频播放最强画质教程(Potplayer + madVR)「建议收藏」
- lambda表达式python_Python中的Lambda表达式「建议收藏」
- 使用ComponentOne C1WebGrid控件「建议收藏」
- 单片机毕业设计196例「建议收藏」
- vector subscript out of range数组下标越界错误「建议收藏」
- MySql Povit_MySQL pivot row成动态列数「建议收藏」