【单调栈】CF771div2 C-Inversion Graph

痛定思痛。 2024-03-23 13:56 59阅读 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 条评论，59人围观）

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

相关阅读

相关 CF723div2 vp

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

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

相关 CF862 div2 D. A Wide, Wide Graph

[Problems - Codeforces][] ![d54b2f1d55aa48239a91dc1fcb026829.png][] 思路：因为要我们输出k为1~n的

╰+攻爆jí腚メ/ 2024年03月24日 14:04/ 0 赞/ 43 阅读

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

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

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

相关【gcd】CF826div2 B

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

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

相关【CF#581(Div.2)】A&B

date：2019.8.20 我第一次打CF的比赛，感觉题目非常新颖并且非常棒，但是由于翻译软件不太给力所以我对题意的理解也不是很透彻，最后我做出了前两道题，感觉还可以吧

骑猪看日落/ 2023年06月05日 08:54/ 0 赞/ 5 阅读

相关 CF#692 div2

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

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

相关单调栈

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

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

相关单调栈

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

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

相关 CF572_Div2_F

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

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

相关单调栈

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

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