首页 > 其他分享 >CF-91-B-单调栈+二分

CF-91-B-单调栈+二分

时间:2024-01-23 11:13:57浏览次数:37  
标签:二分 int siz DSU 栈顶 CF vector 91

91-B 题目大意

给定一个长为\(n\)的序列\(a\),对于每个\(a[i]\),你需要找到一个\(j\)满足\(a[i]>a[j]\)且\(j-i\)最大。


Solution

逆序遍历,维护一个单调递减的栈,如果当前枚举的\(a[i]\)小于栈顶元素,则入栈。如果\(a[i]\)大于栈顶元素,那么后面的元素如果大于\(a[i]\),那么也大于栈顶元素,且栈顶元素能够使得\(j-i\)更大,这时\(a[i]\)无需入栈。

查询\(j\)只需要在这个单调栈上二分即可。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

template<typename T>
struct DSU{
	int n;
	vector<T> p,siz;
	DSU(int _n):p(_n+1),siz(_n+1),n(_n){
		iota(p.begin(),p.end(),0);
		for(int i=0;i<=n;i++) siz[i]=1;
	}
	T findd(T x){
		return p[x]==x?x:p[x]=findd(p[x]);
	}
	void unionn(T x,T y){
		x=findd(x),y=findd(y);
		if(x==y) return;
		if(siz[x]>siz[y]) swap(x,y);
		p[x]=y;
		siz[y]+=siz[x];
	}
};

void solve(){
    int n,m;
    cin>>n>>m;
    vector<DSU<int>> pre(m+2,DSU<int>(n)),suf(m+2,DSU<int>(n));
    vector<pair<int,int>> e(m);
    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        e[i]={x,y};
    }
    for(int i=1;i<=m;i++){
        auto [x,y]=e[i-1];
        pre[i]=pre[i-1];
        pre[i].unionn(x,y);
    }
    for(int i=m;i;i--){
        auto [x,y]=e[i-1];
        suf[i]=suf[i+1];
        suf[i].unionn(x,y);
    }
    int q;
    cin>>q;
    while(q--){
        int l,r;
        cin>>l>>r;
        auto u=pre[l-1],v=suf[r+1];
        for(int i=1;i<=n;i++){
            u.unionn(i,v.findd(i));
        }
        int ans=0;
        for(int i=1;i<=n;i++){
            if(u.p[i]==i){
                ans++;
            }
        }
        cout<<ans<<'\n';
    }
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
    int T=1;
    //cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

标签:二分,int,siz,DSU,栈顶,CF,vector,91
From: https://www.cnblogs.com/fengxue-K/p/17981899

相关文章

  • CF-292-D-并查集
    292-D题目大意给定一张无向图,由\(n\)个顶点\(m\)条边。有\(q\)次询问,每次询问将\([l,r]\)的边删去,问图中有多少连通分量。Solution涉及连通分量,尝试应用并查集解决。记录一个前缀并查集\(pre[i]\),表示前\(i\)条边连通后的图;和一个后缀并查集\(suf[i]\),表示后\(m-i\)条边连通......
  • 二分查找
    二分查找一、应用场景​ 一个很常见的情景:猜数——猜大了就小一点,猜小了就大一点。我们在这个例子中发现,不停的缩小范围,舍弃(更贴切的说法是“排除”)不必要的搜查范围,这样有利于我们去快速查找。​ 这种二分思想,我们也可应用到其他方面:比如开平方数之类——不停的从目标区间的......
  • CF1424M Ancient Language 题解
    1.题意描述一本字典中有\(r\)\((1\leqr\leq10^6)\)个单词,单词长度不超过$10^3$,所有字母都是小写英文字母,但字母排序不是按英文字母排序,求所有出现字母的一种排序,如果不存在,输出"IMPOSSIBLE"。2.题目分析由排序规则可知,对于字符串\(s\)和\(t\),\(s\)排在\(t\)......
  • CF618C Constellation 题解
    题意描述给定\(n\)个点(\(n\leq10^5\)),找到三个点满足这三个点不在同一直线上且三个点构成的三角形中不包含其他点,保证所有点不会在同一直线上。题目分析首先必然每一个点都可以作为一组解中的点。不妨其中一个点编号为\(1\)。找一个点作为第二个点,为了使没有点在这条边上,这......
  • CF1036F Relatively Prime Powers 题解
    题目分析对于一个不合法的数\(x(x\ge2)\),设\(x=\prodp_i^{r_i}\),令\(g=\gcd(r_1,r_2,\ldots,r_k)\),则\(x=\left(\prodp_i^{r_i/g}\right)^g\),所以\(x\)是一个正整数的\(g\)次方。所以可以枚举上文的\(g\),把每一类不合法方案排除掉,就是答案。设\(f(i)\)表示\(2\)......
  • 线段树二分
    问题描述维护长度为\(n\)的序列\(a\),支持以下操作:1ix:把\(a_i\)修改为\(x\)。2ix:询问最小的\(j\)满足\(j>=i\)且\(a_j>=x\)。\(1\leqn\leq10^6\)解决方法在线段树外直接二分可以做到\(O(n\log^2n)\)的时间复杂度,加上简单的剪枝可能效率会高一些,但都无......
  • Ybt 金牌导航 6.1.F 大根堆 / BZOJ 4919 大根堆(LIS,启发式合并)
    题意简述有一个以\(1\)为根的有根树,每个点有权值\(v_i\)。你需要选出一个点集\(S\),使得点集里任意两个元素\(x,y\),若\(x\)在原树上是\(y\)的祖先,则要满足\(v_x>v_y\)。求选出的点集的最大大小是多少。解法原题限制相当于:在选出的点集构成的新树\(T\)中,每个点到根节......
  • CF1914D Three Activities
    题目大意给定三个数组\(a,b,c\)找三个互不相同的整数\(i,j,k\)使得\(a_i+b_j+c_k\)的值最大.思路首先想到的当然是枚举\(i,j,k\)然后找到最大值,但这种方法的时间复杂度是\(O(n^3)\),显然会喜提\(TLE\).当然由瞪眼法可知,因为我们只需要找到\(a_i+b_j......
  • CF-1831-E-卡特兰数+异或哈希+差分
    1831-E题目大意给定一个整数\(n\),和\(k\)个区间,区间端点范围在\([1,n]\)内。如果有一个长为\(n\)合法的括号序列,且它的这\(k\)个区间\([l,r]\)中的子括号序列也是合法的,那么称这个括号序列是“好的”。请你求出有多少个长度为\(n\)的“好的”括号序列,答案对\(998244353\)取模......
  • 从CF1875C学习lowbit运算判断是否为 2 的 k 次幂
    Problem-1875C-Codeforces本题判断无解的时候要判断该数是否为2的k次幂,我的做法是预处理出2的次幂数表。看题解发现可以用lowbit操作。lowbit操作intlowbit(intx){returnx&(-x);}根据补码原理,该操作可以求出来X最靠右的\(1\)构成的数。判断\(x\)......