C11PAIRS - Đếm cặp
Tác giả: skyvn97
Ngôn ngữ: C++
#include<bits/stdc++.h>
#define MAX 500500
#define v first
#define e second
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
int a[MAX];
int n;
ll res;
stack<ii> st;
void init(void) {
scanf("%d",&n);
int i;
for (i=1;i<=n;i=i+1) scanf("%d",&a[i]);
}
void process(void) {
while (!st.empty()) st.pop();
res=0LL;
int i;
for (i=1;i<=n;i=i+1) {
if (st.empty()) st.push(ii(a[i],1));
else {
if (st.top().v>a[i]) {
res++;
st.push(ii(a[i],1));
}
else if (st.top().v==a[i]) {
res+=st.top().e+(st.size()>1);
st.top().e++;
}
else {
while (!st.empty() && st.top().v<a[i]) {
res+=st.top().e;
st.pop();
}
if (st.empty()) st.push(ii(a[i],1));
else {
if (st.top().v==a[i]) {
res+=st.top().e+(st.size()>1);
st.top().e++;
}
else {
res++;
st.push(ii(a[i],1));
}
}
}
}
}
printf("%lld",res);
}
int main(void) {
init();
process();
return 0;
}