題意：給出數組A，定義f(l,r,x)為A[]的下標l到r之間，等于x的元素數。i和j符合f(1,i,a[i])>f(j,n,a[j])，求有多少對這樣的(i,j).
解法：分別從左到右，由右到左預處理到某個下標為止有多少個數等于該下標，用map維護。
然后樹狀數組更新每個f(j,n,a[j])，預處理完畢，接下來，從左往右掃過去，每次從樹狀數組中刪去a[i]，因為i != j，i不能用作后面的統計，然后統計getsum(inc[a[i]]-1),
(inc表示從左到右)，即查詢比此時的a[i]小的f(j,n,a[j])個數。
代碼：
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <algorithm> #include <map> #define lll __int64 using namespace std; using namespace __gnu_cxx; #define N 1000007 #define M 22int c[N],a[N]; map<int,int> inc,des; int n;int lowbit(int x) {return x & (-x); }void modify(int x,int val) {while(x <= n){c[x] += val;x += lowbit(x);} }int getsum(int x) {int res = 0;while(x > 0){res += c[x];x -= lowbit(x);}return res; }int main() {int i;inc.clear();des.clear();memset(c,0,sizeof(c));scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d",&a[i]);for(i=n;i>=1;i--){des[a[i]]++;modify(des[a[i]],1);}lll ans = 0;for(i=1;i<=n;i++){inc[a[i]]++;modify(des[a[i]],-1);des[a[i]]--;ans += getsum(inc[a[i]]-1);}printf("%I64d\n",ans);return 0; }
?
