2021牛客多校7 - xay loves monotonicity(线段树区间合并)

题目链接：点击查看

题目大意：给出一个长度为 $n$ 的数字序列 $a$ 和 $01$ 序列 $b$，需要执行 $m$ 次操作，每次操作分为如下三种类型：

1 x y：修改 $a[x]=y$

2 l r：区间 $[l,r]$ 内的 $b$ 置反

3 l r：输出区间 $[l,r]$ 的贡献

最后说一下区间 $[l,r]$ 的贡献为，首先找到区间 $[l,r]$ 内的 “最长不下降子序列”，设其为 $\{p_1,p_2,...,p_k\}$，需要满足：

$p_1=l$

$a_{p_1}\le a_{p_2}\le a_{p_3}...$

对于任意 $j\in (p_i,p_{i+1})$，满足 $a_j<a_i$

然后将数组 $b$ 中相应的 $01$ 序列取出，即 $\{b_{p_1},b_{p_2},b_{p_3},...,b_{p_k}\}$

贡献就是 $\sum _{i=1}^k[b_i\ne b_{i-1}]$

题目分析：弱化版：HDU - 6406

其实这个题在思路上和弱化版没有区别，只是加了些许条件，只需要对 $cal$ 函数进行一下魔改就可以了

先回顾一下简单版本，如果只需要求解 “最长不下降子序列” 的个数，那么定义 $cal(k,mx)$ 为前一项为 $mx$ ，线段树的节点 $k$ 所提供的贡献。如何求解？线段树维护一下区间的最大值，分成两种情况讨论：

左子树的 $mmax$ 小于 $mx$：那么左子树没有贡献，只需要递归右子树返回 $cal(k<<1|1,mx)$ 即可

左子树的 $mmax$ 大于等于 $mx$：左右子树都有可能有贡献，答案为 $cal(k<<1,mx)+cal(k<<1|1,mx)$

这里为了方便追踪 $mx$ 的状态，我们将其作为引用或者全局变量进行传值，因为在线段树中检索的顺序是先左后右，宏观来看就是从左向右扫描序列的过程，所以实时更新 $mx$ 也就模拟了题目中的不断寻找 “最长不下降子序列” 的过程了。

然后就是我们发现上面的第二种情况的复杂度有点不乐观，但是我们不难看出，在递归完左子树后，右子树的答案就完全受左子树所影响了，而对于子树 $k$ 来说，我们早就通过 $pushup$ 维护好答案了，所以可以 $O(1)$ 计算右子树的贡献为 $cnt[k]-cnt[lc[k]]$

所以就简单描述出了弱化版本的 $O(nlo{g}^{2}n)$ 的做法

回到本题我们该如何维护该序列映射到数组 $b$ 上的贡献呢，其实只需要在 $cal$ 函数中额外维护一个参数就可以了：$cal(k,mx,pre)$ 代表的是，前一项为 $mx$，$mx$ 所代表的位置的 $b$ 的状态为 $pre$，子树 $k$ 所提供的贡献。在 $cal$ 递归到叶子节点时直接计算答案就好了

需要注意的是，在上述两种情况中的第二种情况，虽然优化了访问右子树的过程，但是返回的时候别忘了更新 $mx$ 和 $pre$ 为右子树结束时的状态（因为要从左到右扫描原序列）

剩下的两种操作无非就是单点修改和区间修改，中规中矩的线段树操作就不多说了

计算答案时的初始值根据题意设置成 $a[l]$ 和 $b[l]$ 就可以了

代码：

// Problem: xay loves monotonicity // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/11258/B // Memory Limit: 524288 MB // Time Limit: 4000 ms // // Powered by CP Editor (https://cpeditor.org)// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<list> #include<unordered_map> #define lowbit(x) (x&-x) using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=1e6+100; struct Node {int l,r;int mmax,flag,lazy,cnt; }tree[N<<2]; int a[N],b[N]; void pushdown(int k) {if(tree[k].lazy) {tree[k].lazy=0;tree[k<<1].flag^=1,tree[k<<1|1].flag^=1;tree[k<<1].lazy^=1,tree[k<<1|1].lazy^=1;} } int cal(int k,int &mx,int &pre) {//在子树k中以mx为起点的贡献,pre为mx位置的b的值if(tree[k].mmax<mx) return 0;if(tree[k].l==tree[k].r) {if(mx<=tree[k].mmax) {int ans=tree[k].flag!=pre;mx=tree[k].mmax,pre=tree[k].flag;return ans;} else return 0;}pushdown(k);if(mx>tree[k<<1].mmax) return cal(k<<1|1,mx,pre);else {int ans=cal(k<<1,mx,pre)+tree[k].cnt-tree[k<<1].cnt;mx=tree[k].mmax,pre=tree[k].flag;return ans;} } void pushup(int k) {if(tree[k<<1].mmax>tree[k<<1|1].mmax) {tree[k].mmax=tree[k<<1].mmax,tree[k].flag=tree[k<<1].flag;} else {tree[k].mmax=tree[k<<1|1].mmax,tree[k].flag=tree[k<<1|1].flag;}int mx=tree[k<<1].mmax,pre=tree[k<<1].flag;tree[k].cnt=tree[k<<1].cnt+cal(k<<1|1,mx,pre); } void build(int k,int l,int r) {tree[k]={l,r,0,0,0,0};if(l==r) {tree[k].mmax=a[l],tree[k].flag=b[l];return;}int mid=(l+r)>>1;build(k<<1,l,mid),build(k<<1|1,mid+1,r);pushup(k); } void update_a(int k,int pos,int val) {if(tree[k].l==tree[k].r) {tree[k].mmax=val;return;}pushdown(k);int mid=(tree[k].l+tree[k].r)>>1;if(pos<=mid) update_a(k<<1,pos,val);else update_a(k<<1|1,pos,val);pushup(k); } void update_b(int k,int l,int r) {if(tree[k].l>r||tree[k].r<l) return;if(tree[k].l>=l&&tree[k].r<=r) {tree[k].flag^=1,tree[k].lazy^=1;return;}pushdown(k);update_b(k<<1,l,r),update_b(k<<1|1,l,r);pushup(k); } int query_ans(int k,int l,int r,int &mx,int &pre) {if(tree[k].l>r||tree[k].r<l) return 0;if(tree[k].l>=l&&tree[k].r<=r) {if(mx<=tree[k].mmax) return cal(k,mx,pre);else return 0;}pushdown(k);return query_ans(k<<1,l,r,mx,pre)+query_ans(k<<1|1,l,r,mx,pre); } int query_a(int k,int pos) {if(tree[k].l==tree[k].r) return tree[k].mmax;pushdown(k);int mid=(tree[k].l+tree[k].r)>>1;if(pos<=mid) return query_a(k<<1,pos);else return query_a(k<<1|1,pos); } int query_b(int k,int pos) {if(tree[k].l==tree[k].r) return tree[k].flag;pushdown(k);int mid=(tree[k].l+tree[k].r)>>1;if(pos<=mid) return query_b(k<<1,pos);else return query_b(k<<1|1,pos); } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n,m;read(n);for(int i=1;i<=n;i++) read(a[i]);for(int i=1;i<=n;i++) read(b[i]);build(1,1,n);read(m);while(m--) {int op,x,y;read(op),read(x),read(y);if(op==1) update_a(1,x,y);else if(op==2) update_b(1,x,y);else if(op==3) {int mx=query_a(1,x),pre=query_b(1,x);cout<<query_ans(1,x,y,mx,pre)<<endl;}}return 0; }

总结

以上是生活随笔为你收集整理的2021牛客多校7 - xay loves monotonicity(线段树区间合并)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。