---
tags: Question tutorial
---
# 第K小區間和
## **注意!!作法二比較好**
- 改成第K大區間和
- 注意到前綴和、後綴和為遞增
- 把`lower_bound` 改成線性
## 先備知識
一個長度為$N$的值陣列會有$\frac{N(N + 1)}{2}$ 個區間和
## NA20%
就窮舉
## NA80%
任一個區間都可以被表示為$\implies$ `總和 - (前綴和 + 後綴和)`
因為`總和`為定值所以若有一個長為$N$的區間，其區間和為第$K$小，則其`前綴和 + 後綴和`為第$\frac{N * (N + 1)}{2} - K + 1 大 \implies 令他為第T大問題$
那要如何找到第$T$大的`前綴和 + 後綴和`呢？
```cpp=
K = (N * (N + 1) / 2) - K + 1;
```
| 2 | 4 | 3 | 3 |
| -------- | -------- | -------- | ------ |
**p_f(前綴和)**
| 0 | 2 | 6 | 9 | 12 |
| -------- | -------- | -------- | ------ | ------ |
**p_b(後綴和)**
| 0 | 3 | 6 | 10 | 12 |
| --- | --- | --- | --- | --- |
### 想法
想不到如何找 $\implies$ 簡化題目。
- 若`前綴和 + 後綴和`為`m`，那他會比幾個區間和大? $\quad(0 \leq m \leq sum)$
- 他比`T`個區間和大，那這些區間中**最大**的是否為第`T`大?
- 那這樣是不是可以對`m`二分搜求出第`T`大?
這邊放程式碼，想一想為什麼正確
**<center>找出比`m`的值小的區間和總數。</center>**
```cpp=
#define V vector
#define ALL(x) x.begin(), x.end()
void find(V<ll> &p_f, V<ll> &p_b, ll m) {
ans = 0, mx = -1;
for(int i = 0; i <= N; i++) {
if(m < p_f[i]) return;
ll x = m - p_f[i];
auto p = lower_bound(ALL(p_b), x);
p--;
ans += p - p_b.begin() + 1;
if(*p + p_f[i] > mx) mx = *p + p_f[i];
}
}
```
**<center>對`m`做二分搜</center>**
```cpp=
while(1) {
ll m = (l + r) >> 1;
find(p_f, p_b, m);
if(ans == K || r == l) {
cout << sum - mx << endl;
return;
}
if(ans < K)
l = m + 1;
else
r = m;
}
```
時間複雜度為$O(\lg sum \times N\lg N)$
## AC
發現在$N$長度為$10^6$時，$sum$的值約為$2^{32}$，上面的時間複雜度 $\approx 2 * 10^8$，會$TLE$
觀察一下`find`函式裡面找的過程。
可以發現，`p - p_b.begin() + 1` 的值只會越來越小 $\implies p_f[i]的值越來越大$。
所以可以不用每次都接著二分搜，接下去找就好!!
神奇的事情發生了~
因為是接著下去找，所以`find`函式最多只會把`p_f`, `p_b`都遍歷過一遍 $\implies$ `find`時間複雜度達到$O(N)!!!$
**<center>改良版`find`函數</center>**
```cpp=
void find(V<ll> &p_f, V<ll> &p_b, ll m) {
ans = 0, mx = -1;
int cur_pos = N;
for(int i = 0; i <= N; i++) {
if(m < p_f[i]) return;
ll x = m - p_f[i];
while(p_b[cur_pos] >= x) cur_pos--;
ans += cur_pos + 1;
if(p_b[cur_pos] + p_f[i] > mx) mx = p_b[cur_pos] + p_f[i];
}
}
```
時間複雜度為$(\lg sum \times N)$
# 作法二（ 前綴和 ）
## 性質
- $sum[l, r] = sum[1, r]-sum[1,l-1]$
- 前綴和遞增
## 觀察
**M具有單調性**
可以發現，如果要找到一個大於等於$M$(他是一個數字）的區間和的個數。
在$M$遞增的情況下它也會遞增，所以它具有單調性
**前綴和有單調性**
對於一個前綴合$X$($sum[1,r]$)，如果想要讓區間和大於$M$，可以發現，符合的條件($sum[1,r]-sum[1,l-1] \geq M$)，其中的$l$必定會出現在前面。
**轉換**
$(區間和 \leq M) = (全部可能性) - (區間和 > M)$
## 作法(NA80%)
因為$M$有單調性，我們不妨先對它做二分搜。
:::success
為什麼可以做二分搜，可以思考一下。
如果對區間和做排序的話，可以發現$M$其實就是在$\frac{N(N+1)}{2}$的區間上做二分搜，若$M$越大，獲得的區間個數也會越大。
所以其實我們獲得$M$之後動態的計算個數。
:::
所以我們可以對$M$做二分搜，然後計算有幾個區間和比它大。
複雜度$O(logC \times N lg N)$
## 優化
可以發現二分搜的時候，界線其實是一直遞增的，所以用一個雙指針維護就好了
:::spoiler code `郭勝威`
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define ALL(x) begin(x), end(x)
#define iter(x, sz) (x), (x)+sz
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
constexpr int mxN = 1e5 + 20;
int main () { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int N;
ll K;
cin >> N >> K;
--K;
auto cint = [](int &a) {cin >> a;};
vector< int > vc(N);
for_each( ALL(vc), cint );
ll l = 0, r = 1e15;
while( r-l > 1 ) {
ll m = (r+l)>>1;
ll lsum = 0, rsum = 0;
int l_pos = 0, r_pos = 0;
ll cnt = 0;
for_each(ALL(vc),
[&] (int &a ) {
rsum += a;
while( rsum - lsum >= m ) {
lsum += vc[l_pos];
++l_pos;
}
cnt += (r_pos - l_pos+1);
r_pos++;
}
);
if( cnt > K ) r = m;
else l = m;
}
cout << l << '\n';
}
```
:::
:::spoiler code `劉冠甫`
```cpp=
#include<iostream>
#include<vector>
using namespace std;
#define ll long long
int main(){
cin.tie(0) -> sync_with_stdio(0);
ll n, k; cin >> n >> k;
ll v[n + 1];
v[0] = 0;
for (int i = 1; i <= n; i ++){
int p; cin >> p;
v[i] = v[i - 1] + p;
}
ll l = 0, r = 1e16;
while (r - l > 1){
ll m = (r + l) >> 1;
ll cnt = 0;
int fi = 1, si = 0;
for (; fi <= n; fi ++){
while (v[fi] - v[si] >= m){
si ++;
}
cnt += fi - si;
}
if (cnt >= k) r = m;
else l = m;
}
ll cnt = 0;
int fi = 1, si = 0;
for (; fi <= n; fi ++){
while (v[fi] - v[si] > l){
si ++;
}
cnt += fi - si;
}
if (cnt < k - 1) l = r;
cout << l << '\n';
}
```
:::
Sign in with Wallet
Connect another wallet