【Description】
whitecloth 最近參觀了樓蘭圖騰。圖騰的所在地有一排 N 個柱子，N
個柱子的高度恰好為一個 1 到 N 的排列，而樓蘭圖騰就隱藏在這些
柱子中。
由于 whitecloth 弱爆了，他只知道圖騰由 3 個柱子組成，這三個柱子
組成了下凸或上凸的圖形（>.<），所謂下凸，設三個柱子的高度從左
到右依次為 h1，h2，h3，那么 h1>h2，h3>h2，上凸則滿足 h1<h2，
h3<h2。
現在 whitecloth 也找不到圖騰具體是哪三個柱子，他只想知道滿足這
兩個形狀的柱子有幾組。
【Input】
第一行一個數 N
接下來一行 N 個數，依次表示每個柱子的高度
【Output】
一行兩個數，表示下凸形狀的數量和上凸形狀的數量，用空格隔開
【Sample Input】
5
1 5 3 2 4
【Sample Output】
3 4
【Hint】對于 30%的數據，N<=100
對于 100%的數據，N<=200000

?

這道題其實就是一道裸的樹狀數組，知道一個柱的高度，他左邊比他矮的個數乘以右側比他矮的就是以他為中間柱的上凸形，同理可求得下凹形的。關鍵是知道怎么樣計算出這些數值，沒掃到一個位置，將他的高度壓入樹狀數組，之后掃到一個位置i，lowbit（height（i））就知道了他左側有多少比他矮，一共height（i）-1個比他矮的，也就知道了右邊有多少比他矮，左側一共i-1個數中有多少個比他矮知道了，左側有多少個比他高也就知道了，右側高的也就知道了，綜上所述，可得到ANS。（中間過程記得開long long）。

1 #include<cstdio> 2 #define MAXN 200050UL 3 #define LL long long 4 using namespace std; 5 6 int n,sum[MAXN],h[MAXN]; 7 int ni[MAXN]; 8 LL aa,at; 9 10 int lowbit(int x){ 11 return x&(-x); 12 } 13 void update(int x){ 14 while(x<=n){ 15 sum[x]+=1; 16 x+=lowbit(x); 17 } 18 return ; 19 } 20 int query(int x){ 21 int fec=0; 22 while(x>0){ 23 fec+=sum[x]; 24 x-=lowbit(x); 25 } 26 return fec; 27 } 28 29 int main(){ 30 // freopen("count.in","r",stdin); 31 // freopen("count.out","w",stdout); 32 scanf("%d",&n); 33 for(int i=1;i<=n;i++){ 34 scanf("%d",&h[i]); 35 ni[i]=h[i]-query(h[i]); 36 int t=query(h[i]); 37 at+=(LL)t*(LL)(h[i]-1-t); 38 aa+=(LL)(i-1-t)*(LL)(n-h[i]-i+1+t); 39 update(h[i]); 40 } 41 printf("%lld %lld",aa,at); 42 getchar(); getchar(); getchar(); 43 } View Code

?

轉載于:https://www.cnblogs.com/leni/p/4869730.html

總結

以上是生活随笔為你收集整理的图腾计数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。