---
# System prepended metadata

title: 第K小區間和
tags: [Question tutorial]

---

---
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';
}
```
:::
