首页 > 其他分享 >区间与或

区间与或

时间:2024-10-12 15:10:52浏览次数:5  
标签:lazy 需要 运算 处理 线段 tag 区间

前言

抽象模拟赛, 我现在菜的可怕

题面

疑似自出题, 反正不难, 就不找原题了
挂个 pdf
题目下载

算法

显然可以用线段树维护
观察到与运算和或运算的优先级不好处理, 考虑每一位分开处理(位运算常见处理方法)
如果是与运算, 一旦为 \(0\), 就只需要把前面的或与运算的 \(\rm{lazy_tag}\) 置为 \(0\)
如果是或运算, 那么不需要处理, 只需要记录为 \(1\) 即可
代码显然非常好打, 于是略

但是这题卡常严重, 于是思考能不能用一个线段树解决
对于一个数来说, 当之前的与运算把它其中一位置为 \(0\), 而后面又有或运算将其置为 \(1\), 那么在最终的答案统计中不应该与上这个 \(0\)
因此只需要在每次或运算时, 把先前的与运算的 lazy_tag 与上这个或运算的数即可

代码

后补

总结

多操作类型的题目, 应该想办法消除顺序的影响
当然之前连 线段树 2 都没做过, 没打出来可以理解

标签:lazy,需要,运算,处理,线段,tag,区间
From: https://www.cnblogs.com/YzaCsp/p/18460541

相关文章

  • 双指针维护可交换结合贡献区间价值的正攻法
    对于一类区间价值V(l,r)=a[l]opta[l+1]opt...opta[r]当我们维护双指针同时需要维护内部区间的价值时,如果操作可交换结合并且可消去(存在y,xopty=0),l右移时直接去掉a[l]的价值即可;如果不可消去但可重复贡献(xoptx=x),可以使用ST表计算区间贡献;如果只满足结合律,我......
  • 区间dp板子
    比较简单的dp,但是建模可能会比较困难。以P1775石子合并(弱化版)为例(https://www.luogu.com.cn/problem/P1775)思路:要求1-n的石子合并的代价,可以看成小的区间问题,化为1-k+k-n的两个区间。然后就有递推式子:dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+w[j]-w[i-1]。编......
  • ABC292G Count Strictly Increasing Sequences [区间DP]
    Description你有\(n\)个数,每个数长度为\(m\)。不过这\(n\)个数中,可能有某些位不确定,需要你在每个?位置上\(0\)到\(9\)之间填一个数。设你填出来的序列是\(\{S_i\}\)。请你求出,在所有可能的填数方案中,有多少种满足\(S_1<S_2<\dots<S_n\)?对\(998244353\)取......
  • 区间DP问题归纳总结
    常见问题:常用技巧:将环形区间转变为线形区间,从而解决环形区间的问题区间dp记录方案数区间dp和高精度的结合(将高精度模板结合到dp中去)代码的实现方式有两种:迭代式:自底向上递推计算,适用于简单的dp过程,一般来说,状态用了几维,就需要写几层for循环,当dp维度较高时显然不适用......
  • 合并、删除区间算法C++代码
    #include<algorithm>#include<iostream>#include<vector>usingnamespacestd;classSolution{public:constintCOMBINE_INT=0;//1表示整数点区间,比如[1:3]和[4:5]会合并为[1:5],0则仅会合并[1:3]和[3:4]这类的区间。vector<pair<int,int>>......
  • 【前缀和+开区间二分】codeforces 1187 B. Letters Shop
    题意第一行,输入一个正整数\(n(1\leqn\leq2*10^5)\),代表字符串\(s\)的长度。第二行,输入一个字符串\(s\)。第三行,输入一个正整数\(m(1\leqm\leq5*10^4)\),代表接下来要输入的询问次数,对于每次询问:输入一个字符串\(t(1\leq|t|\leq2*10^5)\),并保证\(\sum_{i=1}^m......
  • P4690 镜中的昆虫 (动态区间颜色数) 题解
    Statement区间涂颜色区间颜色数Solution\(O(\text{polysqrt})\)略。\(O(\text{polylog})\)颜色段均摊有两层含义:随机数据下:任意时刻的颜色段个数期望\(O(\logn)\)非随机数据下:每次推平时访问的颜色段个数均摊\(O(n)\)首先维护每个点\(i\)的\(pre_i\),一次询......
  • 代码随想录算法训练营 | 56. 合并区间,738.单调递增的数字
    56.合并区间题目链接:56.合并区间文档讲解︰代码随想录(programmercarl.com)视频讲解︰合并区间日期:2024-10-06想法:重叠区间类似问题Java代码如下:classSolution{publicint[][]merge(int[][]intervals){List<int[]>res=newArrayList<>();Arra......
  • 代码随想录算法训练营 | 452. 用最少数量的箭引爆气球,435. 无重叠区间,763.划分字母区
    452.用最少数量的箭引爆气球题目链接:452.用最少数量的箭引爆气球文档讲解︰代码随想录(programmercarl.com)视频讲解︰452.用最少数量的箭引爆气球日期:2024-10-05想法:对气球起点排序,没有重叠的箭头+1,有重叠得话将右边置为最小的右边。Java代码如下:classSolution{publ......
  • 数轴上定长区间与给定区间同时相交的最大数量
    模型在[1,n]中给定k个长度不等区间[l,r],求[1,n]中长度为d的区间与给定区间同时相交的最大数量代码intsolve(intn,intd,intk,std::vector<PII>&a){std::sort(a.begin(),a.end());std::priority_queue<int,std::vector<int>,std::greater<int>>f;......