求出每個位置左邊有幾個比它大,右邊有幾個比它小,然後乘法原理加起來就夠了。
大於小於什麼的用樹狀數組YY一下就出來了。
#include #include #include #include #include #include using namespace std; int n; int c[2000000]; struct node { int x; int id; }a[2000000]; bool cmp(node x,node y) { return x.x0) { sum+=c[n]; n=n-lowbit(n); } return sum; } void change(int i,int x) { while(i<=n) { c[i]=c[i]+x; i=i+lowbit(i); } } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i].x); a[i].id=i; } sort(a+1,a+1+n,cmp); for(int i=1;i<=n;i++) mp[a[i].id]=i; for(int i=1;i<=n;i++) { change(mp[i],1); ls[mp[i]]=Sum(mp[i])-1; lb[mp[i]]=i-ls[mp[i]]-1; } long long ans=0; // for(int i=1;i<=n;i++) // { // printf("%d ",lb[mp[i]]); // } // puts(""); // for(int i=1;i<=n;i++) // { // printf("%d ",ls[mp[i]]); // } for(int i=1;i<=n;i++) { rs[mp[i]]=(mp[i]-1-ls[mp[i]]); ans+=rs[mp[i]]*lb[mp[i]]; } cout<
C++標准模板庫與數據結構的學習 STL(Stand
界面如下
在OC函數或者objc_msgSend的入口處(第一行
1、發布C++實現的TCP網絡框架Khala,tcpkhal
二叉查找樹 _ 二叉排序樹 _ 二叉搜索樹_C++,二叉_c
/* * 程序的版權和版本聲明部分: