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