题目描述
给你一个序列\(a\) 让你支持
\(1\) \(l\) \(r\) \(x\) 区间赋值
\(2\) \(l\) \(r\) 询问区间最小值
我们觉得这个问题太水了,所以我们不会给你序列\(a\)
而是给你序列一个长度为\(n\) 的序列\(b\) ,把\(b\) 复制粘贴\(k\) 次就可以得到\(a\)
\(n\le10^5,k\le10^4,q\le10^5,b_i\le10^9\)
\(1\le l\le r\le n\times k\)
感谢@Kelin 提供的翻译
思路：
对于这种类型的题目，我们先考虑一个简化版的问题：如果没有修改操作，怎么做？
解法：
显然我们可以进行分类讨论：
- \(r-l+1\ge n\) 则答案为 \(Min(0,n-1)\)
- \(r-l+1<n \ \land \ \frac{l}{n}=\frac{r}{n}\) 则答案为 \(Min(l\%n,r\%n)\)
- \(r-l+1<n \ \land \ \frac{l}{n}\neq \frac{r}{n}\) 则答案为 \(\min(Min(l\%n,n-1),Min(0,r\%n))\)
然后我们回归这个题目，显然我们如果将整棵线段树建出来，时间复杂度 \(O(nk\log_2 (nk))\)，空间复杂度 \(O(nk)\)，全部爆掉了。
所以我们要尝试优化这个东西。
首先思考怎么优化空间：
可以考虑使用动态开点线段树，空间复杂度应该是 \(O(q\log_2(nk))\) 大概是这样吧……
然后考虑怎么优化时间：
发现其实复杂度堆积的地方是在建树的部分，复杂度达到了 \(O(nk)\)
所以我们不妨尝试能否不在一开始就建出完整的树。顺着一开始动态开点的顺序思考这个问题。
如果我们根据询问来动态开点，则对于一次修改操作，我们可以将他修改的部分进行标记，其他位置不需要标记。
对于一次询问操作，对于修改的部分我们就遍历一下，否则就在原序列上比较。
然后就可以通过一开始的引例的解法来解决问题了。
具体的代码实现其实也比较简单，没什么思维难度。主要是如果见过类似的题目就会比较简单。
点击查看代码
#include<bits/stdc++.h>
#define mem(a) memset(a,0,sizeof(a))
#define set(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define pt putchar
#define All(a) a.begin(),a.end()
#define T int t;cin>>t;while(t--)
#define rand RAND
using namespace std;
char buf[1<<20],*p1,*p2;
#define gc()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
template<class Typ> Typ &re(Typ &x){char ch=gc(),sgn=0; x=0;for(;ch<'0'||ch>'9';ch=gc()) sgn|=ch=='-';for(;ch>='0'&&ch<='9';ch=gc()) x=x*10+(ch^48);return sgn&&(x=-x),x;}
template<class Typ> void wt(Typ x){if(x<0) putchar('-'),x=-x;if(x>9) wt(x/10);putchar(x%10^48);}
const int maxn=1e5+5;
const int N=2e7+5;
const int mod=1e9+7;
int seed = 19243;
unsigned rand(){return seed=(seed*48271ll)%2147483647;}
int n,k;
int a[maxn];
namespace RMQ{
int st[maxn][20];
void init(){
for(int j=1;j<=18;j++){
for(int i=0;i+(1<<j)-1<n;i++){
st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
}
}
int Mn(int l,int r){
int k=log2(r-l+1);
return min(st[l][k],st[r-(1<<k)+1][k]);
}
}using namespace RMQ;
int rt;
namespace Seg{
struct node{
int mn,tg;
}tree[N];
int ls[N],rs[N];
int idx=0;
int newnode(int l,int r){
idx++;
if(r-l+1>=n)tree[idx].mn=Mn(0,n-1);
else if(l/n==r/n)tree[idx].mn=Mn(l%n,r%n);
else tree[idx].mn=min(Mn(l%n,n-1),Mn(0,r%n));
return idx;
}
void push_down(int x,int l,int r){
int mid=(l+r)>>1;
if(!ls[x])ls[x]=newnode(l,mid);
if(!rs[x])rs[x]=newnode(mid+1,r);
if(!tree[x].tg)return ;
tree[ls[x]].mn=tree[ls[x]].tg=tree[rs[x]].mn=tree[rs[x]].tg=tree[x].tg;
tree[x].tg=0;
return ;
}
void push_up(int x){
tree[x].mn=min(tree[ls[x]].mn,tree[rs[x]].mn);
return ;
}
void update(int &x,int l,int r,int L,int R,int val){
if(!x)x=newnode(l,r);
if(L<=l&&R>=r){
tree[x].mn=tree[x].tg=val;
return ;
}
int mid=(l+r)>>1;
push_down(x,l,r);
if(L<=mid)update(ls[x],l,mid,L,R,val);
if(R>mid)update(rs[x],mid+1,r,L,R,val);
push_up(x);
}
int query(int &x,int l,int r,int L,int R){
if(!x)x=newnode(l,r);
if(L<=l&&R>=r){
return tree[x].mn;
}
int mid=(l+r)>>1;
push_down(x,l,r);
int res=1e18;
if(L<=mid)res=min(res,query(ls[x],l,mid,L,R));
if(R>mid)res=min(res,query(rs[x],mid+1,r,L,R));
return res;
}
}using namespace Seg;
signed main(){
cin>>n>>k;
for(int i=0;i<n;i++)cin>>a[i];
for(int i=0;i<n;i++)st[i][0]=a[i];
init();
int Q;cin>>Q;
while(Q--){
int op;
cin>>op;
if(op==1){
int l,r,c;cin>>l>>r>>c;
l--,r--;
update(rt,0,n*k-1,l,r,c);
}
else{
int l,r;
cin>>l>>r;
l--,r--;
cout<<query(rt,0,n*k-1,l,r)<<endl;
}
}
return 0;
}