异或和左移的优先级_异或链表

异或和左移的优先级_异或链表给定一个非负整数序列 a,初始长度为 N。有 M 个操作,有以下两种操作类型:A x:添加操作,表示在序列末尾添加一个数 x,序列的长度 N 增大 1。Q l r x:询问操作,你需要找到一个位置 p,满足 l≤p≤r,使得:a[p] xor a[p+1] xor … xor a[N] xor x 最大,输出这个最大值。输入格式第一行包含两个整数 N,M,含义如问题描述所示。第二行包含 N 个非负整数,表示初始的序列 A。接下来 M 行,每行描述一个操作,格式如题面所述。输出格式每个询问操

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

给定一个非负整数序列 a,初始长度为 N。

有 M 个操作,有以下两种操作类型:

A x:添加操作,表示在序列末尾添加一个数 x,序列的长度 N 增大 1。
Q l r x:询问操作,你需要找到一个位置 p,满足 l≤p≤r,使得:a[p] xor a[p+1] xor … xor a[N] xor x 最大,输出这个最大值。
输入格式
第一行包含两个整数 N,M,含义如问题描述所示。

第二行包含 N 个非负整数,表示初始的序列 A。

接下来 M 行,每行描述一个操作,格式如题面所述。

输出格式
每个询问操作输出一个整数,表示询问的答案。

每个答案占一行。

数据范围
N,M≤3×105,0≤a[i]≤107。

输入样例:
5 5
2 6 4 3 6
A 1 
Q 3 5 4 
A 4 
Q 5 7 0 
Q 3 6 6 
输出样例:
4
5
6
#include<bits/stdc++.h>
using namespace std;
const int K = 25;
const int M = 6e6 + 10;
const int N = 6e6 + 10;
int trie[M * K][2],ctx;
int root[N],max_id[M * K];
int s[N];
int query(int l,int p,int C){ 
   
    if(root == 0)return 0;
    for(int i = 24;i >= 0;i --){ 
   
        int a = ((C >> i) & 1);
        if(trie[p][a ^ 1] && max_id[trie[p][a ^ 1]] >= l){ 
   
            p = trie[p][a ^ 1];
        }else { 
   
            p = trie[p][a];
        }
    }
    return s[max_id[p]];
}
void insert(int bit,int x,int p,int q,int d){ 
   
    if(bit < 0){ 
   
        max_id[p] = d;
        return;
    }else{ 
   
        int a = ((x >> bit) & 1);
        if(q)trie[p][a ^ 1] = trie[q][a ^ 1];
        trie[p][a] = ++ ctx;
        int t = p;
        q = trie[q][a],p = trie[p][a];
        insert(bit - 1,x,p,q,d);
        max_id[t] = max(max_id[trie[t][0]],max_id[trie[t][1]]);
    }
}
int main(){ 
   
    int n,m;
    cin>>n>>m;
    int now = 0,x;
    int e = 0;
    for(int i = 0;i < n;i ++){ 
   
        scanf("%d",&x);
        root[i + 1] = ++ ctx;
        insert(24,x ^ now,root[i + 1],root[i],i + 1);
        now ^= x;
        s[i + 1] = now;
        e = x;
    }
    char t;
    int l,r;
    int c = 1;
    for(int i = 0;i < m; i++){ 
   
        scanf(" %c",&t);
        if(t == 'A'){ 
   
            scanf("%d",&x);
            root[n + c] = ++ ctx;
            insert(24,now ^ x,root[n + c],root[n + c - 1],n + c);
            now ^= x;
            s[n + c] = now;
            e = x;
            c ++;
        }
        else { 
   
            scanf("%d %d %d",&l,&r,&x);
            printf("%d\n",(query(l - 1,root[r - 1],now ^ x) ^ (now ^ x)));
        }
    }
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

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

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

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

(0)


相关推荐

发表回复

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

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