# 113學年度建國中學校內資訊能力競賽 複試題解
----
## 難度
$C<A<D<B<E$
---
# pA PCC 問問題
## Setter : PCC
----
連續給分是因為怕同分比序
~~順便出最近兩年校內賽都沒出現的互動題~~
----
## Subtask 1 : $N \le 10$
其實我也不知道怎麽做到的
應該是寫subtask 2寫爛就會只有subtask 1？
----
## Subtask 2 : 41./100
看一下範例是問 $(0,0,n-1)$ 想到可以問兩個一樣的人
於是可以觀察到問 $i,i,j$ 可以比較兩個數字的大小
如果Ask(i,i,j) = 0，則 $p_i \le p_j$
有比較函式了耶
----
sort(p.begin(),p.end(),cmp)
----
蛤怎麽沒過???
因為 std::sort 沒有保證比較次數
用 std::stable_sort
----
## Subtask 2 : 68./100
如果已知 $p_i < p_j$ ，那問 $(i,j,j)$ 可以知道 $p_i \oplus p_j$
可以花 $N$ 次找出最小的人
之後花 $N$ 次知道各人跟 $0$ 的 xor
----
## Subtask 2 : 78./100
比大小的時候問了什麼? $(i,i,j)$
知道兩個人的xor時問了什麼? $(i,i,j)$
感覺一樣欸
----
壓一下次數，令目前記到的最小值的index為mn
如果問 $(mn,mn,i) \neq 0$
那我們同時會知道 $p_{mn} > p_i \land p_{mn} \oplus p_i$
如果 $(mn,mn,i) = 0$ ，那我們再問一次 $(mn,i,i)$ 知道兩個人的 xor
----
找答案的時候只要把已知的兩個人xor接邊，，從 $p_{mn} = 0$ 開始 DFS 即可
----
這樣看起來是滿滿的 $2N$ 次？
只要整個排列是反序的就會跑滿
----
judge 是 non-adaptive
----
如果我們random決定先問 $(mn,mn,i)$ 還是 $(mn,i,i)$ ，那我們有一半的機率戳到非零的那一個
期望次數 $\frac{1}{2} \times N+\frac{1}{2} \times 2N = 1.5N$
理論上會有 78.多分
----
## Subtask 2 : 100/100
一樣用到 judge 是 non-adaptive
----
先 random shuffle 以免被刻意構造的測資卡
有哪些情況問 $(mn,i,i) = 0$ ?
----
當最小值變小的時候
----
這東西大概在隨機的陣列期望值是幾次？
Ans : $\log N$ 層級次數
(proof is left as an exercise)
提示：分開考慮各個數字的貢獻
----
次數： $N+\log N$
滿分!
----
希望不會有人因為這題 $< 1$ 分的差距下去...
---
# pB 補牙
## Setter : guagua0407
----
## Subtask 1：$n,q\leq 5000$
暴力$O(nq)$做
----
## Subtask 2：$t=1$
基本上是[cses](https://cses.fi/problemset/task/2416)
其中一種做法是離線+bit
----
## full
考慮一顆線段樹存$[l,r]$的：
- 最大的$a_i$
- $\sum a_i$
- $[l,r]$中把$[l,m]$變好的最小操作次數
----
怎麼build?
前兩項都很好做
問題是最後一項
把$[l,m]$和$[m+1,r]$合併時要看的是右邊給左邊的
左邊的人可能要抬到右邊最大的人那麼高
----
假設右邊最大的人是$X$
來看怎麼算$[l,m]$
- 如果$[l,m]$最大的人$<X$ 那就是$X\cdot len-\sum a_i$
- 不然的話看$[l,m]$的左小孩有沒有$<X$
- 如果有：那右邊的人都會抬到$X$，然後往左邊遞迴
- 反之：左小孩都不會動，遞迴右邊
這樣能在$O(n\log^2n)$建好
----
那算答案呢？
其實差不多
就把$[l,r]$分成$\log$個區間
從右往左用類似的方法算
可以寫在遞迴裡也可以真的把$\log$個人取出來
這樣會是$O((n+q)\log^2 n)$
----
Code
```cpp=
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
void setIO(string s) {
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
struct node{
ll ans,sum;
int maxY;
node(){
ans=0;
sum=0;
maxY=-1;
}
};
const int mxn=2e5+5;
vector<node> segtree(mxn*4);
vector<pair<pair<int,int>,int>> intervals;
int n,q;
bool tf=false;
ll cut(int l,int r,int v,int val){
if(l==r){
return (val>segtree[v].maxY?val-segtree[v].maxY:0);
}
int mid=(l+r)/2;
if(val>segtree[v*2+1].maxY) return cut(l,mid,v*2,val)+1ll*val*(r-mid)-segtree[v*2+1].sum;
else return segtree[v].ans+cut(mid+1,r,v*2+1,val);
}
void pull(int l,int r,int v){
segtree[v].maxY=max(segtree[v*2].maxY,segtree[v*2+1].maxY);
segtree[v].sum=segtree[v*2].sum+segtree[v*2+1].sum;
int mid=(l+r)/2;
segtree[v].ans=cut(l,mid,v*2,segtree[v*2+1].maxY);
}
void update(int pos,int val,int l=0,int r=n-1,int v=1){
if(l==r){
segtree[v].maxY=val;
segtree[v].ans=0;
segtree[v].sum=val;
return;
}
int mid=(l+r)/2;
if(pos<=mid) update(pos,val,l,mid,v*2);
else update(pos,val,mid+1,r,v*2+1);
pull(l,r,v);
}
void query(int tl,int tr,int l=0,int r=n-1,int v=1){
if(r<tl or tr<l){
return;
}
if(tl<=l and r<=tr){
intervals.push_back({{l,r},v});
return;
}
int mid=(l+r)/2;
query(tl,min(mid,tr),l,mid,v*2);
query(max(mid+1,tl),tr,mid+1,r,v*2+1);
}
int main() {_
cin>>n>>q;
vector<int> a(n);
for(int i=0;i<n;i++){
cin>>a[i];
}
for(int i=0;i<n;i++){
update(i,a[i]);
}
for(int i=0;i<q;i++){
int t;
cin>>t;
if(t==0){
int id,x;
cin>>id>>x;
id--;
a[id]=x;
update(id,a[id]);
}
else{
int l,r;
cin>>l>>r;
l--,r--;
query(l,r);
ll ans=0;
int maxY=-1;
while(!intervals.empty()){
ans+=cut(intervals.back().f.f,intervals.back().f.s,intervals.back().s,maxY);
maxY=max(maxY,segtree[intervals.back().s].maxY);
intervals.pop_back();
}
cout<<ans<<'\n';
}
}
return 0;
}
//maybe its multiset not set
//yeeorz
//diaoborz
```
---
# pC SJY 的國際刷牙奧林匹亞難題
## Setter : becaido
----
## Subtask 1：$n=1$
----
等價求最大連續和
$O(m^2)$ 或 $O(m)$ 都會過
----
## Subtask 2：恰好存在一個 $a_{i,j}<0$，其餘都 $\ge 0$
----
$<0$ 的那個只會有拿或不拿
拿的話一定是把全部人都加起來最好
不拿的話是拿上面全部跟下面全部，再看左邊跟右邊哪個比較大
----
要注意 $m=1$ 的 Case
----
## Subtask 3：$n,m\le 70$
----
令 $dp_{i,l,r}$ 是刷了前 $i$ 排牙齒
且第 $i$ 排刷 $[l,r]$ 的最大值
----
轉移可以從 $dp_{i-1}$ 枚舉區間
複雜度 $O(nm^4)$ 可以通過
記 $dp$ 值的前後綴 $\max$ 可以優化到 $O(nm^3)$
----
## Subtask 4：無其他限制
----
第 $i$ 排的區間被 $i-1$ 排包含的情況
$[l,r]$ 可以從 $[l,r+1]$ 加上一段 $dp_{i-1,1,r}\sim dp_{i-1,l,r}$ 轉移過來
----
第 $i$ 排包含第 $i-1$ 排的情況類似
維護 $dp$ 值的前後綴 $\max$
時間複雜度 $O(nm^2)$
----
空間 $O(nm^2)$ 會超過記憶體限制
可以用滾動的方式做到 $O(m^2)$
----
Code
```cpp=
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;
const int N = 505;
int n, m;
ll ans, sum[N][N], dp[N][N], pre_mx[N][N], suf_mx[N][N];
int main() {
ios::sync_with_stdio(false), cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
int x;
cin >> x;
sum[i][j] = sum[i][j - 1] + x;
}
}
for (int i = 1; i <= n; i++) {
for (int r = 1; r <= m; r++) {
pre_mx[r][0] = -INF;
for (int l = 1; l <= r; l++) {
pre_mx[r][l] = max(pre_mx[r][l - 1], dp[l][r]);
}
suf_mx[r][r + 1] = -INF;
for (int l = r; l >= 1; l--) {
suf_mx[r][l] = max(suf_mx[r][l + 1], dp[l][r]);
}
}
for (int l = 1; l <= m; l++) {
ll mx = -INF;
fill(dp[l] + 1, dp[l] + m + 1, -INF);
for (int r = l; r <= m; r++) {
mx = max(mx, suf_mx[r][l]);
dp[l][r] = max(dp[l][r], mx + sum[i][r] - sum[i][l - 1]);
}
mx = -INF;
for (int r = m; r >= l; r--) {
mx = max(mx, pre_mx[r][l]);
dp[l][r] = max(dp[l][r], mx + sum[i][r] - sum[i][l - 1]);
}
}
}
ans = -INF;
for (int l = 1; l <= m; l++) {
ans = max(ans, *max_element(dp[l] + 1, dp[l] + m + 1));
}
cout << ans << '\n';
}
```
---
# pD 小祥愛賽車
## Setter : owoovo
----
## Subtask 1：$a_i=1$
正常的dijkstra
----
## Subtask 2：$a_i遞減$
起點和終點反過來就變正常的dijkstra
----
## Subtask 3：$一條鍊$
對答案二分搜
掃一遍$L$去往前走
----
## Subtask 4：$N,M,L\leq 3000$
拆點，設$v_{i,j}$是走$j$步後到$i$
好好連邊之後就可以開心dijkstra
----
## Subtask 4：$N,M\leq 3000$
出題的人忘了
----
## full
看到$\min$就想二分搜答案了
發現到你在判斷的時候其實是在問說：
只走一些好的邊時，可不可以走到$n$
----
去設$dis_i$是走到$i$最少需要用到多長$L$的前綴
在這上面做dijkstra
現在問題只剩下轉移
----
轉移其實在問一個後綴裡最前面$\leq x$的位置
可以線段樹上二分搜(好像有卡到常 抱歉..)
賽中好像也有人是用sparse table
----
發現到可以不用邊去找$L$，
而是用$L$去看他可以轉移的邊
就可以用一個迴圈取代資結，超賺
會是$O((N+M+L)\cdot\log M\cdot\log C)$之類的
----
Code
```cpp=
#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
using namespace std;
const ll e18=1e18;
int n,m,L,vis[100010];
int a[1000010];
vector<pair<int,int>> e[100010];
bool check(ll c){
for(int i=1;i<=n;i++)vis[i]=0;
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
vis[1]=1;
for(auto x:e[1]){
pq.push({x.S,x.F});
}
for(int i=0;i<L;i++){
vector<int> id;
while(!pq.empty()&&pq.top().F<=c/a[i]){
auto [x,y]=pq.top();
pq.pop();
if(vis[y]==0){
id.push_back(y);
vis[y]=1;
}
}
for(auto x:id){
for(auto E:e[x]){
if(vis[E.F]==0){
pq.push({E.S,E.F});
}
}
}
}
return vis[n];
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m>>L;
for(int i=0;i<L;i++)cin>>a[i];
for(int i=0;i<m;i++){
int u,v;
ll w;
cin>>u>>v>>w;
e[u].push_back(make_pair(v,w));
e[v].push_back(make_pair(u,w));
}
ll l=1,r=e18;
while(l!=r){
ll m=(l+r)>>1;
if(check(m)){
r=m;
}else{
l=m+1;
}
}
cout<<l<<"\n";
return 0;
}
```
---
# pE 小祥愛騎車
## Setter : pacybwoah
----
## 簡短題敘
給兩個長度為 $N$ 的序列 $A,B$，多筆詢問 $[L,R]$ 問 $\max\limits_{L \leq i \leq j \leq R}(\max\limits_{i \leq v \leq j} A_v - \max\limits_{i \leq v \leq j} B_v + K \cdot (j - i + 1))$
----
## Subtask 1：$N,Q \leq 100$
對每筆詢問枚舉所有 $[i,j]$ 算答案，複雜度 $O(QN^3)$
----
## Subtask 2：$N \leq 2000$
$N$ 很小，可以預處理所有可能詢問的答案
----
定義 $dp_{l,r}$ 為 $[l,r]$ 這筆詢問的答案，則他有可能：
- 直接選 $[l,r]$ 這段區間
- 選比較小的區間：此時這段區間會被 $[l,r-1]$ 或 $[l+1,r]$ 覆蓋到，因此可以取 $\max(dp_{l,r-1},dp_{l+1,r})$
詢問時直接查表回答，複雜度 $O(n^2 + q)$
----
## Subtask 3：$K=0$
當長度對答案沒有影響時，可以注意到：對於一段區間 $[l,r]$，假設 $A$ 的 max 出現在 $v$，那其實可以直接選 $[v,v]$ 就好，因為 $\max A$ 不變，而且 $\max B$ 不會變大
----
因此問題其實就是問 $\max\limits_{l \leq i \leq r}(A_i-B_i)$，可以用你最喜歡的 RMQ 資結解，複雜度 $O(N + QlogN)$ 或 $O(NlogN + Q)$
----
## Subtask 4：$Q=1$
要進入比較通靈的部分了
max 的特質是很難刪東西，會發現很難維護
要怎麼樣才能只用合併算出答案呢？
----
考慮分治！
定義 $f(l, r)$ 為算出 $[l,r]$ 這段區間答案的函數，每次遞迴要
- 呼叫 $f(l, mid)$ 跟 $f(mid + 1,r)$
- 算出跨過 mid 的區間中的最大好感度
----
先定義 maxA, maxB 兩個陣列，代表每個位置到 mid 這段區間（$[i,mid]$ 或 $[mid + 1,i]$）的最大 A, B
那題目就變成：想要在 $[l,mid]$ 跟 $[mid + 1,r]$ 分別抓 $i$ 跟 $j$，使得
$\max(\text{maxA[i]},\text{maxA[j]})$
$-\max(\text{maxB[i]},\text{maxB[j]})+K*(j-i+1)$ 最大
----
可以分成兩種情況：
1. maxA 跟 maxB 的最大值出現在同一側
2. maxA 跟 maxB 的最大值出現在不同側
----
先講解同側的 case：
枚舉左邊的位置當作 $i$ ，可以用雙指針找到右邊滿足 $\text{maxA[i]} \geq \text{maxA[j]}$ 而且 $\text{maxB[i]} \geq \text{maxB[j]}$ 的人
----
因為 maxA 跟 maxB 都已經確定，因此選最右邊的人長度最長 = 最好
記得右邊的位置也要做同樣的事
----
異側的 case：
可以做類似的事情，但有兩種不同的枚舉方法：
- 枚舉當 maxA 的人
- 枚舉當 maxB 的人
----
- 如果枚舉當 maxA 的人，那要在另外一邊找（長度 - maxB）最大的人
- 如果枚舉當 maxB 的人，那要在另外一邊找（長度 + maxA）最大的人
----
注意到只有第二種方法會有單調性！
單調性：因為長度跟 maxA 都非嚴格遞增，所以對於左邊的人來說，可以直接選符合條件且最右邊的人配他
----
所以小心分 case 並好好雙指針就可以處理答案了！複雜度 $O(nlogn)$
----
## Subtask 5：無特別限制
線段樹是什麼？
----
線段樹是「把分治的結果儲存起來」的資料結構
----
要儲存什麼東西，才能回答區間詢問？
----
在一般用線段樹回答區間詢問的時候，會分成三種狀況：
- 詢問區間完全包含節點區間
- 詢問區間跟節點區間不相交
- 詢問區間與節點區間部分重疊
----
第一種和第二種狀況很好處理，麻煩的是第三種狀況
為了方便，我們把線段樹上的目前節點叫做 $[l,r]$ ，把重疊的部分叫做 $[L,R]$
----
分治的時候做的事是：枚舉 $[l,mid]$ 中的人，用雙指針找到 $[mid,r]$ 中最右邊且滿足條件的人
我們可以先對每個人紀錄「最右邊且滿足條件的人」，但問題是這個人有可能比 $R$ 大
----
注意到對於一個左邊的人，如果他的「最右邊且滿足條件的人」比 $R$ 大的話，那他會想直接拿 $R$ 當右邊的人。
----
同時，「最右邊且滿足條件的人」會隨著左邊的人遞減而遞增。這代表我們可以用二分搜找到分界點 $x$，使得 $[L,x]$ 的「最右邊且滿足條件的人」都超過 $R$，而 $[x+1,mid]$ 的「最右邊且滿足條件的人」都不超過 $R$
----
對於 $[L,x]$ 中的人，因為右端點都是 $R$ ，所以可以先用一個存「左半邊貢獻」的線段樹查出他們的貢獻最大值，再加上 $R$ 的貢獻
對於 $[x+1,mid]$ 中的人，因為右端點都包含在詢問區間裡，所以可以直接用存「最大貢獻」的線段樹查出貢獻最大值
----
這樣就做完了！在一個線段樹的節點中，總共需要存四個線段樹，對應到（分治時的兩種狀況）$\cdot$（查詢貢獻時的兩種狀況）
詢問時在一個節點中需要花 $O(logN)$ 的時間，所以時間複雜度是 $O(NlogN + Qlog^2N)$
----
空間複雜度是 $O(NlogN)$，但是因為要存很多東西所以記憶體會很大
我有特別開到 1024 MB，但如果想要壓記憶體的話可以用 [這篇 blog 的技巧](https://codeforces.com/blog/entry/119104) 把詢問離線，在分治時一起算答案，這樣子空間複雜度會變成 $O(N)$
----
Code
```cpp=
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
using namespace std;
typedef long long ll;
const ll mininf = -1e18;
ll k;
vector<ll> tmp;
vector<pair<ll, ll>> vec;
struct st{
vector<ll> seg;
void build(int l, int r, int ind){
if(l == r){
seg[ind] = tmp[l];
}
else{
int mid = (l + r) >> 1;
build(l, mid, ind * 2);
build(mid + 1, r, ind * 2 + 1);
seg[ind] = max(seg[ind * 2], seg[ind * 2 + 1]);
}
}
st(int l, int r){
int n = r - l + 1;
if(n == 0) return;
seg.resize(4 * n + 4);
build(l, r, 1);
}
ll query(int l, int r, int start, int end, int ind){
if(r < start || end < l) return mininf;
if(start <= l && r <= end) return seg[ind];
int mid = (l + r) >> 1;
return max(query(l, mid, start, end, ind * 2), query(mid + 1, r, start, end, ind * 2 + 1));
}
};
struct node{
ll ans;
vector<int> ab, ba;
vector<ll> maxA, maxB;
st abnorm, banorm, abhalf, bahalf;
node(): abnorm(1, 0), banorm(1, 0), abhalf(1, 0), bahalf(1, 0){}
};
vector<node> seg;
void build(int l, int r, int ind){
if(l == r){
seg[ind].ans = vec[l].first - vec[l].second + k;
return;
}
int mid = (l + r) >> 1;
build(l, mid, ind * 2);
build(mid + 1, r, ind * 2 + 1);
seg[ind].ans = max(seg[ind * 2].ans, seg[ind * 2 + 1].ans);
int len = r - l + 1;
seg[ind].ab.resize(len);
seg[ind].ba.resize(len);
seg[ind].maxA.resize(len);
seg[ind].maxB.resize(len);
for(int i = mid; i >= l; i--) seg[ind].maxA[i - l] = max(seg[ind].maxA[i + 1 - l], vec[i].first), seg[ind].maxB[i - l] = max(seg[ind].maxB[i + 1 - l], vec[i].second);
seg[ind].maxA[mid + 1 - l] = vec[mid + 1].first, seg[ind].maxB[mid + 1 - l] = vec[mid + 1].second;
for(int i = mid + 2; i <= r; i++) seg[ind].maxA[i - l] = max(seg[ind].maxA[i - 1 - l], vec[i].first), seg[ind].maxB[i - l] = max(seg[ind].maxB[i - 1 - l], vec[i].second);
int ptr = mid;
for(int i = mid; i >= l; i--){
while(ptr < r && seg[ind].maxA[ptr + 1 - l] <= seg[ind].maxA[i - l] && seg[ind].maxB[ptr + 1 - l] <= seg[ind].maxB[i - l]) ptr++;
seg[ind].ab[i - l] = ptr;
if(ptr <= mid) tmp[i] = mininf;
else tmp[i] = seg[ind].maxA[i - l] - seg[ind].maxB[i - l] + k * (ptr - i + 1);
seg[ind].ans = max(seg[ind].ans, tmp[i]);
}
ptr = mid + 1;
for(int i = mid + 1; i <= r; i++){
while(ptr > l && seg[ind].maxA[ptr - 1 - l] <= seg[ind].maxA[i - l] && seg[ind].maxB[ptr - 1 - l] <= seg[ind].maxB[i - l]) ptr--;
seg[ind].ab[i - l] = ptr;
if(ptr > mid) tmp[i] = mininf;
else tmp[i] = seg[ind].maxA[i - l] - seg[ind].maxB[i - l] + k * (i - ptr + 1);
seg[ind].ans = max(seg[ind].ans, tmp[i]);
}
seg[ind].abnorm = st(l, r);
ptr = mid;
for(int i = mid; i >= l; i--){
while(ptr < r && seg[ind].maxB[ptr + 1 - l] <= seg[ind].maxB[i - l]) ptr++;
seg[ind].ba[i - l] = ptr;
if(ptr <= mid) tmp[i] = mininf;
else tmp[i] = seg[ind].maxA[ptr - l] - seg[ind].maxB[i - l] + k * (ptr - i + 1);
seg[ind].ans = max(seg[ind].ans, tmp[i]);
}
ptr = mid + 1;
for(int i = mid + 1; i <= r; i++){
while(ptr > l && seg[ind].maxB[ptr - 1 - l] <= seg[ind].maxB[i - l]) ptr--;
seg[ind].ba[i - l] = ptr;
if(ptr > mid) tmp[i] = mininf;
else tmp[i] = seg[ind].maxA[ptr - l] - seg[ind].maxB[i - l] + k * (i - ptr + 1);
seg[ind].ans = max(seg[ind].ans, tmp[i]);
}
seg[ind].banorm = st(l, r);
for(int i = l; i <= mid; i++) tmp[i] = seg[ind].maxA[i - l] - seg[ind].maxB[i - l] + k * (mid - i + 1);
for(int i = mid + 1; i <= r; i++) tmp[i] = seg[ind].maxA[i - l] - seg[ind].maxB[i - l] + k * (i - mid);
seg[ind].abhalf = st(l, r);
for(int i = l; i <= mid; i++) tmp[i] = -seg[ind].maxB[i - l] + k * (mid - i + 1);
for(int i = mid + 1; i <= r; i++) tmp[i] = -seg[ind].maxB[i - l] + k * (i - mid);
seg[ind].bahalf = st(l, r);
}
ll query(int l, int r, int start, int end, int ind){
if(r < start || end < l) return mininf;
if(start <= l && r <= end) return seg[ind].ans;
int mid = (l + r) >> 1;
ll res = max(query(l, mid, start, end, ind * 2), query(mid + 1, r, start, end, ind * 2 + 1));
if(end <= mid || mid + 1 <= start) return res;
start = max(start, l);
end = min(end, r);
int bsl = start, bsr = mid + 1, bsmid;
while(bsl < bsr){
bsmid = (bsl + bsr) >> 1;
if(seg[ind].ab[bsmid - l] <= end) bsr = bsmid;
else bsl = bsmid + 1;
}
if(bsl > start) res = max(res, seg[ind].abhalf.query(l, r, start, bsl - 1, 1) + k * (end - mid));
if(bsl <= mid) res = max(res, seg[ind].abnorm.query(l, r, bsl, mid, 1));
bsl = start, bsr = mid + 1;
while(bsl < bsr){
bsmid = (bsl + bsr) >> 1;
if(seg[ind].ba[bsmid - l] <= end) bsr = bsmid;
else bsl = bsmid + 1;
}
if(bsl > start) res = max(res, seg[ind].bahalf.query(l, r, start, bsl - 1, 1) + seg[ind].maxA[end - l] + k * (end - mid));
if(bsl <= mid) res = max(res, seg[ind].banorm.query(l, r, bsl, mid, 1));
bsl = mid, bsr = end;
while(bsl < bsr){
bsmid = ((bsl + bsr) >> 1) + 1;
if(seg[ind].ab[bsmid - l] >= start) bsl = bsmid;
else bsr = bsmid - 1;
}
if(bsl >= mid + 1) res = max(res, seg[ind].abnorm.query(l, r, mid + 1, bsl, 1));
if(bsl < end) res = max(res, seg[ind].abhalf.query(l, r, bsl + 1, end, 1) + k * (mid - start + 1));
bsl = mid, bsr = end;
while(bsl < bsr){
bsmid = ((bsl + bsr) >> 1) + 1;
if(seg[ind].ba[bsmid - l] >= start) bsl = bsmid;
else bsr = bsmid - 1;
}
if(bsl >= mid + 1) res = max(res, seg[ind].banorm.query(l, r, mid + 1, bsl, 1));
if(bsl < end) res = max(res, seg[ind].bahalf.query(l, r, bsl + 1, end, 1) + k * (mid - start + 1) + seg[ind].maxA[start - l]);
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
cin >> k;
tmp.resize(n + 1);
vec.resize(n + 1);
for(int i = 1; i <= n; i++) cin >> vec[i].first;
for(int i = 1; i <= n; i++) cin >> vec[i].second;
seg.resize(4 * n + 4, node());
build(1, n, 1);
int q;
cin >> q;
for(int i = 0; i < q; i++){
int l, r;
cin >> l >> r;
cout << query(1, n, l, r, 1) << "\n";
}
}
```
---
# Some stats
----
## 場內 + 場外首殺
pA：dreamoon @ 10:09:32
pB：dreamoon @ 11:19:05
pC：dreamoon @ 09:21:27
pD：dreamoon @ 09:41:37
pE：x
----
## 場內首殺
pA：ckfin_026 @ 10:33:41
pB：ckfin_023 @ 11:56:26
pC：ckfin_023 @ 09:37:44
pD：ckfin_024 @ 10:41:46
pE：x
----
## pA 場內分佈
100：3
68：3
41：4
20：7
----
## pB 場內分佈
100：1
40：3
13：20
----
## pC 場內分佈
100：4
39：1
28：17
12：2
----
## pD 場內分佈
100：1
70：1
28：1
21：1
7：6
----
## pE 場內分佈
62：1
47：1
33：1
22：1
21：1
15：1
7：10
----
## 場內各題平均
pA：26.09
pB：15.48
pC：30.29
pD：8.42
pE：8.71
Total：89.00
{"title":"建中資訊校內賽複賽題解","slideOptions":"{}","description":"A<B<C \\approx D \\approx E","contributors":"[{\"id\":\"80534ff6-e4c7-48c5-88c7-d13ac225a4c2\",\"add\":5332,\"del\":85},{\"id\":\"44be8f10-8a3c-4f95-9084-6a5f98bc8bf5\",\"add\":1278,\"del\":31},{\"id\":\"7816456f-346c-479d-bcac-746977dfdcea\",\"add\":9149,\"del\":72},{\"id\":\"52026c9b-045c-4e64-9cc6-78986ed19085\",\"add\":2120,\"del\":3}]"}