官方题解居然压行了(
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <stack>
using namespace std;
typedef long long llint;
typedef pair<int,int> par;
stack<par> S;
int main( void ) {
int n;
scanf( "%d", &n );
llint ret = 0;
for( int i = 0; i < n; ++i ) {
int h;
scanf( "%d", &h );
par p( h, 1 );
for( ; !S.empty() && S.top().first <= h; S.pop() ) {
ret += S.top().second;
if( S.top().first == h ) p.second += S.top().second;
}
if( !S.empty() ) ++ret;
S.push( p );
}
cout << ret << endl;
return 0;
}
非stack版,用了一个二分查找加速
#include<iostream>
using namespace std;
long long stack[10000000], n, top = 1, ans, m;
int main() {
cin>>n;
int a;
cin>>stack[1];
for (int i = 2; i <= n; i++) {
cin>>a;
if (stack[top] > a) {
stack[++top] = a;
++ans;
} else {
int l = 1, r = top;
while (l < r) {
m = (l + r) >> 1;
if (r == l + 1) m = r;
if (a >= stack[m]) r = m - 1;
else l = m;
}
ans += top - l + 1;
while (top && stack[top] < a) top--;
stack[++top] = a;
}
}
cout<<ans;
}