CF803G Periodic RMQ Problem

简要题意

你需要维护一个序列 \(a\)，有 \(q\) 个操作，支持：

1 l r x 将 \([l,r]\) 赋值为 \(x\)。
2 l r 询问 \([l,r]\) 的最小值。

为了加大难度，\(a\) 不会直接告诉你，但是会告诉你一个长度为 \(n\) 的序列 \(b\) 和一个整数 \(k\)，\(a\) 是将 \(b\) 复制 \(k\) 遍依次拼接而成。

\(1 \leq n,q \leq 10^{5},1 \leq k \leq 10^{4},1 \leq b_i \leq 10^9,1 \leq l_i \leq r_i \leq nk\)

思路

如果直接求出 \(a\)，那么时间复杂度和空间复杂度（都是 \(O(nk)\)）不能接受。

我发现，如果没有修改，那么只需要用一个 ST 表即可，具体操作如下：

如果 \((r-l+1)\geq n\)，那么一定包含所有 \(b\) 中的元素，直接返回 \(b[1,n]\) 的最小值。
如果 \((l-1)\bmod n+1>(r-1)\bmod n+1\)，那么这个区间是跨区块的，如图：

（红色为 \(b\) 块，蓝色为询问 \([l,r]\)，黑色为数值）

那么就是相对应的后缀最小值和前缀最小值的最小值。

剩下的情况是完全在 \(b\) 块中，ST 表查询。

如果带上修改呢？我们可以打一个标记，如果这个区间有修改，那么直接读取修改后的结果，否则走上述过程。这一步可以使用动态开点线段树完成。

不过我的动态开点线段树总是会 TLE 掉一些点，由于本题数据随机，我们使用 ODT 替换掉动态开点线段树，就可以 AC 了。

时间复杂度均摊 \(O(n\log n+q\log nk)\)，可以通过本题。

代码

#include<bits/stdc++.h>

#pragma GCC optimize("Ofast", "inline", "-ffast-math")

#pragma GCC target("avx,sse2,sse3,sse4,mmx")

using namespace std;

const int N=100005;

int n,m,k,f[N][25],lg[N]= {-1},pre[N],suf[N];

int min_=INT_MAX,min_ans=INT_MAX;

int st(int l,int r){

	int logg=lg[r-l+1];

	return min(f[l][logg],f[r-(1<<logg)+1][logg]);

}

int solve(int l,int r) {

	if(r-l+1>=n){// 如果包含整个块，那么最小值一定是 min(b[1],...,b[n])

		return min_;

	}

	l=(l-1)%n+1; // 转成块内坐标

	r=(r-1)%n+1;// 转成块内坐标

	if(l>r){// 如果不在同一个块，直接返回右半块+左半块

		return min(pre[r],suf[l]);

	}

	return st(l,r); // 如果在同一个块,ST表查询

}

struct node {

	int l,r;

	mutable int v;

	bool covered;

	node(int ls,int rs=-1,int vv=0,bool coverevd=0){

		l=ls,r=rs,v=vv,covered=coverevd;

	}

	bool operator<(const node &a)const {

		return this->l<a.l;

	}

};

set<node>s;

set<node>::iterator split(int p) {// 分裂区间

	if(p>n*k)return s.end();

	set<node>::iterator it=--s.upper_bound(node(p,0,0,0));

	if((*it).l==p)return it;

	int l=(*it).l,r=(*it).r,v=(*it).v;

	bool covered=(*it).covered;

	s.erase(it);

	s.insert(node(l,p-1,v,covered));

	return s.insert(node(p,r,v,covered)).first;

}

void assign(int l,int r,int v) { // 区间赋值

	set<node>::iterator rs=split(r+1),ls=split(l);

	s.erase(ls,rs);

	s.insert(node(l,r,v,1));

	min_ans=min(min_ans,v);

}

int query(int l,int r) {

	int ans=INT_MAX;

	set<node>::iterator rs=split(r+1),ls=split(l);

	for(set<node>::iterator it=ls; it!=rs; ++it) {

		bool covered=(*it).covered;

		if(covered) { // 如果被覆盖了，就直接用覆盖的值

			ans=min(ans,(*it).v);

		} else { // 如果没有被覆盖，就去 ST 表中查询

			ans=min(ans,solve((*it).l,(*it).r));

		}

		if(ans==min_ans)break; // 如果已经查到全序列最小值，就直接返回

	}

	return ans;

}

int main() {

	scanf("%d%d",&n,&k);

	for(int i=1;i<=n;i++) {

		scanf("%d",&f[i][0]);

	}

	pre[0]=suf[n+1]=INT_MAX;

	for(int i=1;i<=n;i++) {

		pre[i]=min(pre[i-1],f[i][0]);

		lg[i]=lg[i>>1]+1;

		min_=min(min_,f[i][0]);

		min_ans=min(min_ans,f[i][0]);

	}

	for(int i=n;i>=1;i--) {

		suf[i]=min(suf[i+1],f[i][0]);

	}

	for(int j=1;j<=20;j++) {

		for(int i=1;i<=n+1-(1<<j);i++){

			f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);

		}

	}

	s.insert(node(1,n*k,min_,0));

	scanf("%d",&m);

	for(int i=1;i<=m;i++) {

		int op,l,r,x;

		scanf("%d%d%d",&op,&l,&r);

		if(op==1) {

			scanf("%d",&x);

			assign(l,r,x);

		} else {

			printf("%d\n",query(l,r));

		}

	}

	return 0;

}

巴特西

CF803G Periodic RMQ Problem

简要题意

思路

代码

最新文章

热门文章