首页 > 其他分享 >[ABC308G] Minimum Xor Pair Query 题解

[ABC308G] Minimum Xor Pair Query 题解

时间:2023-07-26 19:44:15浏览次数:41  
标签:Xor int 题解 Query num ABC308G return bit include

Minimum Xor Pair Query

题目大意

维护一个序列,支持动态插入,删除,查询最小异或对。

思路分析

看到查询最小异或对首先想到 01Trie,但 01Trie 不支持删除,考虑暴力套一个线段树分治。

需要预处理出每个元素的存活区间,这里使用了 map<int,vector<int>>。注意,有的元素会存活到最后,需要特判。

时间复杂度为 \(O(n\log n\log V)\),其中 \(V\) 是值域。

这个做法有较强的可扩展性,非常无脑。

代码

代码非常好写,只有 2k。

#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;
const int N=300300,M=10001000;
#define inf 2147483647

int n,op,in1;
int ans[N],type[N];

map<int,vector<int>> mp;//用于预处理元素存活区间

struct Trie{//递归版 Trie
    #define c (x>>bit&1)
    int a[M][2],num[M];
    int tot;
    void insert(int p,int bit,int x){
        if(!~bit) return ;
        if(!a[p][c]) a[p][c]=++tot;
        insert(p=a[p][c],bit-1,x);
        num[p]++;
    }
    void del(int p,int bit,int x){
        if(!~bit) return ;
        del(p=a[p][c],bit-1,x);
        num[p]--;
    }
    int query(int p,int bit,int x){
        if(!~bit) return 0;
        bool f=!num[a[p][c]];
        return query(a[p][c^f],bit-1,x)+f*(1<<bit);
    }
}trie;

struct ST{//线段树
    #define mid ((l+r)>>1)
    vector<int> a[N<<2];
    void add(int p,int l,int r,int x,int y,int k){//增加元素
        if(x<=l&&r<=y){a[p].push_back(k);return ;}
        if(x<=mid) add(p<<1,l,mid,x,y,k);
        if(y>mid) add(p<<1|1,mid+1,r,x,y,k);
    }
    void dfs(int p,int l,int r,int res){//遍历全树
        for(auto it:a[p]){
            res=min(res,trie.query(0,30,it));
            trie.insert(0,30,it);
        }
        if(l==r) ans[l]=res;
        else{
            dfs(p<<1,l,mid,res);//答案下传
            dfs(p<<1|1,mid+1,r,res);
        }
        for(auto it:a[p]) trie.del(0,30,it);
    }
}tree;

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&op);
        if(op==1){
            scanf("%d",&in1);
            mp[in1].push_back(i);
        }
        if(op==2){
            scanf("%d",&in1);
            tree.add(1,1,n,mp[in1].back(),i-1,in1);
            mp[in1].pop_back();
        }
        if(op==3) type[i]=1;
    }
    for(auto it:mp)
        for(auto it2:it.second)
            tree.add(1,1,n,it2,n,it.first);//特判最后的元素
    tree.dfs(1,1,n,inf);
    for(int i=1;i<=n;i++)
        if(type[i]) cout<<ans[i]<<'\n';
    return 0;
}

标签:Xor,int,题解,Query,num,ABC308G,return,bit,include
From: https://www.cnblogs.com/TKXZ133/p/17583400.html

相关文章

  • 网络瘤24题解+总结
    目录网络流24题太空飞行计划最大权闭合子图模型最小路径覆盖问题Trick总结网络流24题顺序主观决定太空飞行计划教训:(开始想费用流,搞半天出不来)网络流解决最大/小费用问题,要么最小割最大流,要么最小费用流最小费用流的前提是最大流,所以在有一些点可以不取换最优代价的时候,是......
  • P5369 [PKUSC2018] 最大前缀和 题解
    传送门题目大意给定一个序列,求任意重排\(n!\)中情况所以的最大非空前缀和的和。模\(998244353\)。\(n\e20\),\(\sum|a_i|\le10^9\)题目解析考虑最大前缀和的性质,有:对于最大前缀和部分,所有的真后缀大于等于零。(最大前缀和可能小于零)对于不在最大前缀和的后半部分,所......
  • [JOI 2022 Final] 自学 题解
    洛谷传送门1.题意简述:一个学期有\(N\)天\(N*M\)节课,每天的第\(i\)节课可以选择效果\(a_i\)的学习与\(b_i\)的自习。问应如何安排每节课,使所有功课最小值最大?2.思路:这道题想直接模拟非常麻烦,但是如果我们能够灵活运用二分算法,这道题就非常简单了。考虑到数据范围较......
  • [ABC308G]MinimumXorPairQuery
    [ABC308G]MinimumXorPairQuery必须知道的性质:对于三个非负整数\(x,y,z(x<y<z)\),有\(\min(x\bigoplusy,y\bigoplusz)<x\bigoplusz\)。证明从二进制最高位开始\(i=\logV\),对\(x,y,z\)进行如下操作:若它们的当前位都两两相同,继续跳到下一位i--。根据......
  • luogu P9474 [yLOI2022] 长安幻世绘 详细题解
    原题:P9474[yLOI2022]长安幻世绘看到很多大佬的题解直接讲了做法,本蒟蒻看得不是很懂,调了很久才把这题做出来,于是写了这篇比较详细的题解谈一下我做这题从头到尾的思路,希望对各位有帮助qwq。思路我们首先思考这样一个问题,如果已经知道最终答案对应的最大值和最小值,又不知道题......
  • AT_agc017_b 题解
    洛谷链接&Atcoder链接本篇题解为此题较简单做法,请放心阅读。题目简述一共有\(n\)个格子,给定两个整数\(A,B\)分别位于第\(1\)和第\(n\)格,中间有\(n−2\)个空格。询问是否存在一种填数方案满足任意相邻两个数之差的绝对值在\([C,D]\)之间。依次输入\(n,a,b,c,d\)......
  • AT_arc149_a 题解
    洛谷链接&Atcoder链接本篇题解为此题较简单做法及较少码量,并且码风优良,请放心阅读。题目简述求满足以下条件的小于\(10^n\)数最大是多少?每一位数字均相同;是\(m\)的倍数。数据范围:\(1\len\le10^5\),\(1\lem\le10^9\)。思路首先每位数字都相同很好满足,仅需......
  • 题解:【ICPC WF 2021 L】 Where Am I?
    题目链接这年WF较为简单的一道了,直接模拟即可。首先可以预处理出它顺时针螺旋轨迹的移动步数,方便过会算距离直接查表。我偷懒直接用map记录的距离表,这样不用处理复数下标的问题。注意到\(X\)的数量不会超过\(100\)个,所以我们可以反过来从标记点上入手。找出所有的标记点,......
  • 洛谷 P2894 [USACO08FEB] Hotel G 题解
    题目链接P2894[USACO08FEB]HotelG-洛谷|计算机科学教育新生态(luogu.com.cn)分析考虑用线段树维护区间信息维护sum(最大连续空房间数)如何合并?sum1为max(sum2,sum3)(1的两个子区间)但我们发现若区间为100001(0表示空房间)sum1=4而max(sum2,sum3)=2所以再维护suml(从左开始的......
  • 网络并发每日习题解释版
    网络并发每日习题解释版1.软件开发架构类别软件开发架构类别:软件开发架构是指在软件设计和开发过程中,用于组织和管理软件系统的基本结构。常见的软件开发架构类别包括:分层架构(LayeredArchitecture):将软件系统划分为多个相互独立的层,每个层都有特定的功能和责任。客户端......