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

P13274 [NOI2025] 三目运算符

P13274 [NOI2025] 三目运算符

提供一个不同的线段树实现。


根据题目我们知道,\(s_i\) 变换后的值仅与 \(s_{i-2},s_{i-1},s_i\) 有关。考虑这三个数的 \(2^3\) 种取值,我们发现只有 101110 会使 \(s_i\) 发生变化。

进一步分析:

  • 101 会使 \(s_i\) 变成 \(0\),这一段不会再变化。

  • 110

    • 1100 会变成 1110
    • 1101 会变成 1110

    换句话说,110 相当于把当前的 \(0\) 向后推了一位。

    这样一路推到最后,如果记 110 的起始位置为 \(p\),则操作次数就是 \(n-p-1\)

综上我们可以得到答案:\(\max([\text{存在 }\texttt{101}],n-p_{\min}-1)\)


我们可以用线段树来动态维护。

我们可以将相邻的三个数压成一个 \([0,7]\) 的整数,扔到大小为 \(n-2\) 的线段树里。

这样我们仅需维护:

  • 是否存在一个位置存有 101
  • 是否存在一个位置存有 010
  • 存有 110 的最小位置。
  • 存有 001 的最小位置。

查询直接查根节点就行了。

修改操作,我们可以转化为区间异或 7,但是因为我们只在叶子节点维护值,所以没必要这样做。直接将需要修改的区间的第 \(1,2\) 条交换,第 \(3,4\) 条交换即可。

需要注意的是,对于 \(l-2,l-1,r-1,r\),它们管辖的区间的修改操作不是完整的。不能参与区修,需要单独点修处理一下。

另外注意特殊处理 \(l=r\) 的情况。

时间复杂度 \(O(T(n+q\log n))\)

码量相比其他题解的做法小了不少。但是受限于能力,还是实现得不怎么好看。权且提供这样一个思路~

点击查看代码
#include<bits/stdc++.h>
#define lc (x<<1)
#define rc (x<<1|1)
using namespace std;
typedef long long ll;
const int N=4e5+5;
int c,t,n,q;ll ans;
string s;
struct SEG{int c[N<<2],p[2][N<<2];bitset<N<<2> tg,a[2];inline int calc(){return max(int(a[0][1]!=0),n-p[0][1]-1);}inline void init(int x,int c,int l){a[0][x]=(c==5),a[1][x]=(c==2);p[0][x]=(c==6?l:1e9),p[1][x]=(c==1?l:1e9);}inline void upd(int x){a[0][x]=a[0][lc]|a[0][rc],a[1][x]=a[1][lc]|a[1][rc];p[0][x]=min(p[0][lc],p[0][rc]),p[1][x]=min(p[1][lc],p[1][rc]);}inline void pushdown(int x){if(tg[x]) tg[x]=0,mktg(lc),mktg(rc);}inline void mktg(int x){tg[x]=tg[x]^1,a[0][0]=a[0][x],a[0][x]=a[1][x],a[1][x]=a[0][0],swap(p[0][x],p[1][x]);}inline void build(int x,int l,int r){tg[x]=0;if(l==r){init(x,c[x]=((s[l-1]&1)<<2)|((s[l]&1)<<1)|(s[l+1]&1),l);return;}int mid=(l+r)>>1;build(lc,l,mid),build(rc,mid+1,r),upd(x);}inline void chp(int x,int p,int v,int l,int r){if(l==r){c[x]^=v;if(tg[x]) tg[x]=0,init(x,c[x]^=7,l);else init(x,c[x],l);return;}int mid=(l+r)>>1;pushdown(x);if(p<=mid) chp(lc,p,v,l,mid);else chp(rc,p,v,mid+1,r);upd(x);}inline void chr(int x,int a,int b,int l,int r){if(a<=l&&r<=b) return mktg(x),void();int mid=(l+r)>>1;pushdown(x);if(a<=mid) chr(lc,a,b,l,mid);if(b>mid) chr(rc,a,b,mid+1,r);upd(x);}
}seg;
inline void chp(int x,int v){if(x>0&&x<n-1) seg.chp(1,x,v,1,n-2);}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>c>>t;while(t--){cin>>n>>q>>s;seg.build(1,1,n-2);ans=seg.calc();for(int i=1,l,r;i<=q;i++){cin>>l>>r;if(l==r) chp(l,4),chp(l-1,2),chp(l-2,1);else{if((l+1)^r) seg.chr(1,l,r-2,1,n-2);chp(r,4),chp(r-1,6),chp(l-1,3),chp(l-2,1);}ans^=1ll*(i+1)*seg.calc();}cout<<ans<<"\n";}return 0;
}
http://www.hskmm.com/?act=detail&tid=28210

相关文章:

  • Microsoft Office不小心卸载或重装系统后,如何重新安装 ... - sherlock
  • HTTPS 抓包乱码怎么办?原因剖析、排查步骤与实战工具对策(HTTPS 抓包乱码、gzipbrotli、TLS 解密、iOS 抓包) - 实践
  • 使用JaCoCo进行代码覆盖率分析
  • 计算机视觉专家入选德国国家科学院
  • 2025 年工程管理软件/软件系统/软件App/软件平台/工程管理软件和验房系统公司/企业推荐榜:数字化转型下的实用选型指南
  • 【Java学习】【Java基础】--第1篇:入门Java和对面向对象的理解
  • solutions
  • 技术面:Spring (事务传播机制、事务失效的原因、BeanFactory和FactoryBean的关系)
  • 安装与配置MySQL 8 on Ubuntu,包括权限授予、数据库备份及远程连接
  • 04-最简单的字符设备驱动
  • 完整教程:手机可视化方案(针对浓度识别)
  • AI元人文系列文章:决策范式与无为而治
  • SAP导入证书
  • Kubernetes存储卷:保障有状态应用的数据持久化
  • MySQL的查询操作语法要点
  • 华为链路聚合配置
  • 手机adb 调试自己
  • 离线安装 mysql
  • what is a good parent
  • 2025 年公共/商场/学校/地铁/电影院/会所/机场/卫生间隔断厂家选购指南:优质厂商推荐与实用选择策略
  • 为什么不该用 Double 表示金额及解决方案
  • Windows开发环境安装备忘录
  • Vue.use(Vuex)
  • [Gym-100343E]Convex Permutominoes 题解
  • MyBatis 中的动态 SQL 的相关使用方法(Javaee/MyBatis) - 教程
  • 网络优化问题
  • Java环境安装备忘录
  • 深入解析:【Spring MVC终极指南】一文掌握请求处理与响应!从Servlet原生方式到SpringMVC高效优雅写法
  • foobar2000 v2.25.2 汉化版
  • 比特币地址投毒攻击深度剖析