题解 CF803G 【Periodic RMQ Problem】

Update On 2020.04.16：修正了 LaTeX 和部分语句问题

前言

前置知识：线段树及其动态开点，ST 表

思路

空间复杂度的优化

区间赋值？区间最小值？立刻想到了朴素线段树。但是 a 的长度可能达到 10^9，显然不可行。

这个时候就要使用线段树动态开点了。顾名思义，就是要用当前节点的信息时再建立这个节点。

至于线段树数组要开多大？我算过，但是算挂了。为了保证正确，建议在空间限制允许的范围内尽可能地开大（例如 2\times10^7）。

时间复杂度的优化

空间复杂度满足了，再来考虑时间复杂度。如果直接用 O(nk\times \log_2(nk)) 的复杂度建一棵线段树，那么直接 TLE。

考虑不建树，而使用 ST 表对付查询。如果当前区间已经被覆盖，则返回覆盖的值。否则有 3 种情况（注：l,r 下标从 0 开始，不同于一般 ST 表）：

1. 区间的左端点 l 与区间的右端点 r 之差 ≥n，即 r-l+1≥n，这个时候 [l,r] 包含了一个完整的b 序列，所以 [l,r] 中的数一定只包含 b 中的数，这种情况使用 ST 表查询 b 中 [0,n-1] 的最小值即可。

这个时候时间复杂度已经降低到O(q\times \log_2(nk))，可以通过本题。

代码

这里给出博主的代码。希望能对您有所帮助。

# include <bits/stdc++.h>
# define rr register
const int N=100010,MAXN=20000010;
struct Node{
    int l,r,add,Min;
}tree[MAXN];
int ST[N][30];
int n,k,q;
int root,id;//root是根节点编号 id是给线段树节点标号用的
inline int read(void){//快读
    int res,f=1;
    char c;
    while((c=getchar())<'0'||c>'9')
        if(c=='-')f=-1;
    res=c-48;
    while((c=getchar())>='0'&&c<='9')
        res=res*10+c-48;
    return res*f;       
}
inline int RMQ_ask(int l,int r){//小区间ST表查询
    int len=log2(r-l+1);
    return std::min(ST[l][len],ST[r-(1<<len)+1][len]);
}
inline int Ask(int l,int r){//大区间ST表查询
    if(r-l+1>=n){
        return RMQ_ask(0,n-1);
    }
    if(l/n==r/n){
        return RMQ_ask(l%n,r%n);
    }
    return std::min(RMQ_ask(l%n,n-1),RMQ_ask(0,r%n));
}
inline bool make(int &x,int l,int r){//开点
    if(x)
        return false;
    x=++id;
    tree[x].Min=Ask(l,r);//每一个新节点都是没有标记的（除非父节点会传下来） 于是初始值都是[l,r]的最小值
    return true;
}
inline void Add(int k,int v){//区间赋值操作
    tree[k].add=tree[k].Min=v;
    return;
}
inline void pushdown(int k,int l,int r){//标记下传操作
    int mid=(l+r)>>1;
    make(tree[k].l,l,mid);
    make(tree[k].r,mid+1,r);
    if(!tree[k].add)
        return;
    tree[tree[k].l].add=tree[tree[k].l].Min=tree[tree[k].r].add=tree[tree[k].r].Min=tree[k].add;
    tree[k].add=0;
    return; 
}
void change(int &k,int l,int r,int L,int R,int v){
    make(k,l,r);//进来一次make一次 防止出奇怪的bug
    if(L<=l&&r<=R){
        Add(k,v);
        return;
    }
    pushdown(k,l,r);
    int mid=(l+r)>>1;
    if(L<=mid)
        change(tree[k].l,l,mid,L,R,v);
    if(mid<R)
        change(tree[k].r,mid+1,r,L,R,v);
    tree[k].Min=std::min(tree[tree[k].l].Min,tree[tree[k].r].Min);
    return;     
}
int ask(int &k,int l,int r,int L,int R){//询问 和普通线段树差不多
    make(k,l,r);
    if(L<=l&&r<=R){
        return tree[k].Min;
    }
    pushdown(k,l,r);
    int res=1e9,mid=(l+r)>>1;
    if(L<=mid)
        res=std::min(res,ask(tree[k].l,l,mid,L,R));
    if(mid<R)
        res=std::min(res,ask(tree[k].r,mid+1,r,L,R));
    return res; 
}
int main(void){
    n=read(),k=read();
    for(rr int i=0;i<n;++i)//从零开始的数组下标
        ST[i][0]=read();
    for(rr int j=1;(1<<j)<=n;++j)
        for(rr int i=0;i+(1<<j)-1<n;++i){
            ST[i][j]=std::min(ST[i][j-1],ST[i+(1<<(j-1))][j-1]);
        }
    q=read();
    make(root,0,n*k-1);//提前建好root节点
    int sign,l,r,x;
    while(q--){
        sign=read(),l=read(),r=read();
        if(sign==1){//修改
            x=read();
            change(root,0,n*k-1,l-1,r-1,x);
        }
        else printf("%d\n",ask(root,0,n*k-1,l-1,r-1));//查询
    }
    return 0;
}