CF1677A Tokitsukaze and Strange Inequality 题解

题目
- 链接
- 字面描述
- - 题目描述
- 输入格式
- 输出格式
- 样例 #1
- - 样例输入 #1
  - 样例输出 #1
- 提示
思路点拨
- 暴力思想
- 经验借鉴
- 优化
- 复杂度分析
代码实现

题目

链接

https://www.luogu.com.cn/problem/CF1677A

字面描述

题目描述

给一个长度为

$n$ 的排列，求有多少个四元组

(

)

(a,b,c,d)

$(a, b, c, d)$ 满足

$a b c d 和$

$p_{a} p_{c}$ 、

p_b>p_d

$p_{b} > p_{d}$ 。

输入格式

第一行包含一个正整数

$t$ (

≤

1000

1 leq t leq 1000

$1 \leq t \leq 1000$ )——表示小测试点总数，每个小测试点包含

$2$ 行输入

第一行一个正整数

(

≤

5000

)

n(4 leq n leq 5000)

$n (4 \leq n \leq 5000)$ 表示

$p :$ {} 数组的长度

第二行包含

$n$ 个正整数

…

p_1, p_2, ldots, p_n

$p_{1}, p_{2}, \dots, p_{n}$ (

≤

1 leq p_i leq n

$1 \leq p_{i} \leq n$ ) — 表示数组

$p$ 内的元素 .

题目保证

∑

≤

5000

sum n leq 5000

$\sum n \leq 5000$

输出格式

对于每个小测试点输出一个非负整数表示合法四元组的数量

样例 #1

样例输入 #1

3
6
5 3 6 1 4 2
4
1 2 3 4
10
5 1 6 2 8 3 4 10 9 7

样例输出 #1

3
0
28

提示

对于第一组样例合法四元组

(

)

(p_a,p_b,p_c,p_d)

$(p_{a}, p_{b}, p_{c}, p_{d})$ 为

思路点拨

暴力思想

先不提优化，如果用最暴力的想法去解决这道题无非分别枚举

a,b,c,d

$a, b, c, d$ 的值，时间复杂度将达到

(

)

≈

6.25

⋅

Omicron(n^4) approx 6.25 cdot 10^{14}

$O (n^{4}) \approx 6.25 \cdot 1 0^{14}$
肯定 TLE

经验借鉴

这类题，借助李学长的优化思路
可将这类题归纳为借助题目性质+预处理优化

优化

∵

四元组满足

because 四元组满足p_a

p_d

$∵ 四元组满足 p_{a} p_{c} 且 p_{b} > p_{d}$

∴

therefore

$∴$ 枚举

b,c

$b, c$ 的范围，分别对

a,d

$a, d$ 提前进行前缀和和后缀和预处理
定义如下

$lessl_{i_j} lesslij表示 ∑ p k ∑pki(1≤k≤j)$
同理 $lessr_{i_j} lessrij表示 ∑ p k ∑pki(j≤k≤n)$

最后只需要枚举

b,c

$b, c$ 下标直接依靠乘法原理完成计算

复杂度分析

感谢题目

≤

1 leq p_i leq n

$1 \leq p_{i} \leq n$ 方便处理

less

$l ess$ {}
空间复杂度:

(

)

Omicron(n^2)

$O (n^{2})$
时间复杂度:

(

)

Omicron(n^2)

$O (n^{2})$

预处理时间复杂度: $Omicron(n^2) O(n2)$
计算时间复杂度: $Omicron(n^2) O(n2)$

记得最后只要

a

n

s

ans

$an s$ 开

l

o

n

g

l

o

n

g

long long

$l o n g l o n g$
不开

$W A$
全开

MLE

$M L E$
只开

$A C$

代码实现

#include
#define ll long long
using namespace std;

const int maxn=5e3+10;
int t,n;
ll ans;
int a[maxn];
int lessl[maxn][maxn],lessr[maxn][maxn];
//预处理
inline void init(){
	for(int i=1;in;i++){
		for(int j=1;jn;j++){
			lessl[i][j]=lessl[i][j-1];
			if(a[j]i)++lessl[i][j];
		}
	}
	for(int i=1;in;i++){
		for(int j=n;j>=1;j--){
			if(j!=n)lessr[i][j]=lessr[i][j+1];
			else lessr[i][j]=0;
			if(a[j]i)++lessr[i][j];
		}
	}
}
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		for(int i=1;in;i++)scanf("%d",&a[i]);
		init();
		ans=0;
		//计算
		for(int i=2;in-2;i++){
			for(int j=i+1;jn-1;j++)ans=(ll)ans+lessl[a[j]][i-1]*lessr[a[i]][j+1];
		}
		printf("%lldn",ans);
	}
	return 0;
}

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net

相关推荐: 小结REDHAT5+11G R2+ASM+ISCSI(OPENFILER)布署【补充中】

一.下载相关的包数据库：第1和第2个压缩包集群：第3个压缩包 iscsi:openfiler2.3 asmlib相关(3个） redhat5.5(x86_64) 平台ESX5(虚拟机上布署) Network Configuration Node Name …

CF1677A Tokitsukaze and Strange Inequality 题解题目思路点拨代码实现