數列(sequence.pas/c/cpp)
?-?問題描述
一個簡單的數列問題：給定一個長度為n的數列，求這樣的三個元素ai, aj, ak的個數，滿足ai < aj > ak，且i < j < k。
?-?輸入數據
第一行是一個整數n(n <= 50000)。
第二行n個整數ai(0 <= ai <= 32767)。
?-?輸出數據
一個數，滿足ai < aj > ak (i < j < k)的個數。
-?樣例輸入
5
1 2 3 4 1
-?樣例輸出
6
分析：思路類似問題 A，先求出一個數左邊有多少比它小，再求出一個數的右邊有多少比它小。而問題 A 中已經知道了前面怎么求，那么求右邊有多少比它大，可以把這個數組反過來存，問題就轉化為求左邊有多少比它小。
#include<algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <queue>
#include <stack>
#include <ctime>
#include <cmath>
#include <map>
#include <set>
#define INF 0x3fffffff
#define db1(x) cout<<#x<<"="<<(x)<<endl
#define db2(x,y) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<endl
#define db3(x,y,z) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<endl
#define db4(x,y,z,r) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<", "<<#r<<"="<<(r)<<endl
#define db5(x,y,z,r,w) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<", "<<#r<<"="<<(r)<<", "<<#w<<"="<<(w)<<endl
using namespace std;#define lowbit(i) ((i)&(-i))typedef struct node
{int val,pos;
}node;long long getsum(int x,int n,int c[])
{long long sum=0;for(int i=x;i>0;i-=lowbit(i))sum+=c[i];return sum;
}void update(int x,int v,int n,int c[])
{for(int i=x;i<=n;i+=lowbit(i))c[i]+=v;return;
}bool cmp(node a,node b)
{return a.val<b.val;
}int main(void)
{#ifdef testfreopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);clock_t start=clock();#endif //testint n;while(~scanf("%d",&n)){node num[n+5];int c1[n+5]={0},c2[n+5]={0},a[n+5]={0},b[n+5]={0};for(int i=0;i<n;++i)scanf("%d",&num[i].val),num[i].pos=i;sort(num,num+n,cmp);for(int i=0;i<n;++i){if(i==0||num[i].val!=num[i-1].val)a[num[i].pos]=i+1;else a[num[i].pos]=a[num[i-1].pos];}for(int i=0;i<n;++i)b[i]=a[n-1-i];long long ans=0;long long sum1[n+5]={0},sum2[n+5]={0};for(int i=0;i<n;++i){update(a[i],1,n,c1);sum1[i]=getsum(a[i]-1,n,c1);update(b[i],1,n,c2);sum2[n-1-i]=getsum(b[i]-1,n,c2);}for(int i=0;i<n;++i)ans+=sum1[i]*sum2[i];printf("%lld\n",ans);}#ifdef testclockid_t end=clock();double endtime=(double)(end-start)/CLOCKS_PER_SEC;printf("\n\n\n\n\n");cout<<"Total time:"<<endtime<<"s"<<endl; //s為單位cout<<"Total time:"<<endtime*1000<<"ms"<<endl; //ms為單位#endif //testreturn 0;
}最后記錄一下《算法筆記》書練習的 AC 代碼：codeup/13.2樹狀數組 at master · maximusyoung007/codeup · GitHub
)
