转载自：http://blog.csdn.net/queuelovestack/article/details/52096337
【题意】
给你一个序列A,选出四个下标不同的元素,下标记为a,b,c,d
a≠b≠c≠d,1≤a<b≤n,1≤c<d≤n
满足Aa<Ab,Ac>Ad
问能找到多少个这样的四元组(a,b,c,d)
【类型】
树状数组应用
【分析】
因为a<b,c<d,Aa<Ab,Ac>Ad
所以我们暂时称(a,b)为递增对,(c,d)为递减对
题目就转化成递增对*递减对-重复对
重复对包括如下四种:
①b,c一致
②a,c一致
③b,d一致
④a,d一致
那么我们该如何计算重复对呢?
考虑一致点下标为i,我们需要事先处理出位置i左边比它大的数的个数w[i],比它小的数的个数l[i];右边比它大的数的个数v[i],比它小的数的个数r[i],这样所有重复对的对数为l[i]*r[i]+l[i]*v[i]+w[i]*r[i]+w[i]*v[i]
而计算这些个数可以通过树状数组求解
【时间复杂度&&优化】
O(nlogn)
题目链接→HDU 5792 World is Exploding
感觉他写的真的很好，看完之后就大致可以懂了，但树状数组求的那块太简略，我补充下：
首先要做的是把输入s[i]离散化，因为题目说的是1e9。离散化之后就是每次检查前n项和，求l w数组，同理，更新v r数组，但注意，每次都要初始化c数组，因为c数组代表的就是第几位出现的次数，这两次相求会影响，所以每次都跟新。
这题还说明一个问题：树状数组和离散化合到一起有很大作用，比如这题，他就能求出递增对个数，利用的就是当求i的递增对个数时，求0~i-1中所有出现次数之和。
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int INF=0x3f3f3f3f; const ll LINF=0x3f3f3f3f3f3f3f3f; #define PI(A) cout<<(A)<<endl #define SI(N) cin>>(N) #define SII(N,M) cin>>(N)>>(M) #define cle(a,val) memset(a,(val),sizeof(a)) #define rep(i,b) for(int i=0;i<(b);i++) #define Rep(i,a,b) for(int i=(a);i<=(b);i++) #define reRep(i,a,b) for(int i=(a);i>=(b);i--) #define dbg(x) cout <<#x<<" = "<<(x)<<endl #define PIar(a,n) rep(i,n)cout<<a[i]<<" ";cout<<endl; #define PIarr(a,n,m) rep(aa,n){rep(bb, m)cout<<a[aa][bb]<<" ";cout<<endl;} const double EPS= 1e-9 ; /* ///////////////////////// C o d i n g S p a c e ///////////////////////// */ const int MAXN= 50000 + 9 ; int n,s[MAXN],c[MAXN],a[MAXN]; ll l[MAXN],r[MAXN],w[MAXN],v[MAXN]; //树状数组 int lowbit(int t){return t&(-t);} //在c[i]上加x void add(int i,int x) { while(i<=n) { c[i]+=x; i+=lowbit(i); } } //求c[]的前n项和 int sum(int n) { int s=0; while(n>0) { s+=c[n]; n-=lowbit(n); } return s; } int main() { while(SI(n)) { int k,Max=0; //su1是递增对个数 su2是递减对个数 ll ans=0,su1=0,su2=0; //输入 rep(i,n) {SI(s[i]);a[i]=s[i];} //将s[]离散化 sort(a,a+n); k=unique(a,a+n)-a; rep(i,n) { s[i]=lower_bound(a,a+k,s[i])-a+1; Max=max(Max,s[i]); } //求递增对个数 和l w数组 cle(c,0); rep(i,n) { l[i]=sum(s[i]-1); w[i]=sum(Max)-sum(s[i]); add(s[i],1); su1+=l[i]; } //求递减对个数 和r v数组 cle(c,0); reRep(i,n-1,0) { r[i]=sum(s[i]-1); v[i]=sum(Max)-sum(s[i]); add(s[i],1); su2+=r[i]; } ans=su1*su2; //减去重复的 rep(i,n) ans-=l[i]*r[i]+l[i]*w[i]+v[i]*r[i]+v[i]*w[i]; PI(ans); } return 0; }