首页 > 其他分享 >CF587E Duff as a Queen

CF587E Duff as a Queen

时间:2023-11-06 22:24:18浏览次数:31  
标签:dots 10 le Duff Queen 异或 CF587E 线性 oplus

维护序列,支持:

  • 区间异或

  • 查询区间子集异或值种数(包含空集)

\(n\le 2\times 10^5\),\(1\le q\le 4\times 10^4\),值域 \([1,10^9]\),TL=7s.


经典题。

操作 2 相当于查询区间线性基大小。

由于不能维护区间异或,作差分 \(b_i=a_i\oplus a_{i-1}\)。

可以得到 \(a_i=\oplus b_1\oplus \dots\oplus b_i\).

不难发现 \(a_l,\dots,a_r\) 的线性基相当于 \(a_l,b_{l+1},\dots b_r\) 的线性基。

操作 \(1\) 相当于单点异或,用线段树维护,查询时加入 \(a_l\) 查询线性基大小即可。

时间复杂度 \(O(q\log n\log^2 V)\).


标签:dots,10,le,Duff,Queen,异或,CF587E,线性,oplus
From: https://www.cnblogs.com/SError0819/p/17813905.html

相关文章

  • 【刷题笔记】52. N-Queens II
    题目Then-queenspuzzleistheproblemofplacingnqueensonann×nchessboardsuchthatnotwoqueensattackeachother.Givenanintegern,returnthenumberofdistinctsolutionstothen-queenspuzzle.Example:Input:4Output:2Explanation:Therea......
  • [LeetCode] 1222. Queens That Can Attack the King
    Ona 0-indexed 8x8 chessboard,therecanbemultipleblackqueensadonewhiteking.Youaregivena2Dintegerarray queens where queens[i]=[xQueeni,yQueeni] representsthepositionofthe ith blackqueenonthechessboard.Youarealsogivena......
  • 【刷题笔记】51. N-Queens
    题目Then-queenspuzzleistheproblemofplacingnqueensonann×nchessboardsuchthatnotwoqueensattackeachother.Givenaninteger n,returnalldistinctsolutionstothe n-queenspuzzle.Eachsolutioncontainsadistinctboardconfigurationoft......
  • [LeetCode] 51. N-Queens
    The n-queens puzzleistheproblemofplacing n queensonan nxn chessboardsuchthatnotwoqueensattackeachother.Givenaninteger n,return alldistinctsolutionstothe n-queenspuzzle.Youmayreturntheanswerin anyorder.Eachsolution......
  • 52. N-Queens II刷题笔记
    回溯算法,参考该题解classSolution:deftotalNQueens(self,n:int)->int:diag1=set()diag2=set()usedCols=set()returnself.helper(n,diag1,diag2,usedCols,0)defhelper(self,n,diag1,diag2,usedCols,......
  • openstack queen版本的安装案例
    一.基本环境描述操作系统采用ubutun16.04,系统最少8G内存,80G硬盘,控制节点和网络节点部署在同一个host,计算和控制节点采用双网卡。参考install.guide手册的第二种网络模型。Blockstorage和objectstorage不做部署。拓扑图中的地址要根据实际的环境进行相应的替换。provider网络部......
  • REDQUEEN译文
    Abstract近年来,基于模糊的自动化软件测试经历了复兴。尤其是反馈驱动的模糊化已经因其在有限的输入语料库中有效地执行随机测试的能力而广为人知。尽管取得了很多进展,但两个常见的问题是幻数和(嵌套的)校验和。通常使用诸如污点跟踪和符号执行等昂贵的计算方法来克服这些障碍。不幸的......
  • Iain McQueen:从移动应用开发中总结出的五个教训
    编者注:本文编译自IainMcQueen发表在Posterous上的博文“WhatILearnedBuildingaMobileFriendlyWebApp”。自今年11月19日发布第一版Swiperoo起,Dave和我就开始时不时谈论开发初期遇到的各种问题。我想,一定也有很多其他移动应用开发者会遇到和我们一样的问题,因此,在这里把......
  • Linux 脚本一键安装openstack(queens版本)
                Linux脚本一键安装openstack(queens版本)分为三个文件,一个配置文件local_settings,两个脚本文件,一个为主节点脚本,一个为计算节点脚本。......
  • [LeetCode]N-Queens II
    QuestionFollowupforN-Queensproblem.Now,insteadoutputtingboardconfigurations,returnthetotalnumberofdistinctsolutions.本题难度Hard。【思路】​N......