思路:
(我也不知道这是不是正解)
ST表预处理出来原数列的两点之间的min
再搞一个动态开节点线段树
节点记录ans 和标记
lazy=-1 当前节点的ans可用 lazy=0 没被覆盖过 else 区间覆盖
push_up的时候要注意好多细节,,
数组尽量往大开
//By SiriusRen
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=;
int n,k,q,op,xx,b[N],f[N][],lson[N<<],rson[N<<],root,cnt;
int lazy[N<<],ans[N<<],base[N];//lazy=-1 废了 lazy=0 原数列 else 区间覆盖
int RMQ(int x,int y){
int t=base[y-x+];
return min(f[x][t],f[y-(<<t)+][t]);
}
int qry(int l,int r){
if(r-l>=n)return RMQ(,n);
else{
l=(l-)%n+,r=(r-)%n+;
if(l>r)return min(RMQ(,r),RMQ(l,n));
else return RMQ(l,r);
}
}
void push_down(int pos){
if(!lson[pos])lson[pos]=++cnt;lazy[lson[pos]]=lazy[pos];
if(!rson[pos])rson[pos]=++cnt;lazy[rson[pos]]=lazy[pos];
}
void insert(int l,int r,int &pos,int L,int R,int wei){
if(!pos)pos=++cnt;
// printf("l=%lld r=%lld pos=%d\n",l,r,pos);
if(lazy[pos]&&~lazy[pos]){
ans[pos]=lazy[pos];
push_down(pos);
lazy[pos]=-;
}
if(l>=L&&r<=R){ans[pos]=lazy[pos]=xx;return;}
int mid=(l+r)>>;
if(mid<L)insert(mid+,r,rson[pos],L,R,wei);
else if(mid>=R)insert(l,mid,lson[pos],L,R,wei);
else insert(l,mid,lson[pos],L,R,wei),insert(mid+,r,rson[pos],L,R,wei);
int temp=0x3f3f3f3f;
if(lson[pos]){
if(!lazy[lson[pos]])temp=qry(l,mid);
else if(lazy[lson[pos]]==-)temp=ans[lson[pos]];
else temp=lazy[lson[pos]];
}
else temp=qry(l,mid);
if(lazy[rson[pos]]){
if(!lazy[rson[pos]])temp=min(temp,qry(mid+,r));
else if(lazy[rson[pos]]==-)temp=min(temp,ans[rson[pos]]);
else temp=min(temp,lazy[rson[pos]]);
}
else temp=min(temp,qry(mid+,r));
ans[pos]=temp,lazy[pos]=-;
}
int query(int l,int r,int pos,int L,int R){
if(l==L&&r==R){
if(lazy[pos]==-)return ans[pos];
else if(!lazy[pos])return qry(l,r);
else return lazy[pos];
}
if(!pos)return qry(L,R);
if(lazy[pos]&&~lazy[pos])return lazy[pos];
int mid=(l+r)>>;
if(mid<L)return query(mid+,r,rson[pos],L,R);
else if(mid>=R)return query(l,mid,lson[pos],L,R);
else return min(query(l,mid,lson[pos],L,mid),query(mid+,r,rson[pos],mid+,R));
}
void DFS(int l,int r,int pos){
printf("l=%d r=%d pos=%d lazy[pos]=%d ans[pos]=%d\n",l,r,pos,lazy[pos],ans[pos]);
int mid=(l+r)>>;
if(lson[pos])DFS(l,mid,lson[pos]);
if(rson[pos])DFS(mid+,r,rson[pos]);
}
int main(){
scanf("%d%d",&n,&k);
base[]=-;
for(int i=;i<=n;i++)scanf("%d",&b[i]),f[i][]=b[i],base[i]=base[i>>]+;
for(int j=;j<=;j++)
for(int i=;i+(<<(j-))<=n;i++)
f[i][j]=min(f[i][j-],f[i+(<<(j-))][j-]);
scanf("%d",&q);
while(q--){
int l,r;
scanf("%d%d%d",&op,&l,&r);
if(op==){
scanf("%d",&xx);
insert(,n*k,root,l,r,xx);
}
else{
printf("%d\n",query(,n*k,root,l,r));
}
// DFS(1,1ll*n*k,1);
}
}
/*
8 4
5 6 1 3 3 2 9 6 14
1 10 19 2
2 14 26 */