CF1692G题解

题目链接（CF，洛谷） | 强烈推荐博客中观看。打的第一场 CF div.4这个题就是那种想到点了就很很简单，没想到的话就……寄了的题（我就属于是寄了）。1. 题意：给你一个长度为 n (∑n<2⋅105)n \ (\sum n < 2\cdot 10^5)n (∑n<2⋅105) 的数组 aaa，问你在这个数组中，有多少个长度为 k+1 (1≤k<n)k + 1 \ (1\le k < n)k+1 (1≤k<n) 的区间，符合以下的条件：20⋅ai<21⋅ai+1<22⋅ai+2< ⁣⋯<2k⋅ai+k注：i为这个区间开始的位置2^0 \cdot a_i < 2^1 \cdot a_{i + 1} < 2^2 \cdot a_{i + 2} < \dotsi < 2^k \cdot a_{i + k}\\\footnotesize{注：i 为这个区间开始的位置}20⋅ai​<21⋅ai+1​<22⋅ai+2​<⋯<2k⋅ai+k​注：i为这个区间开始的位置2. 思路暴力还是很好搞的，就把数组中每个可能的区间都算一遍就行了，但是看到 ∑n<2⋅105\sum n < 2\cdot 10...

Submit