2023ACM夏合宿 Day5 モノトーンキューとモノトーンスタック

目次- DAY 5 モノトーンキュー/スタック

  • トレーニング概要
  • A問題
  • B問題
  • C問題
  • D問題
  • E問題 未解決、解説補完
  • F問題 未解決、解説補完
  • G問題 CFデータでWAのヒントを得る
  • J問題
  • K問題
  • L問題
  • 補足情報
  • モノトーンスタック
    • モノトーンスタック
  • 矩形関連
  • 辞書順最小
  • 貢献度法
  • モノトーンキュー

DAY 5 モノトーンキュー/スタック

トレーニングリンク：リンク

トレーニング概要

  • 2023.6.30 午前：A、B、C、D問題 午後：E問題（未公開、解説参照）F問題（現在のアプローチ不明） 夜：牛客小白月賽75+F、G問題 今日の学習は主にモノトーンスタック関連の問題に集中。他のキュー系問題は既に解いており、後ほど補完予定
  • 2023.7.1 午前：J、K、L問題 7.1午前は1時間かけてモノトーンキューの復習と整理 他の問題は時間の都合で後回し

A問題

問題概要： 数列が与えられ、各要素の次の大きな値のインデックスを特定する。見つからない場合は0を出力 アプローチ： 降順モノトーンスタックのテンプレート問題

B問題

問題概要： 牛の高さの配列が与えられ、各牛が自分より高い牛を見つけるまでの間の牛の数を合計する アプローチ： A問題と同様の降順モノトーンスタックだが、問題文の解釈がやや複雑

C問題

問題概要： 長さnの配列から[l, r]の区間を選択し、その区間内の最大値と第二最大値のXORの最大値を求める アプローチ： 降順モノトーンスタックを活用して区間の最大値・第二最大値を効率的に特定。スタック操作時にXOR値を更新することでO(n)計算量を実現。この手法はO(n^3)の全探索に比べて圧倒的に高速

D問題

問題概要： すべての区間[l, r]で最大値が和以上であることを確認する アプローチ： 降順スタックで最大値を管理し、スタック操作時に最大値と和の比較を行う。ここでのポイントは、スタックの左右境界に注目することで、すべての区間を網羅的に検証できる点。これは、スタックの構造が区間の性質を保証するためである

E問題 未解決、解説補完

問題概要： すべての区間の第二最大値の総和を求める アプローチ： 単純なモノトーンスタックでは第二最大値の検出が困難。洛谷の解説ではスタックに加えてST表を使用する方法が紹介されている。この実装は今後の学習課題

/*
難易度：高
ロジックは洛谷の解説に基づく。現在理解中
双方向リストの構造を活用したアプローチ
*/
const int maxm=1e5+5,inf=0x3f3f3f3f,mod=998244353;
ll n,a[maxm],L[maxm],R[maxm];

void process(){
	cin>>n;
	ll t;
	for(int i=1;i<=n;++i){
		cin>>t;
		//数値の位置を記録
		a[t]=i;
		//初期の左右境界を設定
		L[i]=i-1;
		R[i]=i+1;
	}
	ll ans=0;
	for(int i=1;i<=n;++i){//昇順で処理
		//左右の境界を取得
		int l=L[a[i]],r=R[a[i]];
		//左側の区間処理
		if(l>=1) ans+=i*(l-L[l])*(r-a[i]);
		//右側の区間処理
		if(r<=n) ans+=i*(R[r]-r)*(a[i]-l);
		//現在の要素を削除
		L[r]=l;R[l]=r;
	}
	cout<<ans<<'\n';
	return ;
}

関連資料： Second Sum！ - Acfboy のブログ - 洛谷ブログ (luogu.com.cn)

F問題 未解決、解説補完

問題概要： 制約付き配列構築問題。V字型パターンを避ける アプローチ： モノトーンスタックで非増加/非減少列を検出。中央凸型のケースを考慮するため、前後缀和を活用

/*
WAの可能性あり
問題文の解釈が不正確だった可能性
*/
const int maxm=5e5+5,inf=0x3f3f3f3f,mod=998244353;
ll n,nums[maxm],left[maxm],right[maxm],ans[maxm];
ll prefix[maxm],suffix[maxm];

void process(){
	cin>>n;
	for(int i=1,j;i<=n;++i){
		cin>>nums[i];
		//スタック構造で境界を検出
		j=i-1;
		while(j>0 && nums[i]<nums[j]){
			j=left[j];
		}
		left[i]=j;
		//前缀和の計算
		prefix[i]=prefix[j]+1ll*(i-j)*nums[i];
	}
	ll s=0,t;
	for(int i=n,j;i>0;--i){
		//スタック構造で境界を検出
		j=i+1;
		while(j<=n && nums[i]<nums[j]) j=right[j];
		right[i]=j;
		//後缀和の計算
		suffix[i]=suffix[j]+1ll*(j-i)*nums[i];
		//最適解の更新
		if(prefix[i]+suffix[i]-nums[i]>s){
			s=prefix[i]+suffix[i]-nums[i];
			t=i;
		}
	}
	//最適解の構築
	for(int i=t-1;i>0;--i){
		if(nums[i]>nums[i+1]) nums[i]=nums[i+1];
	}
	for(int i=t+1;i<=n;++i){
		if(nums[i]>nums[i-1]) nums[i]=nums[i-1];
	}
	for(int i=1;i<=n;++i){
		cout<<nums[i]<<" \n"[i==n];
	}
	return ;
}

関連資料： 解説リンク

G問題 CFデータでWAのヒントを得る

問題概要： n個の数列において、特定の条件を満たす移動経路の最短手数を求める アプローチ： モノトーンスタックを活用して移動条件の検証。重複値の取り扱いに注意

J問題

問題概要： モノトーンキューのテンプレート問題 アプローチ： 降順/昇順キューの維持で解決

K問題

問題概要： モノトーンキューのテンプレート問題 アプローチ： 誤解によりWA。区間最小値の検出に昇順キューを使用

L問題

問題概要： モノトーンキューのテンプレート問題 アプローチ： 昇順キューで最小値を維持

補足情報

モノトーンスタック Monotone Stack

【図解】スタックの2つのアプローチ https://leetcode.cn/problems/next-greater-node-in-linked-list/solution/tu-jie-dan-diao-zhan-liang-chong-fang-fa-v9ab/ 例：各要素の左右で厳密に大きい要素の位置を返す 理解のポイント：配列を山脈に見立て、スタックの性質を活用 テクニック：スタックの底に境界要素を事前に追加して処理を簡略化 変換ルール： 区間[l,r]の最大値がa[r]の場合、l > left[r]が成立 区間[l,r]の最大値がa[l]の場合、r < right[l]が成立

https://oi-wiki.org/ds/monotonous-stack/ https://cp-algorithms.com/data_structures/stack_queue_modification.html

モノトーンスタック

    1. 次の大きい要素 I（スタックテンプレート）
    1. 次の大きい要素 II
    1. 次の大きい要素 IV
    1. 132パターン
    1. 毎日温度
    1. 株価のスパン
    1. リンクドリストの次の大きい要素
    1. 良い期間
    1. 商品割引後の価格
    1. 非減少順に並べる

矩形関連

    1. 柱状図の最大矩形
    1. 最大矩形
    1. 全1サブマトリクスのカウント

辞書順最小

    1. 重複文字を削除
  • 316拡張：重複回数制限
    1. K文字を削除
    1. 最大数を構成

貢献度法

モノトーンキュー Monotone Queue

2つの図で理解するキュー（Python/Java/C++/Go） https://leetcode.cn/problems/shortest-subarray-with-sum-at-least-k/solution/liang-zhang-tu-miao-dong-dan-diao-dui-li-9fvh/ キューの単調性を維持し、常に最大/最小値を保つ 前提知識：双指針 固定サイズの窓の最大値を例に： 左端を1つずつ移動する際、キューの先頭が左端の場合、最大値が変化するためキューの先頭を削除 これにより、常にキューの先頭が現在の窓の最大値となる https://oi-wiki.org/ds/monotonous-queue/ https://oi-wiki.org/dp/opt/monotonous-queue-stack/ https://cp-algorithms.com/data_structures/stack_queue_modification.html https://blog.csdn.net/weixin_43914593/article/details/105791217 競技プログラミング专题解析（13）：DP最適化(3)--モノトーンキュー最適化 todo https://xyzl.blog.luogu.org/DQ-OP-DP

タグ: monotonic queue Monotonic Stack C++ Algorithm Data Structures

8月26日 19:16 投稿

ホットタグ

©2026 異端開発室