题意：给你一个序列，问将序列倒过来后，对于每个点，在再碰到第一个比它大的点之前，有多少比它小的？
求出比它小的个数的和
样例：
6
10
3
7
4
12
2
output： 5
倒序后：2 12 4 7 3 10 6
答案： 0 1 0 1 0 3 0
因此最终输出1+1+3=5
虽然是单调栈裸题（打完暴力才刚看出来）
不过我还是坚持写了暴力（明明是刚开始没思路）
#include<cstdio> #include<iostream> #include<cstring> #include<cctype> #include<algorithm> using namespace std; #define int long long #define olinr return #define _ 0 #define love_nmr 0 #define DB double inline int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) { if(ch=='-') f=-f; ch=getchar(); } while(isdigit(ch)) { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } inline void put(int x) { if(x<0) { x=-x; putchar('-'); } if(x>9) put(x/10); putchar(x%10+'0'); } int n; int a[80505]; int tot; int ans; signed main() { n=read(); for(int i=1;i<=n;i++) a[i]=read(); for(int i=1;i<=n;i++) { tot=0; int now=i+1; while(now<=n&&a[now]<a[i]) { tot++; now++; } ans+=tot; } put(ans); olinr ~~(0^_^0)+love_nmr; }
正解：单调栈
考虑维护一个从下到上递减的栈
来一个数1、比栈顶大---》一直弹并统计答案，最后入栈
否则直接入栈
然而。。。。WA
比如12 4 7 3 10
7来的时候，我们把4 弹了出去
但是等10来的时候，4可是要统计进答案的啊
而我们已经把它弹出去了！
怎么办呢？
（请教大佬之后发现）很简单
栈中不再维护元素值，维护元素下标！
入栈入的是下标
这样在弹栈的时候直接让下标作差就可以求出直接有多少数
避免了答案的漏洞
#include<cstdio> #include<iostream> #include<cstring> #include<cctype> #include<algorithm> using namespace std; #define int long long #define olinr return #define _ 0 #define love_nmr 0 #define DB double inline int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) { if(ch=='-') f=-f; ch=getchar(); } while(isdigit(ch)) { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } inline void put(int x) { if(x<0) { x=-x; putchar('-'); } if(x>9) put(x/10); putchar(x%10+'0'); } int n; int a[80505]; int ans; struct node { int tp; int s[80505]; void pop() { tp--; } int top() { return s[tp]; } bool empty() { return tp==0; } void push(int x) { tp++; s[tp]=x; } int size() { return tp; } }s; //手写栈就是快@！ int tot; signed main() { n=read(); for(int i=1;i<=n;i++) a[i]=read(); s.push(n+1); a[n+1]=0x7fffffff; //便于求tot for(int i=n;i>=1;i--) { if(s.empty()) { s.push(i); //推下标 continue; } if(a[i]<a[s.top()]) //比的时候注意存的是下标 { s.push(i); //推下标 continue; } while(!s.empty()&&a[s.top()]<a[i]) s.pop(); ans+=s.top()-i-1; //统计 s.push(i); // ans+=tot; } put(ans); olinr ~~(0^_^0)+love_nmr; }