当前位置: 首页 > article >正文

【最大异或和——可持久化Trie】

题目

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 6e5+10; //注意这里起始有3e5,又可能插入3e5
const int M = N * 25;

int rt[N], tr[M][2]; //根,trie
int idx, cnt, br[M]; //根分配器,点分配器,点的相对版本
char op[2];
int n, m, s;

void insert(int v)
{
    rt[++idx] = ++cnt; //创建新根
    
    int x = rt[idx-1]; //前一个版本
    int y = rt[idx]; //当前版本
    for(int i = 23; i >= 0; i--)
    {
        int j = v >> i & 1; //提取每一位
        tr[y][!j] = tr[x][!j]; //继承不同位值的点
        tr[y][j] = ++cnt; //创建相同位值的点
        x = tr[x][j], y = tr[y][j]; //跳
        br[y] = br[x]+1; //声明所创建的相同位值得点为brand-new
    }
}
int query(int l, int r, int v) //选择版本l-1和r
{
    int retv = 0;
    
    int x = rt[l-1];
    int y = rt[r];
    for(int i = 23; i >= 0; i--)
    {
        int j = v >> i & 1;
        if(br[tr[y][!j]] > br[tr[x][!j]]) //若所求版本不一致,认定可行
        {
            y = tr[y][!j];
            x = tr[x][!j];
            retv += 1 << i;
        }
        else //若所求版本一致,认定冲突
        {
            y = tr[y][j];
            x = tr[x][j];
        }
    }
    
    return retv;
}

int main()
{
    insert(0);
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
    {
        int x;
        scanf("%d", &x);
        s ^= x;
        insert(s);
    }
    for(int i = 1; i <= m; i++)
    {
        int l;
        scanf("%s%d", op, &l);
        
        if(op[0] == 'A')
            s ^= l, insert(s);
        else if(op[0] == 'Q')
        {
            int r, x;
            scanf("%d%d", &r, &x);
            printf("%d\n", query(l, r, s ^ x));
        }
    }
}


http://www.kler.cn/a/589856.html

相关文章:

  • STM32输入捕获采集超声波模块HC-SR04响应的高电平
  • 自动化APP测试APPium的元素等待
  • Django Rest Framework 创建纯净版Django项目部署DRF
  • Android Fresco 框架缓存模块源码深度剖析(二)
  • 爬虫代码中需要设置哪些HTTP头部信息?
  • 在遇见— 再遇见
  • docker入门篇
  • Windows 图形显示驱动开发-WDDM 3.0功能- 硬件翻转队列(一)
  • WPF窗口读取、显示、修改、另存excel文件——CAD c#二次开发
  • wordpress导入mysql数据库文件的方法及注意事项
  • Python----计算机视觉处理(Opencv:图片颜色识别:RGB颜色空间,HSV颜色空间,掩膜)
  • 基于CPLD+MCU的3U机箱模拟量采样板(AIO-I),主要功能由模拟量采集,模拟量输出,PWM采集和输出
  • Qt SQL-1
  • 洛谷 P1182 数列分段 Section II 二分详细讲解
  • vue3vue-elementPlus-admin框架中form组件的upload写法
  • 人工智能辅助 3D 建模:Claude + Blender MCP 体验
  • Java高频面试之集合-13
  • vllm-openai多服务器集群部署AI模型
  • 365天之第P10周:Pytorch实现车牌识别
  • [HelloCTF]PHPinclude-labs超详细WP-Level 0