P4891 序列 - 题解

· · 题解

@chen_qian 先写了这一种做法，这篇题解权当是一个对他的题解的补充。

其实主要是感觉他写的太长了

考虑每一种操作对所有数组造成的影响。

出现了区间 cover，单点修改，线段树没得跑了。

由于线段树上维护的都是 C 数组，所以下面的 A 就代指 题面中的 C 数组了。

接下来来看答案的维护。

我们发现，每一次如果要用 naive 的方式正确维护所有区间，那么必然需要递归到叶子来暴力修改。而这是我们所不能接受的。

之前有一些题，也是需要暴力递归到叶子，我们的优化方式是什么？

参考操作本身的性质，通过一定的剪枝，使得区间可以被合并处理，达到降低复杂度的目的。

那就来看看这个题什么时候区间能够合并处理吧。（对于区间 cover 操作）

考虑这样做的时间复杂度的级别。

如果我们将 A_i < B_i 的个数看做总势能的话，每一次递归到叶子的操作都会使得总势能 -1。

而唯一能够增加势能的方式就是对于 B 的 单点修改。每一次最多使得总势能 +1。

由于总势能在 O(n+q) 级别，所以递归到叶子的操作最多执行这么多次。

其余的操作都可以看做是递归到叶子路上的长度为 1 的小分支，无足轻重。

所以这么做的总时间复杂度就被证明了是 O(n\log^2 n)的（认为 n,q 等价）。

关于实现：（这才是万恶之源）

其实根本不用像 @chen_qian 的题解那样维护这么多东西 /lh

对于每个节点，维护 Amx,Amn,Bmx,Bmn,tag,tagty,ans 即可。

注释：

#include <cstdio>
#include <cstring>
const int maxn = 1e5+5,mod = 1e9+7;
inline int min(int a,int b) {return a<b?a:b;}
inline int max(int a,int b) {return a>b?a:b;}
inline int ksm(int a,int x) {
    int base=a,ans=1;
    while(x) {
        if(x&1)ans = 1ll*ans*base%mod;
        base = 1ll*base*base%mod;
        x >>= 1;
    }
    return ans;
}
int n,m,tmp,a[maxn],b[maxn],amn[maxn<<2],amx[maxn<<2],bmn[maxn<<2],bmx[maxn<<2],ans[maxn<<2],tag[maxn<<2],ty[maxn<<2];
void pushup(int k) {
    ans[k] = 1ll*ans[k<<1]*ans[k<<1|1]%mod;
    amx[k] = max(amx[k<<1],amx[k<<1|1]),bmx[k] = max(bmx[k<<1],bmx[k<<1|1]);
    amn[k] = min(amn[k<<1],amn[k<<1|1]),bmn[k] = min(bmn[k<<1],bmn[k<<1|1]);
}
void build(int k,int l,int r) {
    if(l == r)return amn[k]=amx[k]=a[l],bmx[k]=bmn[k]=b[l],ans[k]=min(a[l],b[l]),void();
    int mid = l+r>>1;
    build(k<<1,l,mid),build(k<<1|1,mid+1,r),pushup(k);
}
void gtag(int k,int l,int r,int v,int typ) {
    tag[k] = v,ty[k] = typ,amn[k] = amx[k] = v;
    if(typ&1)ans[k] = ksm(v,r-l+1);
}
void pushdown(int k,int l,int r,int mid) {if(~tag[k])gtag(k<<1,l,mid,tag[k],ty[k]),gtag(k<<1|1,mid+1,r,tag[k],ty[k]),tag[k] = -1,ty[k] = 0;}
int getpos(int k,int l,int r,int v) {
    if(amx[k]<=v)return n+1;
    if(l==r)return l;
    int mid = l+r>>1;
    pushdown(k,l,r,mid);
    if((tmp=getpos(k<<1,l,mid,v)) != n+1)return tmp;
    return getpos(k<<1|1,mid+1,r,v);
}
void cover(int k,int l,int r,int x,int y,int v) {
    if(l>y||r<x)return ;
    if(l>=x&&r<=y) {
        if(amn[k] >= bmx[k])return gtag(k,l,r,v,2);
        if(max(amx[k],v) <= bmn[k])return gtag(k,l,r,v,1);
        if(l == r)return amn[k]=amx[k]=v,ans[k]=bmn[k],void();
    }
    int mid = l+r>>1;
    pushdown(k,l,r,mid);
    cover(k<<1,l,mid,x,y,v),cover(k<<1|1,mid+1,r,x,y,v),pushup(k);
}
void update(int k,int l,int r,int p,int v) {
    if(l == r)return bmn[k] = bmx[k] = v,ans[k] = min(amn[k],bmn[k]),void();
    int mid = l+r>>1;
    pushdown(k,l,r,mid);
    p<=mid?update(k<<1,l,mid,p,v):update(k<<1|1,mid+1,r,p,v);
    pushup(k);
}
int main() {
    memset(tag,-1,sizeof(tag));
    scanf("%d %d",&n,&m);
    for(int i=1; i<=n; ++i)scanf("%d",&a[i]),a[i] = max(a[i],a[i-1]);
    for(int i=1; i<=n; ++i)scanf("%d",&b[i]);
    build(1,1,n);
    while(m--) {
        int ty,x,y;
        scanf("%d %d %d",&ty,&x,&y);
        if(ty == 0) {
            int pos = getpos(1,1,n,y);
            if(x<=pos-1)cover(1,1,n,x,pos-1,y);
        }
        if(ty == 1)update(1,1,n,x,y);
        printf("%d\n",ans[1]);
    }
    return 0;
}

upd: 修复了部分笔误以及代码缩进问题。