P13274 [NOI2025] 三目运算符
提供一个不同的线段树实现。
根据题目我们知道，\(s_i\) 变换后的值仅与 \(s_{i-2},s_{i-1},s_i\) 有关。考虑这三个数的 \(2^3\) 种取值，我们发现只有 101 和 110 会使 \(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;
}