zkw 递推 线段树二分

· · 算法·理论

Problem

给定序列 a_1,\dots,a_n，共 m 次操作，每次操作给出 x,y,l,r，将 a_x 修改为 y。

问修改前后，有几个区间 [l',r'] 满足 l\le l'\le r'\le r，且 a_{l'},\dots,a_{r'} 的最大值发生了变化。

询问的更改操作是持久化的。

对于所有的数据，满足 1\le n,m\le10^6,1\le a_i,y\le10^9,1\le l\le x\le r\le n。

做法

找到最大的满足条件的区间 [L,R]，
可以发现该区间的所有包含位置 x 的子区间都满足条件，
所以答案就是 (x-L+1)(R-x+1)，
线段树二分即可做到 O(m\log n)。

在网上我没找到 zkw 线段树二分，所以自己按照树状数组的思想自己推了下式子：

#include<bits/stdc++.h>
int a[1000005<<2],N,n,m;
int&mx(int&x,int v){return (v>x?x=v:x);}
void C(int x,int k){a[x+=N]=k;while(x>>=1)mx(a[x]=a[x<<1],a[x<<1|1]);}
int B(int x,int v,bool f){
    x=N+x;while(a[x]<v){x+=f,x/=(x&-x),x-=!f;if(x==f)return N*f;}
    while(x<=N)x=x<<1|f^(a[x<<1|!f]>=v);return x-N;
}int main(){
    std::ios::sync_with_stdio(0);std::cin.tie(0),std::cout.tie(0);
    std::cin>>n>>m;N=1<<(std::__lg(n)+1);
    for(int i=N+1;i<=N+n;++i)std::cin>>a[i];
    for(int i=N-1;i>=1;--i)mx(a[i]=a[i<<1],a[i<<1|1]);
    while(m--){
        int x,y,l,r,v;std::cin>>x>>y>>l>>r;
        if(a[N+x]==y){std::cout<<"0\n";continue;}
        mx(v=y,a[N+x]),C(x,y);
        mx(l,B(x-1,v,0)+1),r=std::min(r,B(x+1,v,1)-1);
        std::cout<<int64_t(x-l+1)*(r-x+1)<<"\n";
    }return 0;
}

时间（同一个输入输出）：