【单调栈】CF771div2 C-Inversion Graph

痛定思痛。 2024-03-23 13:56 39阅读 0赞

[Problem - C - Codeforces][]

题意：

![aa325c0ceb554a5fbaa6e1d1a8eb7d7e.png][]

![df307d82503a45c7a3786f259198b662.png][]

思路：

首先它是个排列，要我们维护连通分量的数量

肯定不能直接建图，复杂度太大，那怎么间接地维护连通块个数呢

我们去维护每一个连通块的代表元素即可

如果第i个位置出现x使得x和前面一些元素组成连通块，那么就需要在栈里删除前缀那些大于x的值，并用x代替

因此可以使用单调栈维护每一个连通分量的代表元素

答案就是栈的大小

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=1e5+10;
    
    stack<int> S;
    int n;
    int a[mxn];
    void solve(){
    	while(!S.empty()) S.pop();
    	cin>>n;
    	for(int i=1;i<=n;i++) cin>>a[i];
    	for(int i=1;i<=n;i++){
    		if(S.empty()||S.top()<a[i]) S.push(a[i]);
    		else{
    			int mx=S.top();
    			while(!S.empty()&&S.top()>a[i]) S.pop();
    			S.push(mx);
    		}
    	}
    	cout<<S.size()<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;cin>>__;
    	while(__--)solve();return 0;
    }

[Problem - C - Codeforces]: https://codeforces.com/contest/1638/problem/C
[aa325c0ceb554a5fbaa6e1d1a8eb7d7e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/7b6f4669bb824432a575b0e908cb4aa6.png
[df307d82503a45c7a3786f259198b662.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/24a297a29a70494db8957ed46825233f.png

发表评论取消回复

表情：

评论列表（有 0 条评论，39人围观）

还没有评论，来说两句吧...

相关阅读

相关 CF723div2 vp

哈哈，我是弱智哈哈，我是弱智哈哈，我是弱智谢谢你xcpc，让我认识到我就是个什么都不会的dinner ![cafe464664a699c7748235ab1488

小鱼儿/ 2024年03月26日 15:51/ 0 赞/ 48 阅读

相关【单调栈】CF771div2 C-Inversion Graph

[Problem - C - Codeforces][] 题意： ![aa325c0ceb554a5fbaa6e1d1a8eb7d7e.png][] ![df307d82

痛定思痛。/ 2024年03月23日 13:56/ 0 赞/ 40 阅读

相关【gcd】CF826div2 B

有人不会div2 B 没关系，精神稳定一分钟也很厉害了嘻嘻，嘻嘻.... [Problem - B - Codeforces][] ![2ad3819b26264c2

不念不忘少年蓝@/ 2024年03月22日 17:20/ 0 赞/ 28 阅读

相关 CF#692 div2

A 从后往前找连续)最长长度判断是否大于n/2即可 B 一个数字只会出现1-9，而1-9的最小公倍数为7560 所以你最多自增7560个数后必能找到符合条件的数，所以暴力模拟

缺乏、安全感/ 2022年12月29日 06:47/ 0 赞/ 149 阅读

相关单调栈

> 参考https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/84-by-ikaru

叁歲伎倆/ 2022年12月12日 13:58/ 0 赞/ 156 阅读

相关单调栈，栈还能单调一下？

之前遇到一个算法题目，自己只会用时间复杂度 O(N^2) 暴力解法解决，有大佬说用单调栈，可以做到 O(N) 的时间复杂度，当时我的表情是这样的： ![1d3f60a4338

水深无声/ 2022年09月12日 11:59/ 0 赞/ 173 阅读

相关单调栈

通过使用栈这个简单的结构，我们可以巧妙地降低一些问题的时间复杂度。单调栈性质： 1、若是单调递增栈，则从栈顶到栈底的元素是严格递增的。若是单调递减栈，则从栈顶到栈底的元素

ゝ一纸荒年。/ 2022年05月12日 07:28/ 0 赞/ 227 阅读

相关单调栈

单调栈性质单调栈是一种特殊的栈，特殊之处在于栈内的元素都保持一个单调性，可能为单调递增，也可能为单调递减。模型例如下图就是一个单调递增的单调栈。 ![

你的名字/ 2021年11月10日 12:46/ 0 赞/ 286 阅读

相关 CF572_Div2_F

题意 [http://codeforces.com/contest/1189/problem/F][http_codeforces.com_contest_1189_pr

╰半夏微凉°/ 2021年10月29日 13:32/ 0 赞/ 261 阅读

相关单调栈

一、单调栈定义单调递增栈：数据出栈的序列为单调递增序列（比站内元素小就入栈，否则将栈中比当前元素小的元素弹出后再入栈）单调递减栈：数据出栈的序列为单调递减

水深无声/ 2021年09月21日 05:40/ 0 赞/ 395 阅读