广西网站建设设计,北京手机软件开发公司,深圳做网站网络公司排名,网站建设 分析Ping pong UVALive - 4329
题目传送门
题目大意#xff1a;一条大街上住着n个乒乓球爱好者#xff0c;经常组织比赛切磋技术。每个人都有一个不同的技能值ai。每场比赛需要三个人#xff1a;两名选手#xff0c;一名裁判。他们有一个奇怪的规定#xff0c;即裁判必须住…Ping pong UVALive - 4329
题目传送门
题目大意一条大街上住着n个乒乓球爱好者经常组织比赛切磋技术。每个人都有一个不同的技能值ai。每场比赛需要三个人两名选手一名裁判。他们有一个奇怪的规定即裁判必须住在两名选手的中间并且技能值也在两名选手之间。问一共能组织多少场比赛。输入第一行表示共有T组测试数据每组数据占一行先输入整数n(3n20000)后面跟着输入n个不同的整数即a1,a2,a3...an(1ai100000)按照从左到右的顺序给出每个乒乓球爱好者的技能值。
解决方法树状数组解决考虑第i个人当裁判的情况。假设a1到ai-1中有ci个比ai小那么就有(i-1)-ci个比ai大同理假设a(i1)到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 il;ir;i)
#define lep(i,l,r) for(int il;ir;i--)
#define ms(arr) memset(arr,0,sizeof(arr))
//priority_queueint,vectorint ,greaterint q;
const int maxn (int)1e6 5;
const ll mod 1e97;
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(x100000){C1[x]d;xlowbit(x);}
}
int sum1(int x)
{int ret0;while(x0){retC1[x];x-lowbit(x);}return ret;
}
void add2(int x,int d)
{while(x100000){C2[x]d;xlowbit(x);}
}
int sum2(int x)
{int ret0;while(x0){retC2[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;cinT;while(T--){ms(C1);ms(C2);ms(arr);ms(sum11);ms(sum22);cinn;rep(i,1,n) {cinarr[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 ans0;rep(i,1,n) {ll c1sum11[i];ll d1sum22[i];ansc1*(n-i-d1)d1*(i-1-c1);}coutansendl;}return 0;
}
