Ping pong
?UVALive - 4329?
題目傳送門
題目大意：一條大街上住著n個乒乓球愛好者，經常組織比賽切磋技術。每個人都有一個不同的技能值ai。每場比賽需要三個人：兩名選手，一名裁判。他們有一個奇怪的規定，即裁判必須住在兩名選手的中間，并且技能值也在兩名選手之間。問一共能組織多少場比賽。輸入第一行表示共有T組測試數據，每組數據占一行，先輸入整數n(3<=n<=20000)，后面跟著輸入n個不同的整數，即a1,a2,a3...an(1<=ai<=100000)，按照從左到右的順序給出每個乒乓球愛好者的技能值。
解決方法：樹狀數組解決，考慮第i個人當裁判的情況。假設a1到ai-1中有ci個比ai小，那么就有(i-1)-ci個比ai大；同理，假設a(i+1)到an中有di個比ai小，則其中就有n-i-di個比其大，所以以ai為裁判的比賽場數為：ci*(n-i-di)+di*(i-1-ci)，因此先用樹狀數組求每個數前面比其小的數字的數目，再反向求其后面比它小的數目，即可得到答案。
AC代碼：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <set>
#include <utility>
#include <sstream>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define inf 0x3f3f3f3f
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define lep(i,l,r) for(int i=l;i>=r;i--)
#define ms(arr) memset(arr,0,sizeof(arr))
//priority_queue<int,vector<int> ,greater<int> >q;
const int maxn = (int)1e6 + 5;
const ll mod = 1e9+7;
int C1[maxn];
int C2[maxn];
int arr[maxn]; //存技能值
int sum11[maxn]; //存的每個數前面的比其小的數目
int sum22[maxn]; //存的每個數后面比其小的數目
int n;
int lowbit(int x)
{return x&(-x);
}
void add1(int x,int d)
{while(x<=100000){C1[x]+=d;x+=lowbit(x);}
}
int sum1(int x)
{int ret=0;while(x>0){ret+=C1[x];x-=lowbit(x);}return ret;
}
void add2(int x,int d)
{while(x<=100000){C2[x]+=d;x+=lowbit(x);}
}
int sum2(int x)
{int ret=0;while(x>0){ret+=C2[x];x-=lowbit(x);}return ret;
}
int main()
{#ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);#endif//freopen("out.txt", "w", stdout);ios::sync_with_stdio(0),cin.tie(0);int T;cin>>T;while(T--){ms(C1);ms(C2);ms(arr);ms(sum11);ms(sum22);cin>>n;rep(i,1,n) {cin>>arr[i];add1(arr[i],1);sum11[i]=sum1(arr[i]-1);}lep(i,n,1) {add2(arr[i],1);sum22[i]=sum2(arr[i]-1);}ll ans=0;rep(i,1,n) {ll c1=sum11[i];ll d1=sum22[i];ans+=c1*(n-i-d1)+d1*(i-1-c1);}cout<<ans<<endl;}return 0;
}
?
)
