给出一个长度为 n 数列 a,求有多少个数对 (i,j) 使得 i<j 且 ai<aj。保证 2≤n≤105。
我是用单调栈做的:
#include <bits/stdc++.h>
using namespace std;
int n;
unsigned __int128 num;
stack<unsigned __int128> st;
unsigned __int128 ans;
inline unsigned __int128 uread(){
unsigned __int128 x(0);
char ch;
while ((ch = getchar()) < 48);
do{
x = (x << 1) + (x << 3) + (ch ^ 48);
}while ((ch = getchar()) > 47);
return x;
}
inline void print(unsigned __int128 x){
unsigned __int128 tmp = x/10;
if (tmp) print(tmp);
putchar('0'+x-(tmp<<1)-(tmp<<3));
}
int main(){
cin >> n;
for (int i=1; i<=n; i++){
num = uread();
while (!st.empty() && num < st.top()) st.pop();
ans += st.size();
st.push(num);
}
print(ans);
return 0;
}
但是通过不了(结果错误)。