一个小问题
  • 板块学术版
  • 楼主rainygame
  • 当前回复7
  • 已保存回复7
  • 发布时间2023/3/18 10:35
  • 上次更新2023/10/23 21:18:15
查看原帖
一个小问题
804607
rainygame楼主2023/3/18 10:35

给出一个长度为 nn 数列 aa,求有多少个数对 (i,j)(i,j) 使得 i<ji < jai<aja_i < a_j。保证 2n1052 \leq n \leq 10^5

我是用单调栈做的:

#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;
}

但是通过不了(结果错误)。

2023/3/18 10:35
加载中...