求巨佬计算时间复杂度

问题讨论区 基础段
1 
for(int i=1;i<n;i++) cnt[i]=cnt[i-1]+(a[i]>a[i+1]),cnt2+=(a[i]>a[i+1]);
for(int r=3;r<=n;r++){
	for(int l=r-2;l>=1;l--){
		int t=cnt[r-1]-cnt[l-1];
		if(t==1) cnt2+=(a[r]<a[l]);
		if(t>1) break;
	}
}

这份代码过了 1e7。

2

<O(n^2)

被卡到极限就应该是 O(n \sum_{1}^{n-2})

3

@张乐凡 这份代码的复杂度不算初始化的话一定是小于 O(\frac{(n-1)(n+1)(2n-5)}{6}) 的

4

不是啊 O(n^2) 当然小于 O(n^3) 啊

5

关键是这份代码能过 1e7！

6

@张乐凡 数据水

7

n 的范围是多少

8

这是基础赛

9

@张乐凡 你中间还有一个break呀省掉很多时间

10

多测， 1\le T\le10^5,1\le n \le 5\times 10^6,\sum n\le 10^7

11

那就是数据水（特判发力了

12

@张乐凡 对不起刚刚算错了我重新算一下

13

@张乐凡 你的代码复杂度小于 O(\frac{n^2-3n+2}{2})

14

这代码轻松卡啊

1
5000000
1 2 3 4 5 6 7 8 9（后略）
15

这数据水得没谁了，这是基础赛啊

16

@张乐凡 你反馈吧

17

找谁啊，我没加洛谷群，私信被禁了，讨论区关了

18

这代码甚至最优解第三页

19

轻松卡

20

@王钰宸涵 你在赛时答疑帖发一下这个链接：
https://www.luogu.com.cn/record/204308129

1 个赞