前言

T1没做出来的一集。。。

时间安排及成绩

• 7:40 开题
• 7:40 - 7:45 T1看懂了，感觉像广搜，但是复杂度好像不对。又好像是背包，但是物品的体积和权值好像会算错。不是很会。看了一眼T2，好像是线段树分治的板子？？
• 7:45 - 8:00 T1还是不咋会，果断开T2。发现这题好像也不是线段树分治。想到答案肯定满足单调性，于是可以二分。但是不能对所有询问都二分，因此可以整体二分？？中间也想过kruskal重构树，但感觉不太行。没想太多，感觉整体二分加上按秩合并并查集应该就行。直接开写。
• 8:00 - 8:20 想了一会儿按秩合并并查集，然后写到一般发现我不会就算维护了点的连通性也没法 $O(1)$ 判断一段区间是否联通！！！这。。。感觉好难啊。
• 8:20 - 8:40 冷静思考，发现我们可以求出每个点和它前一个点最早的联通时间，那么一段区间联通的答案就是区间最大值。
• 8:40 - 9:00 改完了，调了调，把样例都过了。感觉没啥问题，于是直接扔了。
• 9:00 - 9:10 回去看T1，感觉还是没啥清晰的思路。直接开T3！！
• 9:10 - 9:20 T2看懂了，发现明显具有单调性，可以直接二分答案 + 线段树合并。时间复杂度应该是 $nlo{g}^{2}n$，感觉可过就直接开写。
• 9:20 - 10:10 写完了，但是样例答案是负数？？回去重看了一遍题发现确实说明了答案有可能是负数。把二分的边界改一下就把所有样例过了？？但是这个大样例跑的有点慢啊。
• 10:10 - 10:40 放到oj上测试一下，发现确实过不去，会TLE。考虑一下卡常。最开始想的是不二分，直接用一个指针，然后每次检验。指针只会单减因此复杂度不会炸？？但是被我构个菊花直接卡炸了。然后就想到可以对每个点分别二分求出答案，最后答案就是所有点的最小值。然后每个点二分时右边界可以根据其它点的答案缩小。也算卡常吧。
• 10:40 - 11:10 改完了，大样例跑的飞快。检查一下，感觉没啥问题直接扔了。
• 11:10 - 11:15 5min把T4看了，然后5min写了个40分跑路。回去看T1
• 11:15 - 11:30 自认为想到一个很对的思路，但是写起来又感觉不会了。果断写暴力。
• 11:30 - 11:55 暴力好难写，写完后编译。CE？？！！感觉没问题啊。
• 11:55 - 12:00 最后都没看出来啥问题，交了个CE的程序。

估分：0 + 100 + 100 + 40 = 240
得分：0 + 100 + 100 + 40 = 240
rk6

T3赛后卡双log好像没卡掉我。。

题解

A. 倒水（bfs + dp）

分析：

感觉是很好的一道题。

题意已经很清楚了，就不赘述了。

首先直接搜索需要纪录四个状态 桶里的水量和三个杯子中的水量。状态数是 $10^5\times 100^3$ 的，显然过不去。我们想要减少状态数。

又不难发现实际上这个问题好像可以对应成背包问题：水量看作体积，操作数是代价。但是 被子倒满水后要不要倒掉 显然就成了一个问题。我们想让最后不用的那一次不倒，其他用的时候需要倒掉。这似乎没法在dp里体现。

正解是有一条性质：设操作(5) 为使用若干次操作(1)，(2)，(4)，然后让被子中有一些水量。那么最优方案一定是进行若干次操作 (5)，每个操作(5)后将所有有水的杯子中的水都倒入桶中。最后进行一次操作(5)，但是可以将部分水倒入桶中。

这个打表证明是对的。但是我们也可以感性理解一下：对于一个杯子里的水而言，如果它不倒入桶中，并且以后还要使用，那么一定会在下次往里倒水前将里面的水倒掉。由于它里面的水不会倒入桶中，又因为交换操作对于操作数没有影响。因此我们可以把这个杯子中的水被倒掉的操作移到前面，形成 除了要往桶中倒水的杯子，其他杯子都是空的状态。并且这个状态不会影响最优性。如果这个杯子以后不使用了，那么可以看作使用最后一次操作(5)后只将部分水倒入桶中的状态。

那么就可以 $bfs$ $O(100^3)$ 搜出所有状态，然后计算出 $cos{t}_1$ 和 $cos{t}_2$ 数组。接着用 $cos{t}_1$ 和 $cos{t}_2$ 转移 $dp$ 即可。

复杂度 $O(300\times n)$

CODE：

#include<bits/stdc++.h>
using namespace std;
typedef pair< int, int > PII;
const int N = 105;
const int M = 1e5 + 10;
int n, num[4], dis[N][N][N];
int cost1[N * 3], cost2[N * 3]; // 全部到入，部分倒入 
int dp[M], f[M];
bool vis[N][N][N];
struct state {int x, y, z; // 三杯水的质量分别为 x, y, z 
};
queue< state > qq;
PII pour(int x, int y, int lx, int ly) {return make_pair(x - min(x, ly - y), y + min(x, ly - y));
}
void ins(int x, int y, int z) {cost1[x + y + z] = min(cost1[x + y + z], dis[x][y][z] + (x > 0) + (y > 0) + (z > 0));if(x > 0) cost2[x] = min(cost2[x], dis[x][y][z] + 1);if(y > 0) cost2[y] = min(cost2[y], dis[x][y][z] + 1);if(z > 0) cost2[z] = min(cost2[z], dis[x][y][z] + 1);if(x + y > 0) cost2[x + y] = min(cost2[x + y], dis[x][y][z] + 2);if(x + z > 0) cost2[x + z] = min(cost2[x + z], dis[x][y][z] + 2);if(y + z > 0) cost2[y + z] = min(cost2[y + z], dis[x][y][z] + 2);if(x + y + z > 0) cost2[x + y + z] = min(cost2[x + y + z], dis[x][y][z] + 3);
}
int main() {cin >> num[1] >> num[2] >> num[3] >> n;sort(num + 1, num + 3 + 1);memset(cost1, 0x3f, sizeof cost1);memset(cost2, 0x3f, sizeof cost2);memset(dis, 0x3f, sizeof dis);vis[0][0][0] = 1; qq.push((state) {0, 0, 0});dis[0][0][0] = 0;while(!qq.empty()) {state u = qq.front(); qq.pop();int x = u.x, y = u.y, z = u.z;ins(x, y, z); // 更新答案 if(!vis[num[1]][y][z]) { // 1操作 vis[num[1]][y][z] = 1;dis[num[1]][y][z] = dis[x][y][z] + 1;qq.push((state) {num[1], y, z});}if(!vis[x][num[2]][z]) {vis[x][num[2]][z] = 1;dis[x][num[2]][z] = dis[x][y][z] + 1;qq.push((state) {x, num[2], z});}if(!vis[x][y][num[3]]) {vis[x][y][num[3]] = 1;dis[x][y][num[3]] = dis[x][y][z] + 1;qq.push((state) {x, y, num[3]});}if(!vis[0][y][z]) { // 2操作 vis[0][y][z] = 1;dis[0][y][z] = dis[x][y][z] + 1;qq.push((state) {0, y, z});}if(!vis[x][0][z]) {vis[x][0][z] = 1;dis[x][0][z] = dis[x][y][z] + 1;qq.push((state) {x, 0, z});}if(!vis[x][y][0]) { vis[x][y][0] = 1;dis[x][y][0] = dis[x][y][z] + 1;qq.push((state) {x, y, 0});}PII g; int p, q;g = pour(x, y, num[1], num[2]); // x -> yp = g.first, q = g.second;if(!vis[p][q][z]) {vis[p][q][z] = 1;dis[p][q][z] = dis[x][y][z] + 1;qq.push((state) {p, q, z});}g = pour(y, x, num[2], num[1]); // y -> xp = g.first, q = g.second;if(!vis[q][p][z]) {vis[q][p][z] = 1;dis[q][p][z] = dis[x][y][z] + 1;qq.push((state) {q, p, z});}g = pour(x, z, num[1], num[3]); // x -> zp = g.first, q = g.second;if(!vis[p][y][q]) {vis[p][y][q] = 1;dis[p][y][q] = dis[x][y][z] + 1;qq.push((state) {p, y, q});}g = pour(z, x, num[3], num[1]); // z -> xp = g.first, q = g.second;if(!vis[q][y][p]) {vis[q][y][p] = 1;dis[q][y][p] = dis[x][y][z] + 1;qq.push((state) {q, y, p});}g = pour(y, z, num[2], num[3]); // y -> zp = g.first, q = g.second;if(!vis[x][p][q]) {vis[x][p][q] = 1;dis[x][p][q] = dis[x][y][z] + 1;qq.push((state) {x, p, q});}g = pour(z, y, num[3], num[2]); // z -> yp = g.first, q = g.second;if(!vis[x][q][p]) {vis[x][q][p] = 1;dis[x][q][p] = dis[x][y][z] + 1;qq.push((state) {x, q, p});}		}memset(dp, 0x3f, sizeof dp);memset(f, 0x3f, sizeof f);dp[0] = 0;for(int i = 0; i <= n; i ++ ) {f[i] = min(f[i], dp[i]);for(int j = 1; j <= num[1] + num[2] + num[3]; j ++ ) {if(i + j <= n) dp[i + j] = min(dp[i + j], dp[i] + cost1[j]);if(i + j <= n) f[i + j] = min(f[i + j], dp[i] + cost2[j]);}}for(int i = 1; i <= n; i ++ ) {if(f[i] > 20000000) printf("-1 ");else printf("%d ", f[i]);}return 0;
}
/*
20 5 15 10 13 13 7 19 2 22 3 17 8 15 11 9 17 4 22 2 19 6 17 9 11 15 6 20 4 21 4 19 7 13 13 8 18 6 21 3 21 5 15 11 10 16 8 19 5 23 3 17 9 12 14 10 17 7 23 2*/

B. 让他们连通（整体二分 + 按秩合并并查集 / kruskal重构树）

原题链接

分析：

$Sol1：$
一个关键想法是我们可以 只关心一个点 $i$ 和点 $i-1$最早的连通时间$t_i$即可。

那么对于区间 $[l,r]$ 而言，它最早的连通的时间就是 $ma{x}_{i=l+1}^r{t}_i$。

对于 $t_i$ 的求法，我们可以整体二分 + 可撤销并查集 即可。我们使用 按秩合并 并查集就行。

时间复杂度 $O(q\times lo{g}_{2}q\times lo{g}_{2}n)$。

$Sol2：$

考虑维护两个点的最早连通时间，也可以使用 Kruskal重构树。然后查询只需要求 $lca$ 即可。

时间复杂度 $O(n\times lo{g}_{2}n)$

下面的代码是第一种解法的代码。
CODE：

#include<bits/stdc++.h> // 只需求出每个点和它前面的点最早的联通时间 
using namespace std;
const int N = 2e5 + 10;
int n, m, qc, u[N], v[N], o;
int g[N], lt[N], rt[N], Link[N];
int mx[N][21];
struct Q {int l, r;
}q[N];
struct inform { // 合并信息 int x, y, hx, hy; // x 合到 y 上,  x原来的树高是 hx， y原来的树高是 hy 
};
int bin[N], h[N]; // 父亲, 树高 
stack< inform > s;
int Find(int x) {return x == bin[x] ? x : Find(bin[x]);
}
void Merge(int x, int y) { // 合并 x, y int f1 = Find(x), f2 = Find(y);if(f1 != f2) {if(h[f1] > h[f2]) swap(f1, f2);s.push((inform) {f1, f2, h[f1], h[f2]});o ++;bin[f1] = f2;if(h[f1] == h[f2]) h[f2] ++;}
}
void back(int cnt) { // 撤回 cnt 次 while(cnt --) {inform t = s.top(); s.pop();int x = t.x, y = t.y, hx = t.hx, hy = t.hy;bin[x] = x;h[x] = hx; h[y] = hy;}
}
void solve(int l, int r, int ql, int qr) {if(l == r) {Merge(u[l], v[l]); // 合并 for(int i = ql; i <= qr; i ++ ) Link[g[i]] = l;return ;}int mid = (l + r >> 1);o = 0;for(int i = l; i <= mid; i ++ ) {int U = u[i], V = v[i];Merge(U, V);}int lc = 0, rc = 0; for(int i = ql; i <= qr; i ++ ) {int p = g[i];if(Find(p - 1) == Find(p)) lt[++ lc] = p;else rt[++ rc] = p;}for(int i = 1; i <= lc; i ++ ) g[i + ql - 1] = lt[i];for(int i = 1; i <= rc; i ++ ) g[lc + ql + i - 1] = rt[i];back(o); // 撤回操作 solve(l, mid, ql, ql + lc - 1); // 左 solve(mid + 1, r, ql + lc, qr);// 右 
}
int query(int l, int r) {int k = log2(r - l + 1);return max(mx[l][k], mx[r - (1 << k) + 1][k]);
}
void build_st() {for(int i = 1; i <= n; i ++ ) mx[i][0] = Link[i];for(int i = 1; (1 << i) <= n; i ++ ) {for(int j = 1; j + (1 << i) - 1 <= n; j ++ ) {mx[j][i] = max(mx[j][i - 1], mx[j + (1 << (i - 1))][i - 1]);}}
}
int main() {scanf("%d%d%d", &n, &m, &qc);for(int i = 1; i <= n; i ++ ) bin[i] = i, h[i] = 1;for(int i = 1; i <= m; i ++ ) {scanf("%d%d", &u[i], &v[i]);}for(int i = 1; i <= qc; i ++ ) {scanf("%d%d", &q[i].l, &q[i].r);}for(int i = 1; i <= n; i ++ ) g[i] = i;solve(1, m, 1, n);build_st();for(int i = 1; i <= qc; i ++ ) {int ans;if(q[i].l == q[i].r) ans = 0;else ans = query(q[i].l + 1, q[i].r);printf("%d ", ans);}return 0;
}

C. 通信网络（线段树合并 + 二分）

分析：

题意：
给你一个 $n$ 个点的树，点有点权 $w_i$。若现在有一个数 $P$，那么对于一个点 $x$，它的负荷就是所有满足一下两个条件的简单路径条数：

1. $u，v$ 是路径的两个端点，并且满足 $w_u\le w_x+P$， $w_v\le w_x+P$。
2. $x$ 在路径 $u\to v$ 上。

现在想让所有点的负荷都小于 $K$，求最大的 $P$。

不难看出，$P$ 越大，每个点的负荷只会增大，不会减小。具有单调性，因此可以 二分答案。 我们考虑如何检验：

若给定一个$P$，那么每个点的负荷计算就很简单了。对于一个点 $x$，只需要能快速查询它的子树里小于等于 $w_x+P$ 的数的个数即可。那么可以做 线段树合并，并在 值域线段树 里二分。这样可以计算出端点都在 $x$ 子树里的路径个数。对于一个端点在子树里，一个端点在子树外的路径，显然可以拿所有小于等于 $w_x+P$ 的数的个数减去 $x$ 的子树里的个数，这样能算出来 $x$ 子树外能成为端点的点数，然后和子树里的相乘即可。这样时间复杂度就是 $O(n\times lo{g}_2^{2}w)$ 的。

我们发现这样过不去，还要卡一下常：
由于 $K$ 给定，因此可以对每个点求出满足条件的最大的 $P$，然后最终答案就是所有点的答案取 $min$。对每个点求这样的 $P$ 可以二分，这样时间复杂度也是 $O(n\times lo{g}_2^{2}w)$ 的。但是注意到每个点二分时右端点不必开满，可以令当前求出的答案的最小值作为端点。这样也是一个剪枝。这样做之后就跑的特别快了，最后没有被卡掉。

CODE：

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 3e5 + 10;
const int M = 3e6 + 10;
typedef long long LL;
int n, w[N], u, v;
int pre[M], tot, rt[N];
int ans[N], res = 1e8, now;
vector< int > E[N];
LL k;
struct SegmentTree {int ls, rs, cnt;#define ls(x) t[x].ls#define rs(x) t[x].rs#define cnt(x) t[x].cnt
}t[N * 25];
void update(int p) {cnt(p) = cnt(ls(p)) + cnt(rs(p));
}
void ins(int p, int lp, int rp, int pos) {if(lp == rp) {cnt(p) ++;return ;}int mid = (lp + rp >> 1);if(pos <= mid) {if(!ls(p)) ls(p) = ++ tot;ins(ls(p), lp, mid, pos);}else {if(!rs(p)) rs(p) = ++ tot;ins(rs(p), mid + 1, rp, pos);}update(p);
}
int query(int p, int lp, int rp, int pos) {if(lp == rp) return (lp == pos ? cnt(p) : 0);int mid = (lp + rp >> 1);if(pos <= mid) return query(ls(p), lp, mid, pos);else return cnt(ls(p)) + query(rs(p), mid + 1, rp, pos);
}
int Merge(int p, int q, int lp, int rp) {if(!p || !q) return (p ^ q);if(lp == rp) {cnt(p) += cnt(q);return p;}int mid = (lp + rp >> 1);ls(p) = Merge(ls(p), ls(q), lp, mid);rs(p) = Merge(rs(p), rs(q), mid + 1, rp);update(p);return p;
}
bool check(int x, int fa, int p) {int o = (p + w[x] >= w[x] ? 1 : 0); LL res = 0;for(auto v : E[x]) {if(v == fa) continue;int c = query(rt[v], 1, 2e6, p + w[x]);res += 1LL * o * c;o += c; }res += 1LL * o * ((p + w[x] >= 0 ? pre[w[x] + p] : 0) - o);return res < k;
}
void dfs(int x, int fa) { // x 作为中转站的答案 for(auto v : E[x]) {if(v == fa) continue;dfs(v, x);}int l = -1e6, r = now, mid, res = -1;while(l <= r) {mid = (l + r >> 1);if(check(x, fa, mid)) res = mid, l = mid + 1;else r = mid - 1;}ans[x] = res; now = res;for(auto v : E[x]) {if(v == fa) continue;rt[x] = Merge(rt[x], rt[v], 1, 2e6);}
}
void solve() { // 检验 p 是否合法   弄完再清空 for(int i = 1; i <= n; i ++ ) {rt[i] = ++ tot;ins(rt[i], 1, 2e6, w[i]);}dfs(1, 0);for(int i = 1; i <= n; i ++ ) {res = min(res, ans[i]);}
}
int main() {scanf("%d%lld", &n, &k);int maxw = 0;for(int i = 1; i <= n; i ++ ) {scanf("%d", &w[i]);pre[w[i]] ++;maxw = max(maxw, w[i]);}for(int i = 1; i < n; i ++ ) {scanf("%d%d", &u, &v);E[u].pb(v); E[v].pb(u);}for(int i = 1; i < M; i ++ ) pre[i] += pre[i - 1];now = 1e6; solve();printf("%d\n", res);return 0;
}

正解是单 $log$ 的。首先对于它没有使用线段树合并，而是 按照 $dfs$ 序由小到大建主席树。那么一个点的子树信息也可以在 $dfs$ 序列中的一段区间中查询。正解也是按照上面这种对每个点求最大的 $P$，然后所有点取 $min$ 得到答案。考虑如果二分答案然后用主席树检验，时间复杂度也是 $O(n\times lo{g}_2^{2}w)$ 的。然后它就是把所有区间都拿出来，一起在线段树上二分减去一个 $log$。具体写法没仔细看，但是大概思路就是这。

D. 3SUM（扫描线 + 线段树）

原题链接

分析：

题意说的很清楚了，不在赘述。

直接说正解吧：

我们对最大值在那一段进行分讨，然后答案取最优：

1. 最大值在中间一段。那么可以把中间一段往两边延伸，发现中间那段的答案不变，两边段的答案单调不增。因此这种情况下最优值就是 $[l,l]$，$[l+1,r-1]$， $[r,r]$ 的最大值之和。
2. 最大值在左边段。如果我们求出 $[l,r]$ 中最大值的最左边位置 $x$，那么第一段的右端点应该大于等于 $x$。我们考虑如果左段的右端点是 $rt$，那么要把 $[rt+1,r]$ 分成两端。如果右段的左端点为 $lt$，那么三段就是 $[l,rt]$， $[rt+1,lt-1]$， $[lt,r]$。不难发现，这时可以将左段向右延伸直到中间段的长度为 $1$。这样左段，右段的答案不变，中间段的答案只会变得更优。因此我们得出结论：对于最大值在左段的情况，中间段的长度一定为 $1$。因此如果中间段为 $[p,p]$，那么中间段和右段的答案就是 $h_p=a_p+ma{x}_{i=p+1}^r{a}_i$，我们需要维护 区间中 $h$ 的最小值。这个可以用 线段树 + 单调栈维护 维护。具体来讲，我们对 $r$ 扫描线，然后维护一个单调栈。如果 $a_r>a_{s_{top}}$，就将栈顶弹出。那么 $[s_{top-1},s_{top})$ 区间的 $h$ 值将会加上 $a_r-a_{s_{top}}$ 。特别的，由于每个数刚入栈时后边没有数，因此它的 $h$ 值是正无穷。那么每次对于第一个栈顶我们将它的 $h$ 值改为 $a_{s_{top}}+a_r$ 即可。然后对于所有右端点为当前 $r$ 的区间 $[l,r]$，我们在栈中二分出第一个大于 $l$ 的位置$pos$，这是 $[l,r]$ 区间里最靠左的最大值的位置。在线段树上查询 $[pos+1,r]$ 的最小值并加上 $a_{pos}$更新这个询问的答案即可。
3. 最大值在右边段。将序列和询问区间反转一下就能变成上一种情况。

时间复杂度 $O(n\times lo{g}_{2}n)$。

CODE：

#include<bits/stdc++.h> // 扫描线 + 线段树 + 单调栈 
#define pb push_back
#define MP make_pair 
using namespace std;
typedef pair< int, int > PII;
const int N = 3e5 + 10;
const int INF = 4e8;
int n, qc, a[N], ans[N], mx[N][21];
vector< PII > vec[N];
struct Q {int l, r, id;
}q[N];
void build_st() {for(int i = 1; i <= n; i ++ ) mx[i][0] = a[i];for(int i = 1; (1 << i) <= n; i ++ ) for(int j = 1; j + (1 << i) - 1 <= n; j ++ ) mx[j][i] = max(mx[j][i - 1], mx[j + (1 << (i - 1))][i - 1]);
}
int query(int l, int r) {int k = log2(r - l + 1);return max(mx[l][k], mx[r - (1 << k) + 1][k]);
}
struct SegmentTree {int l, r, mn, tag;#define l(x) t[x].l#define r(x) t[x].r#define mn(x) t[x].mn#define tag(x) t[x].tag
}t[N * 4];
void build(int p, int l, int r) {l(p) = l, r(p) = r;mn(p) = INF; tag(p) = 0;if(l == r) return ;int mid = (l + r >> 1);build(p << 1, l, mid); build(p << 1 | 1, mid + 1, r);
}
void update(int p) {mn(p) = min(mn(p << 1), mn(p << 1 | 1));
}
void spread(int p) {if(tag(p)) {tag(p << 1) += tag(p); tag(p << 1 | 1) += tag(p);mn(p << 1) += tag(p); mn(p << 1 | 1) += tag(p); tag(p) = 0;}
}
void change(int p, int l, int r, int c) {if(l <= l(p) && r >= r(p)) {mn(p) += c; tag(p) += c;return ;}spread(p);int mid = (l(p) + r(p) >> 1);if(l <= mid) change(p << 1, l, r, c);if(r > mid) change(p << 1 | 1, l, r, c);update(p);
}
void ins(int p, int pos, int c) {if(l(p) == r(p)) {mn(p) = c;return ;}int mid = (l(p) + r(p) >> 1);if(pos <= mid) ins(p << 1, pos, c);else ins(p << 1 | 1, pos, c);update(p);
}
int ask(int p, int l, int r) {if(l <= l(p) && r >= r(p)) return mn(p);spread(p);int mid = (l(p) + r(p) >> 1);if(r <= mid) return ask(p << 1, l, r);else if(l > mid) return ask(p << 1 | 1, l, r);else return min(ask(p << 1, l, r), ask(p << 1 | 1, l, r));
}
void solve() { // 对 r 扫描线 int stk[N], Top = 0; // 单调栈 for(int r = 1; r <= n; r ++ ) {if(r != 1) ins(1, r - 1, a[r - 1] + a[r]);// 先把 r - 1修改了 while(Top > 0 && a[r] > a[stk[Top]]) {int x = stk[Top]; Top --;int l = (Top == 0 ? 1 : stk[Top]);if(x - 1 >= l) change(1, l, x - 1, a[r] - a[x]);}stk[++ Top] = r;for(auto qy : vec[r]) {int l = qy.first, idx = qy.second;int p = lower_bound(stk + 1, stk + Top + 1, l) - (stk); // 第一个大于等于l的位置 int x = stk[p];if(x + 1 <= r) ans[idx] = min(ans[idx], a[x] + ask(1, x + 1, r));} }
}
int main() {scanf("%d%d", &n, &qc);for(int i = 1; i <= n; i ++ ) {scanf("%d", &a[i]);}for(int i = 1; i <= qc; i ++ ) {scanf("%d%d", &q[i].l, &q[i].r);q[i].id= i;}build_st();for(int i = 1; i <= qc; i ++ ) ans[i] = a[q[i].l] + a[q[i].r] + query(q[i].l + 1, q[i].r - 1);for(int i = 1; i <= qc; i ++ ) {vec[q[i].r].pb(MP(q[i].l, q[i].id));}build(1, 1, n);solve();reverse(a + 1, a + n + 1);for(int i = 1; i <= n; i ++ ) {vector< PII > tmp;swap(tmp, vec[i]);}for(int i = 1; i <= qc; i ++ ) {vec[n - q[i].l + 1].pb(MP(n - q[i].r + 1, q[i].id));}build(1, 1, n);solve();for(int i = 1; i <= qc; i ++ ) printf("%d\n", ans[i]);return 0;
}