G. Periodic RMQ Problem
题目大意
给你一个序列\(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\)
分析
题目不难,我们就来顺序的捋一下我们要干嘛。
两个操作,区间赋值与询问区间最小值。
但是区间太大啦,是\(10^9\)的数量级。一般线段树区间这么大,那我们肯定要上动态开点了。
并且虽然是求最小值,但是其构成是有规律的,它是由k
个长度为n
的数组拼接而成的。
也就是说,如果我们要求一段区间的最小值,如果该区间,我们的线段树中并未开出对应区间,则代表的是,该区间的最小值是原来数组中对应位置的最小值。
因此,我们要能快速的求出一段静态区间的最值,想到了什么?没错,ST表此时就可以发挥作用。
总的时间复杂度是\(O(q\log(nk)\log(n))\)
AC_code
#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false); cin.tie(0), cout.tie(0)
using namespace std;
const int N = 1e5 + 10,inf = 0x3f3f3f3f;
template<typename T=int,const int N=18,typename Comp=less<T>>//Comp则是设立比较方式
struct ST
{
T ans[N][1<<N];int n,lg[1<<N],k;
void init(T*a,int n_){
n=n_;
lg[0]=-1;for(int i=1;i<=n;i++)lg[i]=lg[i>>1]+1;
for(int i=1;i<=n;i++)ans[0][i]=*++a;
for(int i=1;i<N;i++)
for(int j=1;j+(1<<i)<=n+1;j++)
ans[i][j]=max(ans[i-1][j],ans[i-1][j+(1<<(i-1))],Comp());
}
int query(const int l,const int r){
k=31-__builtin_clz(r-l+1);
return max(ans[k][l],ans[k][r-(1<<k)+1],Comp());
}
};
ST<int,17,greater<int>> st;
struct Node
{
int l,r;
int mi,tag;
}tr[N<<6];
int a[N];
int idx,root;
int n,k,q;
int get(int l,int r)
{
if(r-l+1>=n) return st.query(1,n);
if(r%n==0) return st.query(l%n==0?n:l%n,n);
if(l%n==0) return min(a[n],st.query(1,r%n));
if(l/n!=r/n) return min(st.query(l%n,n),st.query(1,r%n));
return st.query(l%n,r%n);
}
int init(int u,int l,int r)
{
tr[u].tag = tr[u].l = tr[u].r = 0;
tr[u].mi = get(l,r);
return u;
}
void pushup(int u,int l,int r)
{
int L,R,mid = l + r >> 1;
if(!tr[u].l) L = get(l,mid);
else L = tr[tr[u].l].mi;
if(!tr[u].r) R = get(mid+1,r);
else R = tr[tr[u].r].mi;
tr[u].mi = min(L,R);
}
void pushdown(int u,int l,int r)
{
int mid = l + r >> 1;
if(!tr[u].l) tr[u].l = init(++idx,l,mid);
if(!tr[u].r) tr[u].r = init(++idx,mid+1,r);
auto &root = tr[u],&left = tr[tr[u].l],&right = tr[tr[u].r];
if(root.tag)
{
left.tag = root.tag;
right.tag = root.tag;
left.mi = root.tag;
right.mi = root.tag;
root.tag = 0;
}
}
void modify(int &u, int l, int r, int L, int R, int k) {
if(R<l||L>r) return ;
if(!u) u = init(++idx,l,r);
if(L <= l && R >= r) {
tr[u].mi = k;
tr[u].tag = k;
return ;
}
pushdown(u, l, r);
int mid = l + r >> 1;
modify(tr[u].l, l, mid, L, R, k);modify(tr[u].r, mid + 1, r, L, R, k);
pushup(u,l,r);
}
int query(int u,int l,int r,int L,int R)
{
if(R<l||L>r) return inf;
if(L<=l&&r<=R)
{
if(!u) return get(l,r);
return tr[u].mi;
}
pushdown(u,l,r);
int mid = l + r >> 1;
return min(query(tr[u].l,l,mid,L,R),query(tr[u].r,mid+1,r,L,R));
}
int main()
{
ios;
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i];
st.init(a,n);
cin>>q;
while(q--)
{
int op,l,r,x;cin>>op>>l>>r;
if(op==1)
{
cin>>x;
modify(root,1,n*k,l,r,x);
}
else cout<<query(root,1,n*k,l,r)<<'\n';
}
return 0;
}
标签:RMQ,return,int,tr,mid,Periodic,query,Problem,tag
From: https://www.cnblogs.com/aitejiu/p/16836565.html