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; }

?

總結

以上是生活随笔為你收集整理的Ping pong【树状数组】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。