CF803G

发表于 分类于
Periodic RMQ Problem

Periodic RMQ Problem

？？？

动态开点线段树即可。遇到没有被修改的块单独写一个函数在 $b$ 数组中查询即可。

然后就没了。

注意一下空间什么的，常数稍大，但是 CF 的数据卡不满，动态开点大概开个两倍就够了。

介于没有什么加减操作，无需担心溢出，使用 int 即可。

代码：

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include<iostream>
#include<cstdio>
#define ll int
using namespace std;

const ll N=1e5;

ll n,m,q,k,op,x,l,r,cnt;

ll b[N+5];

struct sgt{
  ll mi;
  #define mi(x) tree[x].mi
}tree[N*4+5];

struct dsgt{
  ll l,r,ls,rs,dat,laz;
  #define l(x) dtree[x].l
  #define r(x) dtree[x].r
  #define ls(x) dtree[x].ls
  #define rs(x) dtree[x].rs
  #define dat(x) dtree[x].dat
  #define laz(x) dtree[x].laz
}dtree[N*80+5];

inline void build(ll p,ll l,ll r) {
  if(l==r) {mi(p)=b[l];return;}
  ll mid=(l+r)>>1;
  build(p<<1,l,mid);build(p<<1|1,mid+1,r);
  mi(p)=min(mi(p<<1),mi(p<<1|1));
}

inline ll query(ll p,ll lp,ll rp,ll l,ll r) {
  if(lp>=l&&rp<=r) return mi(p);
  ll mid=(lp+rp)>>1;
  if(l>mid) return query(p<<1|1,mid+1,rp,l,r);
  if(r<=mid) return query(p<<1,lp,mid,l,r);
  return min(query(p<<1,lp,mid,l,r),query(p<<1|1,mid+1,rp,l,r));
}

inline ll queryb(ll l,ll r) {
  if(r-l+1>=n) return query(1,1,n,1,n);
  l=(l-1)%n+1;r=(r-1)%n+1;
  if(l<=r) return query(1,1,n,l,r);
  return min(query(1,1,n,1,r),query(1,1,n,l,n));
}

inline void pushdown(ll p) {
  ll mid=(l(p)+r(p))>>1;
  if(!ls(p)) {
    cnt++;ls(p)=cnt;l(cnt)=l(p);r(cnt)=mid;dat(cnt)=queryb(l(cnt),r(cnt));
  }
  if(!rs(p)) {
    cnt++;rs(p)=cnt;l(cnt)=mid+1;r(cnt)=r(p);dat(cnt)=queryb(l(cnt),r(cnt));
  }
  if(laz(p)) {
    dat(ls(p))=laz(p);laz(ls(p))=laz(p);
    dat(rs(p))=laz(p);laz(rs(p))=laz(p);
    laz(p)=0;
  }
}

inline void modify(ll p,ll l,ll r,ll k) {
  if(l(p)>=l&&r(p)<=r) {dat(p)=x;laz(p)=x;return;}
  ll mid=(l(p)+r(p))>>1;pushdown(p);
  if(l<=mid) modify(ls(p),l,r,k);
  if(r>mid) modify(rs(p),l,r,k);
  dat(p)=min(dat(ls(p)),dat(rs(p)));
}

inline ll ask(ll p,ll l,ll r) {
  if(l(p)>=l&&r(p)<=r) {return dat(p);}
  ll mid=(l(p)+r(p))>>1;pushdown(p);
  if(l>mid) return ask(rs(p),l,r);
  if(r<=mid) return ask(ls(p),l,r);
  return min(ask(ls(p),l,r),ask(rs(p),l,r));
}

inline ll read() {
  ll ret=0,f=1;char ch=getchar();
  while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
  while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
  return ret*f;
}

inline void write(ll x) {
  static char buf[22];static ll len=-1;
  if(x>=0) {
    do{buf[++len]=x%10+48;x/=10;}while(x);
  }
  else {
    putchar('-');
    do{buf[++len]=-(x%10)+48;x/=10;}while(x);
  }
  while(len>=0) putchar(buf[len--]);
}

inline void writeln(ll x) {
  write(x);putchar('\n');
}

int main() {

  n=read();k=read();

  for(ll i=1;i<=n;i++) {b[i]=read();}

  build(1,1,n);cnt=1;l(cnt)=1;r(cnt)=n*k;dat(cnt)=queryb(1,n*k);

  q=read();

  while(q--) {
    op=read();l=read();r=read();
    if(op==1) {x=read();modify(1,l,r,x);}
    if(op==2) {writeln(ask(1,l,r));}
  }

  return 0;
}