题目，要求找出有多少对这样的东西，四个数，并且满足num[a]<num[b] &&num[c]>num[d]
要做这题，首先要懂得用树状数组，我设，下面的小于和大于都是严格的小于和大于
dpL_min[i]:表示在第i个数往左，（不包括第i个），有多少个数是少于num[i]的
dpL_max[i]:表示在第i个数往左，（不包括第i个），有多少个数是大于num[i]的
dpR_min[i]:表示在第i个数往右，（不包括第i个），有多少个数是小于num[i]的
dpR_max[i]:表示在第i个数往右，（不包括第i个），有多少个数是大于num[i]的
首先我们能预处理出所有的sumab对数，表示在1--n中有多少对这样的ab对。
sumcd同理。然后默认的ans=sumab*sumcd了
但是有重复的呀。有四种情况是重复的，就是a==d || a==c || b==c || a==c
那么，我们枚举每一个i，表示当前是a==d=num[i]，就是把a和d现在相同，且数字是num[i]，那么要减去的值就是dpR_max[i]*dpL_max[i]; dpR_max[i]表示有多少个数能和num[a]组合，变成num[a]<num[b]的对数。同理dpL_max[i]
再来一个例子吧.。假如现在是a==c=num[i]，那么ans -= dpR_max[i] * dpR_min[i]; dpR_max[i] 表示有多少个数能和num[a]组合，变成num[a]<num[b]的对数。dpR_min[i]表示有多少个数能和num[c]结合，变成num[c]>num[d]这样的对数。
这里和网上说的枚举i作为d值是不同的哦，网上的解释我感觉上是说不通的。反正我是想不明白。我这里的枚举每个i，作为他们相同的数子。
有没可能是a==c && b==d呢？可能的，矛盾了。
这里要注意的还有数字是严格大于，在离散的时候注意一下就可以了
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> int n; const int maxn = 50000 + 20; struct data { int val,pos; }book[maxn]; int a[maxn]; int c[maxn];//树状数组 int lowbit (int x)//得到x二进制末尾0的个数的2次方 2^num { return x&(-x); } void add (int pos,int val)//在第pos位加上val这个值 { while (pos<=n) //n是元素的个数 { c[pos] += val; pos += lowbit(pos); } return ; } int get_sum (int pos) //求解：1--pos的总和 { int ans = 0; while (pos) { ans += c[pos]; pos -= lowbit(pos); } return ans; } bool cmp (struct data a,struct data b) { return a.val < b.val; } int dpL_min[maxn]; int dpL_max[maxn]; int dpR_min[maxn]; int dpR_max[maxn]; void init () { memset(c,0,sizeof c); memset(dpR_max,0,sizeof dpR_max); memset(dpR_min,0,sizeof dpR_min); memset(dpL_max,0,sizeof dpL_max); memset(dpL_min,0,sizeof dpL_min); } void work () { init(); for (int i=1;i<=n;++i) { scanf("%d",&book[i].val); book[i].pos = i; } sort(book+1,book+1+n,cmp); for (int i=1;i<=n;++i) { if (i>=2 && book[i].val == book[i-1].val) a[book[i].pos] = a[book[i-1].pos]; else a[book[i].pos]=i; //从小到大离散 } for (int i=1;i<=n;++i) { dpL_min[i] = get_sum(a[i]-1); dpL_max[i] = get_sum(n)-get_sum(a[i]); add(a[i],1); } memset(c,0,sizeof c); for (int i=n;i>=1;--i) { dpR_min[i] = get_sum(a[i]-1); dpR_max[i] = get_sum(n) - get_sum(a[i]); add(a[i],1); } LL sumab = 0; LL sumcd = 0; for (int i=1;i<=n;++i) sumab += dpL_min[i]; for (int i=1;i<=n;++i) sumcd += dpL_max[i]; LL ans = sumab * sumcd; for (int i=1;i<=n;++i) { ans -= dpL_max[i] * dpR_max[i]; //a==d ans -= dpL_max[i] * dpL_min[i]; // b==d ans -= dpR_max[i] * dpR_min[i]; // a==c; ans -= dpL_min[i] * dpR_min[i]; //c==b } printf ("%I64d ",ans); return ; } int main() { #ifdef local freopen("data.txt","r",stdin); #endif while(scanf("%d",&n)!=EOF && n) work(); return 0; }