TIOJ 1176 . Cows

stack
dp 一下

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<cmath>
using namespace std;
typedef long long int int64;
int arr[1000100];
int cnt[1000100];
int link[1000100];
int val[1000100];
int main()
{
 int n;scanf("%d", &n);
 for(int lx = 0;lx < n;lx++)
  scanf("%d", arr+lx);
 cnt[n-1] = 0;
 val[0] = arr[0], link[0] = 1; int ptr = 0;
 for(int lx = n-2;lx >= 0;lx--){
  int ccc = 1;
  while(ptr > 0 and val[ptr] < arr[lx])
   ccc += link[ptr--];
  ptr++;
  val[ptr] = arr[lx];
  link[ptr] = ccc;
  cnt[lx] = ccc;
 }
 for(int lx = 0;lx < n;lx++)
  printf("%d\n", cnt[lx]);
 return 0;
}