#C241125D. 最小值

标签（Label）

• 笛卡尔树

网址（Website）

题目详情 - 最小值 - Super

题解 - 最小值 - Super

题目（Problem）

输入数据 1

3
1 3 4
8 5 7

输出数据 1

2
2
4

【样例1解释】

$k=1, l=2, r=2 $；

$k=2, l=2, r=3 $；

$k=3, l=1, r=3$。

【样例2】

见选手目录下的 $min/min2.in$ 与 $min/min2.ans$。

该样例满足测试点 $1\sim3$ 的限制。

【样例3】

见选手目录下的 $min/min3.in$ 与 $min/min3.ans$。

该样例满足测试点 $4\sim8$ 的限制。

【样例4】

见选手目录下的 $min/min4.in$ 与 $min/min4.ans$。

该样例满足测试点 $9\sim10$ 的限制。

【样例5】

见选手目录下的 $min/min5.in$ 与 $min/min5.ans$。

该样例满足测试点 $11\sim16$ 的限制。

【样例6】

见选手目录下的 $min/min6.in$ 与 $min/min6.ans$。

该样例满足测试点 $17\sim20$ 的限制。

【样例7】

见选手目录下的 $min/min7.in$ 与 $min/min7.ans$。

该样例满足测试点 $21\sim25$ 的限制。

题解（Solution）

记录这道题主要是因为打部分分的时候没有把思路想清楚，导致最后没有打出来（悲~）

笛卡尔树很好处理，注意根是 st[1] 。

出题者题解

代码（Code）

64分

#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
#define show(a) For(i,1,n) cerr<<a[i]<<' ';cerr<<' ';
using namespace std;
#define P pair<int,int> 
#define int long long
#define x first
#define y second
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}template<typename G>
void write(G x){
	if(x<0) putchar('-'),write(-x);
	else if(x<=9) putchar('0'+x);
	else write(x/10), putchar(x%10+'0');
}constexpr int inf = 0x3f3f3f3f3f3f3f3f;
constexpr int N = 1012345;
bool ST;

int a[N],b[N];
int n,as[N];

namespace S1{
	inline bool check(){return n<=1000;}
	void Solve(){
		cerr<<"Solve1\n";
		For(i,1,n){
			int m1=inf,m2=inf;
			For(j,i,n){
				m1=min(m1,a[j]), m2=min(m2,b[j]);
				as[j-i+1] = min(as[j-i+1], abs(m1-m2));
			}
		}For(i,1,n) write(as[i]), putchar('\n');
	}
}

namespace S2{
	inline bool check(){
		For(i,1,n) if(b[i]^1) return false;
		return true;
	}
	void Solve(){
		cerr<<"Solve2\n";
		int mn = *min_element(a+1,a+n+1);
		For(i,1,n) write(mn-b[i]), putchar('\n');
	}
}

namespace S3{
	inline bool check(){
		For(i,1,n) if(b[i]^1000000000) return false;
		return true;
	}
	int ch[N][2],st[N],tp;
	int mn[N],siz[N];
	void dfs(int x){
		siz[x] = 1;
		For(i,0,1){
			int y = ch[x][i];
			if(y){
				dfs(y);
				siz[x] += siz[y];
			}
		}mn[siz[x]] = max(mn[siz[x]], a[x]);
	}
	void Solve(){
		cerr<<"Solve3\n";
		For(i,1,n){
			while(tp && a[st[tp]] > a[i]) ch[i][0] = st[tp--];
			if(tp) ch[st[tp]][1] = i;
			st[++tp] = i;
		}dfs(st[1]);
		Rof(i,n-1,1) mn[i] = max(mn[i],mn[i+1]);
		For(i,1,n) write(abs(b[i]-mn[i])), putchar('\n');
	}
}

void Solve(){
	n=rd();For(i,1,n) a[i]=rd();For(i,1,n) b[i]=rd();
	memset(as, 0x3f, sizeof as);
	if(S1::check()) return S1::Solve();
	if(S2::check()) return S2::Solve();
	if(S3::check()) return S3::Solve();
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("min.in","r",stdin);
	freopen("min.out","w",stdout);
	int Tt=1;double Tim = clock();
	while(Tt--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}