专业建站公司的业务内容,宜城建设局网站,广告设计公司前台,wordpress中page与post文章目录 前言时间安排及成绩题解A. 倒水#xff08;bfs dp#xff09;B. 让他们连通#xff08;整体二分 按秩合并并查集 / kruskal重构树#xff09;C. 通信网络#xff08;线段树合并 二分#xff09;D. 3SUM#xff08;扫描线 线段树#xff09; 前言
T1没做出… 文章目录 前言时间安排及成绩题解A. 倒水bfs dpB. 让他们连通整体二分 按秩合并并查集 / kruskal重构树C. 通信网络线段树合并 二分D. 3SUM扫描线 线段树 前言
T1没做出来的一集。。。
时间安排及成绩
7:40 开题7:40 - 7:45 T1看懂了感觉像广搜但是复杂度好像不对。又好像是背包但是物品的体积和权值好像会算错。不是很会。看了一眼T2好像是线段树分治的板子7:45 - 8:00 T1还是不咋会果断开T2。发现这题好像也不是线段树分治。想到答案肯定满足单调性于是可以二分。但是不能对所有询问都二分因此可以整体二分中间也想过kruskal重构树但感觉不太行。没想太多感觉整体二分加上按秩合并并查集应该就行。直接开写。8:00 - 8:20 想了一会儿按秩合并并查集然后写到一般发现我不会就算维护了点的连通性也没法 O ( 1 ) O(1) O(1) 判断一段区间是否联通这。。。感觉好难啊。8:20 - 8:40 冷静思考发现我们可以求出每个点和它前一个点最早的联通时间那么一段区间联通的答案就是区间最大值。8:40 - 9:00 改完了调了调把样例都过了。感觉没啥问题于是直接扔了。9:00 - 9:10 回去看T1感觉还是没啥清晰的思路。直接开T39:10 - 9:20 T2看懂了发现明显具有单调性可以直接二分答案 线段树合并。时间复杂度应该是 n l o g 2 n nlog^2n nlog2n感觉可过就直接开写。9:20 - 10:10 写完了但是样例答案是负数回去重看了一遍题发现确实说明了答案有可能是负数。把二分的边界改一下就把所有样例过了但是这个大样例跑的有点慢啊。10:10 - 10:40 放到oj上测试一下发现确实过不去会TLE。考虑一下卡常。最开始想的是不二分直接用一个指针然后每次检验。指针只会单减因此复杂度不会炸但是被我构个菊花直接卡炸了。然后就想到可以对每个点分别二分求出答案最后答案就是所有点的最小值。然后每个点二分时右边界可以根据其它点的答案缩小。也算卡常吧。10:40 - 11:10 改完了大样例跑的飞快。检查一下感觉没啥问题直接扔了。11:10 - 11:15 5min把T4看了然后5min写了个40分跑路。回去看T111: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 分析
感觉是很好的一道题。
题意已经很清楚了就不赘述了。
首先直接搜索需要纪录四个状态 桶里的水量和三个杯子中的水量。状态数是 1 0 5 × 10 0 3 10^5 \times 100^3 105×1003 的显然过不去。我们想要减少状态数。
又不难发现实际上这个问题好像可以对应成背包问题水量看作体积操作数是代价。但是 被子倒满水后要不要倒掉 显然就成了一个问题。我们想让最后不用的那一次不倒其他用的时候需要倒掉。这似乎没法在dp里体现。
正解是有一条性质设操作(5) 为使用若干次操作(1)(2)(4)然后让被子中有一些水量。那么最优方案一定是进行若干次操作 (5)每个操作(5)后将所有有水的杯子中的水都倒入桶中。最后进行一次操作(5)但是可以将部分水倒入桶中。
这个打表证明是对的。但是我们也可以感性理解一下对于一个杯子里的水而言如果它不倒入桶中并且以后还要使用那么一定会在下次往里倒水前将里面的水倒掉。由于它里面的水不会倒入桶中又因为交换操作对于操作数没有影响。因此我们可以把这个杯子中的水被倒掉的操作移到前面形成 除了要往桶中倒水的杯子其他杯子都是空的状态。并且这个状态不会影响最优性。如果这个杯子以后不使用了那么可以看作使用最后一次操作(5)后只将部分水倒入桶中的状态。
那么就可以 b f s bfs bfs O ( 10 0 3 ) O(100^3) O(1003) 搜出所有状态然后计算出 c o s t 1 cost_1 cost1 和 c o s t 2 cost_2 cost2 数组。接着用 c o s t 1 cost_1 cost1 和 c o s t 2 cost_2 cost2 转移 d p dp dp 即可。
复杂度 O ( 300 × n ) O(300 \times n) O(300×n)
CODE
#includebits/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重构树
原题链接 分析 S o l 1 Sol1 Sol1 一个关键想法是我们可以 只关心一个点 i i i 和点 i − 1 i - 1 i−1最早的连通时间 t i t_i ti即可。
那么对于区间 [ l , r ] [l, r] [l,r] 而言它最早的连通的时间就是 m a x i l 1 r t i max_{i l 1}^{r}t_i maxil1rti。
对于 t i t_i ti 的求法我们可以整体二分 可撤销并查集 即可。我们使用 按秩合并 并查集就行。
时间复杂度 O ( q × l o g 2 q × l o g 2 n ) O(q \times log_2q \times log_2n) O(q×log2q×log2n)。 S o l 2 Sol2 Sol2
考虑维护两个点的最早连通时间也可以使用 Kruskal重构树。然后查询只需要求 l c a lca lca 即可。
时间复杂度 O ( n × l o g 2 n ) O(n \times log_2n) O(n×log2n)
下面的代码是第一种解法的代码。 CODE
#includebits/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 n n 个点的树点有点权 w i w_i wi。若现在有一个数 P P P那么对于一个点 x x x它的负荷就是所有满足一下两个条件的简单路径条数 u v uv uv 是路径的两个端点并且满足 w u ≤ w x P w_u \leq w_x P wu≤wxP w v ≤ w x P w_v \leq w_x P wv≤wxP。 x x x 在路径 u → v u \to v u→v 上。
现在想让所有点的负荷都小于 K K K求最大的 P P P。 不难看出 P P P 越大每个点的负荷只会增大不会减小。具有单调性因此可以 二分答案。 我们考虑如何检验
若给定一个 P P P那么每个点的负荷计算就很简单了。对于一个点 x x x只需要能快速查询它的子树里小于等于 w x P w_x P wxP 的数的个数即可。那么可以做 线段树合并并在 值域线段树 里二分。这样可以计算出端点都在 x x x 子树里的路径个数。对于一个端点在子树里一个端点在子树外的路径显然可以拿所有小于等于 w x P w_x P wxP 的数的个数减去 x x x 的子树里的个数这样能算出来 x x x 子树外能成为端点的点数然后和子树里的相乘即可。这样时间复杂度就是 O ( n × l o g 2 2 w ) O(n \times log^2_2w) O(n×log22w) 的。
我们发现这样过不去还要卡一下常 由于 K K K 给定因此可以对每个点求出满足条件的最大的 P P P然后最终答案就是所有点的答案取 m i n min min。对每个点求这样的 P P P 可以二分这样时间复杂度也是 O ( n × l o g 2 2 w ) O(n \times log^2_2w) O(n×log22w) 的。但是注意到每个点二分时右端点不必开满可以令当前求出的答案的最小值作为端点。这样也是一个剪枝。这样做之后就跑的特别快了最后没有被卡掉。
CODE
#includebits/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;
}正解是单 l o g log log 的。首先对于它没有使用线段树合并而是 按照 d f s dfs dfs 序由小到大建主席树。那么一个点的子树信息也可以在 d f s dfs dfs 序列中的一段区间中查询。正解也是按照上面这种对每个点求最大的 P P P然后所有点取 m i n min min 得到答案。考虑如果二分答案然后用主席树检验时间复杂度也是 O ( n × l o g 2 2 w ) O(n \times log^2_2w) O(n×log22w) 的。然后它就是把所有区间都拿出来一起在线段树上二分减去一个 l o g log log。具体写法没仔细看但是大概思路就是这。
D. 3SUM扫描线 线段树
原题链接
分析
题意说的很清楚了不在赘述。
直接说正解吧
我们对最大值在那一段进行分讨然后答案取最优
最大值在中间一段。那么可以把中间一段往两边延伸发现中间那段的答案不变两边段的答案单调不增。因此这种情况下最优值就是 [ l , l ] [l, l] [l,l] [ l 1 , r − 1 ] [l 1, r - 1] [l1,r−1] [ r , r ] [r, r] [r,r] 的最大值之和。最大值在左边段。如果我们求出 [ l , r ] [l, r] [l,r] 中最大值的最左边位置 x x x那么第一段的右端点应该大于等于 x x x。我们考虑如果左段的右端点是 r t rt rt那么要把 [ r t 1 , r ] [rt 1, r] [rt1,r] 分成两端。如果右段的左端点为 l t lt lt那么三段就是 [ l , r t ] [l, rt] [l,rt] [ r t 1 , l t − 1 ] [rt 1, lt - 1] [rt1,lt−1] [ l t , r ] [lt, r] [lt,r]。不难发现这时可以将左段向右延伸直到中间段的长度为 1 1 1。这样左段右段的答案不变中间段的答案只会变得更优。因此我们得出结论对于最大值在左段的情况中间段的长度一定为 1 1 1。因此如果中间段为 [ p , p ] [p, p] [p,p]那么中间段和右段的答案就是 h p a p m a x i p 1 r a i h_p a_p max_{i p 1}^{r}a_i hpapmaxip1rai我们需要维护 区间中 h h h 的最小值。这个可以用 线段树 单调栈维护 维护。具体来讲我们对 r r r 扫描线然后维护一个单调栈。如果 a r a s t o p a_r a_{s_{top}} arastop就将栈顶弹出。那么 [ s t o p − 1 , s t o p ) [s_{top - 1},s_{top}) [stop−1,stop) 区间的 h h h 值将会加上 a r − a s t o p a_r - a_{s_{top}} ar−astop 。特别的由于每个数刚入栈时后边没有数因此它的 h h h 值是正无穷。那么每次对于第一个栈顶我们将它的 h h h 值改为 a s t o p a r a_{s_{top}} a_r astopar 即可。然后对于所有右端点为当前 r r r 的区间 [ l , r ] [l, r] [l,r]我们在栈中二分出第一个大于 l l l 的位置 p o s pos pos这是 [ l , r ] [l, r] [l,r] 区间里最靠左的最大值的位置。在线段树上查询 [ p o s 1 , r ] [pos 1, r] [pos1,r] 的最小值并加上 a p o s a_{pos} apos更新这个询问的答案即可。最大值在右边段。将序列和询问区间反转一下就能变成上一种情况。
时间复杂度 O ( n × l o g 2 n ) O(n \times log_2n) O(n×log2n)。
CODE
#includebits/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;
}
