D - Buildings

Problem Statement

There are $N$ buildings, Building $1$, Building $2$, $\ldots$, Building $N$, arranged in a line in this order. The height of Building $i$ $(1 \leq i \leq N)$ is $H_i$.

For each $i = 1, 2, \ldots, N$, find the number of integers $j$ $(i < j \leq N)$ satisfying the following condition:

• There is no building taller than Building $j$ between Buildings $i$ and $j$.

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq H_i \leq N$
• $ H_i\neq H_j\ (i\neq j)$
• All input values are integers.

Sample Input 1

5
2 1 4 3 5

Sample Output 1

3 2 2 1 0

For $i=1$, the integers $j$ satisfying the condition are $2$, $3$, and $5$: there are three. (Between Buildings $1$ and $4$, there is a building taller than Building $4$, which is Building $3$, so $j=4$ does not satisfy the condition.) Therefore, the first number in the output is $3$.

实现

倒着将元素挨个放入单调栈，栈的元素个数即为当前位置的答案

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 10;
int a[N],b[N],c[N];
stack<int>st;
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=n;i>=1;i--){     
        b[i]=st.size();
        while(!st.empty()&&a[i]>st.top()){
            st.pop();
        }
        st.push(a[i]);
    }
    for(int i=1;i<=n;i++){
        cout<<b[i]<<' ';
    }
    cout<<endl;
}
signed main() {
    int t=1;
    //cin >> t;
    while (t--) {
        solve();
    }
       
}

E - K-th Largest Connected Components

Problem Statement

There is an undirected graph with $N$ vertices and $0$ edges. The vertices are numbered $1$ to $N$.

You are given $Q$ queries to process in order. Each query is of one of the following two types:

• Type $1$: Given in the format 1 u v. Add an edge between vertices $u$ and $v$.

• Type $2$: Given in the format 2 v k. Print the $k$-th largest vertex number among the vertices connected to vertex $v$. If there are fewer than $k$ vertices connected to $v$, print -1.

Constraints

• $1 \leq N, Q \leq 2 \times 10^5$
• In a Type $1$ query, $1 \leq u < v \leq N$.
• In a Type $2$ query, $1 \leq v \leq N$, $1 \leq k \leq 10$.
• All input values are integers.

Sample Input 1

4 10
1 1 2
2 1 1
2 1 2
2 1 3
1 1 3
1 2 3
1 3 4
2 1 1
2 1 3
2 1 5

Sample Output 1

2
1
-1
4
2
-1

• In the first query, an edge is added between vertices $1$ and $2$.
• In the second query, two vertices are connected to vertex $1$: $1$ and $2$. Among them, the $1$-st largest vertex number is $2$, which should be printed.
• In the third query, two vertices are connected to vertex $1$: $1$ and $2$. Among them, the $2$-nd largest vertex number is $1$, which should be printed.
• In the fourth query, two vertices are connected to vertex $1$: $1$ and $2$, which is fewer than $3$, so print -1.
• In the fifth query, an edge is added between vertices $1$ and $3$.
• In the sixth query, an edge is added between vertices $2$ and $3$.
• In the seventh query, an edge is added between vertices $3$ and $4$.
• In the eighth query, four vertices are connected to vertex $1$: $1,2,3,4$. Among them, the $1$-st largest vertex number is $4$, which should be printed.
• In the ninth query, four vertices are connected to vertex $1$: $1,2,3,4$. Among them, the $3$-rd largest vertex number is $2$, which should be printed.
• In the tenth query, four vertices are connected to vertex $1$: $1,2,3,4$, which is fewer than $5$, so print -1.

实现

启发式合并+平衡树查询

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace __gnu_cxx;
using namespace __gnu_pbds;
using namespace std;
#define int long long
typedef tree<int, null_type, greater<int>, rb_tree_tag, tree_order_statistics_node_update> Tree;
const int N = 2e6 + 10;
Tree tr[N];
int f[N];
int find(int x){
    return f[x]==x?x:f[x]=find(f[x]);
}
void solve(){
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        tr[i].insert(i);
        f[i]=i;
    }
    for(int i=1;i<=q;i++){
        int st;
        cin>>st;
        if(st==1){
            int u,v;
            cin>>u>>v;
            u=find(u),v=find(v);
            if(u==v) continue;
            if(tr[u].size()>tr[v].size()){
                swap(u,v);
            }
            for(auto it:tr[u]){
                tr[v].insert(it);
                f[it]=v;
            }
            tr[u].clear();
        }
        else{
            int v,k;
            cin>>v>>k;
            v=find(v);
            if(tr[v].size()>=k){
                cout<<*tr[v].find_by_order(k-1)<<endl;
            }
            else{
                cout<<-1<<endl;
            }
        }
    }
}
signed main(){
    int t=1;
    //cin >> t;
    while (t--) {
        solve();
    } 
}