BIT LA 4329 Ping pong

ゝ一纸荒年。 2022-01-09 05:59 119阅读 0赞

[**题目传送门**][Link 1]

**题意:训练指南P197**

**分析:枚举裁判的位置,用树状数组来得知前面比它小的和大的以及后面比它小的和大的,然后O (n)累加小 \* 大 + 大 \* 小 就可以了**

#include <bits/stdc++.h>
    using namespace std;
    
    typedef long long ll;
    const int N = 1e5 + 5;
    const int M = 2e4 + 5;
    struct BIT	{
    	int c[N], sz;
    	void init(int n)	{
    		memset (c, 0, sizeof (c));
    		sz = n;
    	}
    	void updata(int i, int x)	{
    		while (i <= sz)	{
    			c[i] += x;	i += i & -i;
    		}
    	}
    	int query(int i)	{
    		int ret = 0;
    		while (i)	{
    			ret += c[i];	i -= i & -i;
    		}
    		return ret;
    	}
    }bit;
    int a[M], small[M][2], large[M][2];
    
    int main(void)	{
    	int T;	scanf ("%d", &T);
    	while (T--)	{
    		bit.init (100000);
    		int n;	scanf ("%d", &n);
    		for (int i=1; i<=n; ++i)	{
    			scanf ("%d", &a[i]);
    			small[i][0] = bit.query (a[i] - 1);
    			large[i][0] = i - 1 - small[i][0];
    			bit.updata (a[i], 1);
    		}
    		for (int i=1; i<=n; ++i)	{
    			small[i][1] = bit.query (a[i] - 1) - small[i][0];
    			large[i][1] = n - i - small[i][1];
    		}
    		ll ans = 0;
    		for (int i=1; i<=n; ++i)	{
    			ans += 1ll * small[i][0] * large[i][1];
    			ans += 1ll * large[i][0] * small[i][1];
    		}
    		printf ("%lld\n", ans);
    	}
    
    	return 0;
    }

转载于:https://www.cnblogs.com/Running-Time/p/5027390.html

[Link 1]: https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2330

发表评论取消回复

表情：

评论列表（有 0 条评论，119人围观）

还没有评论，来说两句吧...

相关阅读

相关 UVALive - 4329 树状数组

题意：一条大街上住着n个乒乓球爱好者，经常组织比赛。每个人都有一个技能值ai，每场比赛需要3个人：两名选手和一名裁判。规定裁判位置必须在两个选手的中间，而且技能值也必

约定不等于承诺〃/ 2024年02月17日 21:40/ 0 赞/ 28 阅读

相关 redisTemplate ping pong

楔子 > 自我学习笔记。 demo public String ping(){ return redisTempl

谁践踏了优雅/ 2023年02月27日 05:46/ 0 赞/ 26 阅读

相关 LA 3458——Bridge

题意：建设一座大桥，在桥上建若干个塔，塔高为H，相邻两塔间的距离不能超过D，桥长度为B，线的总长度为L，桥之间的绳索为对称抛物线，问建最少塔的时候的线索的最下端的离地高度y

今天药忘吃喽~/ 2022年09月25日 06:28/ 0 赞/ 170 阅读

相关 ping-pong

[【转】乒乓缓冲机制][Link 1] 乒乓缓冲机制在很多场合都有应用价值，将其抽象成某种通用化类库，使代码得以复用。那么首先就要抽象出此机制的抽象模型。

本是古典何须时尚/ 2022年07月29日 09:19/ 0 赞/ 40 阅读

相关 POJ 3928-Ping pong（树状数组+加/乘法原理）

Ping pong <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</t

雨点打透心脏的1/2处/ 2022年07月19日 01:50/ 0 赞/ 82 阅读

相关 UVALive 4329 Ping pong, beijing 2008

题目链接:[ ][Link 1] [https://vjudge.net/contest/157087\problem/A][Link 1] [https://vjud

旧城等待，/ 2022年06月18日 09:29/ 0 赞/ 66 阅读

相关 la查数据

$result=TiezeDetail::where('uid',$userLoginStatus->uid)->where('parent',0)->orderBy(

朱雀/ 2022年05月28日 02:08/ 0 赞/ 205 阅读

相关 LB和LA

观点1： 1. ha lb 软件的优点与缺点？两个本来就不是一路的，应该不好比较优缺点。从目的上来说： ha的目的是不中断服务，lb的目的是为了提高接入能力，

怼烎@/ 2022年03月11日 06:48/ 0 赞/ 253 阅读

相关 BIT LA 4329 Ping pong

[题目传送门][Link 1] 题意:训练指南P197 分析:枚举裁判的位置,用树状数组来得知前面比它小的和大的以及后面比它小的和大的,然后O (n)累加小 \ 大 + 大

ゝ一纸荒年。/ 2022年01月09日 05:59/ 0 赞/ 120 阅读

相关 LA4329 Ping pong 乒乓比赛（树状数组与组合原理）

题意：一条大街上住着n个乒乓球爱好者，经常组织比赛切磋技术。每个人都有一个能力值a\[i\]。每场比赛需要三个人：两名选手，一名裁判。他们有个奇怪的约定，裁判必须住在两

小咪咪/ 2021年12月11日 13:03/ 0 赞/ 145 阅读