CF803G Periodic RMQ Problem

(Updated: )
oi
,

Description

题目链接：CF803G

一个序列 ${a_i}$ 由 $k$ 个长度为 $n$ 的序列 ${b_i}$ 拼接而成，支持 $q$ 个操作：

  1. 1 l r x，区间赋值
  2. 2 l r求区间最小值

$1\leq n\leq 10^5,1\leq k \leq 10^4,1\leq q \leq 10^5,1\leq b_i\leq 10^9$

Solution

乍一看就是线段树模板题，然后看一眼数据范围，序列 ${a_i}$ 的长度可以高达 $10^9$，所以不能直接开线段树。

考虑这个序列的特殊性质：由 $k$ 个长度为 $n$ 的序列 ${b_i}$ 拼接而成。

也就是说其实我们可以把所有操作映射到 ${b_i}$ 上做。

然后把所有操作离线下来，离散化，拆成每个点以及两个点间的区间，先用 RMQ 预处理出离散化后每个点的初值，然后再套个线段树动态维护一下最小值即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
using namespace std;
namespace Debug{
    Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
    Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
    Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
    #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
    Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;}
    Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
    Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
    Tp I void writeln(Cn Ty& x){write(x),pc('\n');}
}using namespace FastIO;
Cn int N=1e5+10;
int n,k,b[N],q,o[N<<1],cnt,tot,w[N<<2],id[N<<2];
struct Que{int op,l,r,x;}c[N];
class RMQ{
    private:
        int F[N][20],lg[N];
    public:
        I void B(){
            RI i,j;for(lg[0]=-1,i=1;i<=n;i++) F[i][0]=b[i],lg[i]=lg[i/2]+1;
            for(j=1;(1<<j)<=n;j++) for(i=1;i+(1<<j)-1<=n;i++) F[i][j]=min(F[i][j-1],F[i+(1<<j-1)][j-1]);
        }
        I int Q(CI l,CI r){return min(F[l][lg[r-l+1]],F[r-(1<<lg[r-l+1])+1][lg[r-l+1]]);}
}R;
class SegmentTree{
    private:
        struct node{int S,T;}T[N<<3];
        #define mid (l+r>>1)
        #define PT CI x=1,CI l=1,CI r=tot
        #define LT x<<1,l,mid
        #define RT x<<11,mid+1,r
        #define PU(x) (T[x].S=min(T[x<<1].S,T[x<<11].S))
        #define PD(x) (T[x].T&&(T[x<<1].T=T[x<<11].T=T[x<<1].S=T[x<<11].S=T[x].T,T[x].T=0))
    public:
        I void B(PT){
            if(l==r) return void(T[x].S=w[l]);
            B(LT),B(RT),PU(x);
        }
        I void U(CI L,CI R,CI v,PT){
            if(L<=l&&r<=R) return void(T[x].T=T[x].S=v);
            PD(x),L<=mid&&(U(L,R,v,LT),0),R>mid&&(U(L,R,v,RT),0),PU(x);
        }
        I int Q(CI L,CI R,PT){
            if(L<=l&&r<=R) return T[x].S;
            RI S=2e9;return PD(x),L<=mid&&(S=min(S,Q(L,R,LT))),R>mid&&(S=min(S,Q(L,R,RT))),S;
        }
}S;
int main(){
    RI i,l,r;for(read(n,k),i=1;i<=n;i++) read(b[i]);
    for(R.B(),read(q),i=1;i<=q;i++) read(c[i].op,c[i].l,c[i].r),c[i].op&1&&(read(c[i].x),0),o[++cnt]=c[i].l,o[++cnt]=c[i].r;
    #define idx(x) ((x)%n?(x)%n:n)
    sort(o+1,o+cnt+1),cnt=unique(o+1,o+cnt+1)-o-1;for(i=1;i<cnt;i++) if(w[++tot]=b[idx(o[i])],id[i]=tot,o[i+1]>o[i]+1){//离散化后分情况讨论
        if(o[i+1]-1-(o[i]+1)>=n) w[++tot]=R.Q(1,n);//如果长度超过 n ，其实就是整个 bi 的最小值
        else if((l=idx(o[i]+1))<=(r=idx(o[i+1]-1))) w[++tot]=R.Q(l,r);//如果在一段区间内
        else w[++tot]=min(R.Q(l,n),R.Q(1,r));//如果跨越了两个区间
    }w[++tot]=b[idx(o[cnt])],id[cnt]=tot;
    #define LW(x) (lower_bound(o+1,o+cnt+1,x)-o)
    for(S.B(),i=1;i<=q;i++) c[i].l=LW(c[i].l),c[i].r=LW(c[i].r),c[i].op&1?S.U(id[c[i].l],id[c[i].r],c[i].x):
    writeln(S.Q(id[c[i].l],id[c[i].r]));return 0;
}