CF803G Periodic RMQ Problem（题解）

· · 题解

P.S.

高质量好题！！！！！！

这题我写了三种不同的方法，第一种写挂了，第二种也写挂了（（（
于是这篇题解会介绍三种不同的方法，有两种可能是假的。。。
通过这题让我明白了一个血的教训：能用简单的做法，不管常数有多大，就用。
AC 代码 99808KB（50 行，WA 的代码 148736 KB （100 行

Description.

给你一个序列，需要支持区间覆盖，查询区间最小值。
但是这个序列很长，是 10^9 级别的，但是它有不超过 10^5 的循环节。
读入方式是读入循环节长度和循环节数量。

Solution1.

思路很暴力，类似分块一样。
对于所有区间维护一个动态开点线段树，再对所有循环节维护另一颗线段树。
然后每次查询、修改直接对边块暴力修改（指在那颗线段树上修改。
然后整块直接在循环节线段树上维护区间最小值以及这个循环节应该打的标记
然后时间复杂度是 O(n\log n+n\log k) 的，空间复杂度对每次询问只会增加 \log n 个节点，所以是 O(n+Q\log n) 的，结果笔者写挂了。
附写挂的代码。 

//愿你和你重要的人能够重逢！
#include<bits/stdc++.h>
using namespace std;
template<typename T>inline void read(T &x)
{
    x=0;char c=getchar(),f=0;
    for(;c<'0'||c>'9';c=getchar()) if(!(c^45)) f=1;
    for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
    f?x=-x,1:1;
}
const int INF=1e9+5;
int n,Q,k,a[1000005],rt[1000005],tt=0;
struct seg{int mn,lz,tg;}t[4000005];
struct segm{int mn,tg,ls,rs;}T[6000005];
inline void tallc(int x,int c) {if(c) t[x].mn=t[x].lz=t[x].tg=c;}
inline void tdown(int x) {tallc(x<<1,t[x].tg),tallc(x<<1|1,t[x].tg),t[x].tg=0;}
inline void tup(int x) {t[x].mn=min(t[x<<1].mn,t[x<<1|1].mn);}
inline void tbuild(int x,int l,int r,int c)
{
    if(l==r) return(void)(t[x].mn=c,t[x].lz=t[x].tg=0);else t[x].tg=0;
    tbuild(x<<1,l,(l+r)>>1,c),tbuild(x<<1|1,((l+r)>>1)+1,r,c),tup(x);
}
inline void tmotif(int x,int l,int r,int dl,int dr,int dc)
{
    if(dl>r||l>dr||dl>dr) return;else if(dl<=l&&r<=dr) return tallc(x,dc);else tdown(x);
    tmotif(x<<1,l,(l+r)>>1,dl,dr,dc),tmotif(x<<1|1,((l+r)>>1)+1,r,dl,dr,dc),tup(x);
}
inline int tquery(int x,int l,int r,int dl,int dr)
{
    if(dl>r||l>dr||dl>dr) return INF;else if(dl<=l&&r<=dr) return t[x].mn;else tdown(x);
    return min(tquery(x<<1,l,(l+r)>>1,dl,dr),tquery(x<<1|1,((l+r)>>1)+1,r,dl,dr));
}
inline int task(int x,int l,int r,int dw)
{
    if(l==r) return t[x].lz;else tdown(x);
    return dw<=((l+r)>>1)?task(x<<1,l,(l+r)>>1,dw):task(x<<1|1,((l+r)>>1)+1,r,dw);
}
inline void tqklz(int x,int l,int r,int dw,int dc)
{
    if(l==r) return(void)(t[x].lz=0,t[x].mn=dc);else tdown(x);
    if(dw<=((l+r)>>1)) tqklz(x<<1,l,(l+r)>>1,dw,dc),tup(x);
    else tqklz(x<<1|1,((l+r)>>1)+1,r,dw,dc),tup(x);
}
inline void Tallc(int &x,int c) {T[++tt]=T[x],x=tt;if(c) T[x].tg=c,T[x].mn=c;}
inline void Tdown(int x) {Tallc(T[x].ls,T[x].tg),Tallc(T[x].rs,T[x].tg),T[x].tg=0;}
inline void Tup(int x) {T[x].mn=min(T[T[x].ls].mn,T[T[x].rs].mn);}
inline void Tbuild(int &x,int l,int r)
{
    x=++tt;if(l==r) return(void)(T[x]=(segm){a[l],0,0,0});else T[x].tg=0;
    Tbuild(T[x].ls,l,(l+r)>>1),Tbuild(T[x].rs,((l+r)>>1)+1,r),Tup(x);
}
inline void Tmotif(int &x,int l,int r,int dl,int dr,int dc)
{
    if(l>dr||dl>r||!x) return;
    T[++tt]=T[x],x=tt;if(dl<=l&&r<=dr) return Tallc(x,dc);else Tdown(x);
    Tmotif(T[x].ls,l,(l+r)>>1,dl,dr,dc),Tmotif(T[x].rs,((l+r)>>1)+1,r,dl,dr,dc),Tup(x);
}
inline int Tquery(int x,int l,int r,int dl,int dr)
{
    if(!x||dl>r||l>dr) return INF;else if(dl<=l&&r<=dr) return T[x].mn;else Tdown(x);
    return min(Tquery(T[x].ls,l,(l+r)>>1,dl,dr),Tquery(T[x].rs,((l+r)>>1)+1,r,dl,dr));
}
inline void Push_Down(int w) {int val=task(1,1,n,w);if(val) Tmotif(rt[w],1,n,1,n,val),tqklz(1,1,n,w,val);}
inline void Chang(long long l,long long r,int c)
{
    int le=(l-1)/n+1,ri=(r-1)/n+1;Push_Down(le);if(le^ri) Push_Down(ri);
    if(le==ri) return Tmotif(rt[le],1,n,(l-1)%n+1,(r-1)%n+1,c),tqklz(1,1,n,le,T[rt[le]].mn);
    Tmotif(rt[le],1,n,(l-1)%n+1,n,c),tqklz(1,1,n,le,T[rt[le]].mn);
    Tmotif(rt[ri],1,n,1,(r-1)%n+1,c),tqklz(1,1,n,ri,T[rt[ri]].mn);
    tmotif(1,1,n,le+1,ri-1,c);
}
inline void P(int id) {for(int i=1;i<=n;i++) printf("%d%c",Tquery(rt[id],1,n,i,i),i==n?'\n':' ');}
inline int Query(long long l,long long r)
{
    int le=(l-1)/n+1,ri=(r-1)/n+1;Push_Down(le);if(le^ri) Push_Down(ri);
    int res=INF;if(le==ri) return Tquery(rt[le],1,n,(l-1)%n+1,(r-1)%n+1);
    res=min(res,Tquery(rt[le],1,n,(l-1)%n+1,n));
    res=min(res,Tquery(rt[ri],1,n,1,(r-1)%n+1));
    res=min(res,tquery(1,1,n,le+1,ri-1));return res;
}
inline void debug(int x,int l,int r)
{
    if(x) printf("%d : [ %d ~ %d ] : %d ( %d -> %d %d\n",x,l,r,T[x].mn,T[x].tg,T[x].ls,T[x].rs);
    if(l^r) Tdown(x),debug(T[x].ls,l,(l+r)>>1),debug(T[x].rs,((l+r)>>1)+1,r);
}
int main()
{
    read(n),read(k);for(int i=1;i<=n;i++) read(a[i]);
    Tbuild(rt[1],1,n),tbuild(1,1,n,T[rt[1]].mn);for(int i=2;i<=k;i++) rt[i]=rt[1];
    for(read(Q);Q--;)
    {
        //debug(rt[1],1,n),debug(rt[2],1,n);
        int fg,x;long long l,r;read(fg),read(l),read(r);
        if(fg^1) printf("%d\n",Query(l,r));else read(x),Chang(l,r,x);
    }
    return 0;
}

Solution 2.

直接离线，然后直接暴力。
把一段没有修改的区间直接压成一个点，用 st表 维护区间最值。
思路很简单，一交直接 WA on 7，代码就不放了。

Solution 3.

还是用 st表，但是不离散化，直接更加暴力地动态开点。
和上面 Solution2 的思路差不对，只不过不压点。
结果直接 A 了。。。小编也很惊讶但是事实就是这样子
具体实现看代码注释qwq

Coding.

//愿你和你重要的人能够重逢
#include<bits/stdc++.h>
using namespace std;
template<typename T>inline void read(T &x)
{
    x=0;char c=getchar(),f=0;
    for(;c<48||c>57;c=getchar()) if(!(c^45)) f=1;
    for(;c>=48&&c<=57;c=getchar()) x=(x<<1)+(x<<3)+(c^48);
    if(f) x=-x;
}
struct node{int vl,tg,ls,rs;}t[5000005];
int n,k,Q,a[300005],lg[200005],st[200005][25],tt=0,rt=0;
inline int qry(int l,int r) {int g=lg[r-l+1];return min(st[l][g],st[r-(1<<g)+1][g]);}
inline int rqry(int l,int r)
{//像分块一样，如果同一块，直接查
//如果相邻块就是后面一段和前面一段
//否则就肯定至少包括了一个整块，直接全局最小值
    int le=(l-1)/n+1,ri=(r-1)/n+1,L=(l-1)%n+1,R=(r-1)%n+1;if(le==ri) return qry(L,R);
    if(le+1==ri) return min(qry(L,n),qry(1,R));else return qry(1,n);
}
//↓动态开点线段树的动态开点函数↓
inline void New(int &x,int l,int r) {if(!x) t[x=++tt]=(node){rqry(l,r),0,0,0};}
//↓线段树模板↓
inline void allc(int x,int c) {if(c) t[x].vl=t[x].tg=c;}
inline void down(int x,int l,int r) {New(t[x].ls,l,(l+r)>>1),New(t[x].rs,((l+r)>>1)+1,r),allc(t[x].ls,t[x].tg),allc(t[x].rs,t[x].tg),t[x].tg=0;}
inline void motif(int &x,int l,int r,int dl,int dr,int dc)
{
    New(x,l,r);if(l>dr||dl>r) return;else if(dl<=l&&r<=dr) return allc(x,dc);else down(x,l,r);
    motif(t[x].ls,l,(l+r)>>1,dl,dr,dc),motif(t[x].rs,((l+r)>>1)+1,r,dl,dr,dc),t[x].vl=min(t[t[x].ls].vl,t[t[x].rs].vl);
}
inline int query(int &x,int l,int r,int dl,int dr)
{
    New(x,l,r);if(l>dr||dl>r) return 1e9;else if(dl<=l&&r<=dr) return t[x].vl;else down(x,l,r);
    return min(query(t[x].ls,l,(l+r)>>1,dl,dr),query(t[x].rs,((l+r)>>1)+1,r,dl,dr));
}
//debug函数，不删了
inline void debug(int x,int l,int r)
{
    if(x) printf("%d : [ %d , %d ] & %d\n",x,l,r,t[x].vl);
    if(l^r) down(x,l,r),debug(t[x].ls,l,(l+r)>>1),debug(t[x].rs,((l+r)>>1)+1,r);
}
int main()
{
    lg[0]=-1,read(n),read(k);
    for(int i=1;i<=n;i++) lg[i]=lg[i>>1]+1;
    for(int i=1;i<=n;i++) read(st[i][0]);
    for(int i=1;i<=20;i++) for(int j=1;j+(1<<(i-1))<=n;j++) st[j][i]=min(st[j][i-1],st[j+(1<<(i-1))][i-1]);
//  printf("%d , %d , %d , %d , %d , %d\n",rqry(1,1),rqry(1,2),rqry(1,3),rqry(2,2),rqry(2,3),rqry(3,3));
    read(Q),New(rt,1,n*k);for(int fg,l,r,c;Q--;)
    {
        read(fg),read(l),read(r);//debug(rt,1,n);
        if(fg&1) read(c),motif(rt,1,n*k,l,r,c);else printf("%d\n",query(rt,1,n*k,l,r));
    }
    return 0;
}