C11PAIRS - Đếm cặp
Tác giả: ladpro98
Ngôn ngữ: C++
#include <iostream>
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
const int N = 500005;
using namespace std;
int a[N], S[N], lazy[N];
int n, top;
int main() {
ios :: sync_with_stdio(0); cin.tie(0);
cin >> n;
FOR(i, 0, n) cin >> a[i];
top = 0; long long ans = 0;
FOR(i, 0, n) {
while (top && a[S[top - 1]] < a[i]) ans += lazy[--top];
if (top && a[S[top - 1]] == a[i]) {
ans += lazy[top - 1];
lazy[top - 1]++;
if (top > 1) ans++;
}
else {
if (top) ans++;
lazy[top] = 1;
S[top++] = i;
}
}
cout << ans;
return 0;
}