###### tags: `OI`
# 112-1 延平中學校內賽簡易題解
以下題解如果有問題，歡迎找出題者討論：
* E-mail: dave910602@gmail.com
* Facebook: 郭軒語（Dave Kuo）
* Discord: HNO2#4672
[題本連結](https://drive.google.com/file/d/15dfCJ-ZgQXZ34Dx_wUc5RR-MWDCVXE2R/view?usp=drive_link)
特別感謝 SorahISA、Misuki 幫忙驗題。
如果在題解過程中看到什麼演算法或資料結構不會的話，[這裡](https://github.com/HHSH-CYSH-WGSH-HSNU-Summer-Camp)跟[這裡](https://www.csie.ntu.edu.tw/~sprout/algo2023/)都是很好的學習資源。
## pA. 分糖果 (candy)
### Subtask 2
> $k = 0$
根據題意，$k = 0$ 的意思就是不會做任何分配工作，所以每個小朋友手上拿的糖果數量還是一樣，直接輸出輸入的 $a$ 就好。
### Subtask 3
> $n=2$，且在 $k$ 次平分中，兩人手上糖果數量和都是偶數
如果 $k = 0$ 就直接照原樣輸出。否則在第一次平分以後，兩人各會拿到 `(a[0] + a[1]) / 2` （0-based）顆糖果，不論平分多少次都是一樣。
### Subtask 4
> $n=2$
考慮兩人手上糖果數量和是奇數的情況。如果 $k$ 是奇數，那第一個人會拿到 `(a[0] + a[1]) / 2`（0-based） 顆，第二個人會多拿一顆，也就是 `(a[0] + a[1]) / 2 + 1`（0-based）。如果 $k$ 是偶數就兩人糖果數量對調。
### Subtask 5
> 在 $k$ 次平分中，兩人手上糖果數量和都是偶數
跟 Subtask 3 一樣，只是在第 $i$ 次（0-based）分配的時候是分 `a[i % n]` 和 `a[(i + 1) % n]`。
### Subtask 6
> 無額外限制
跟 Subtask 4 一樣，只是在第 $i$ 次（0-based）分配的時候是分 `a[i % n]` 和 `a[(i + 1) % n]`。
:::spoiler Sample Solution
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int &i : a)
cin >> i;
for (int i = 0; i < k; i++) {
int x = i % n, y = (x + 1) % n;
int sum = a[x] + a[y];
a[x] = sum / 2;
a[y] = sum - sum / 2;
}
for (int i = 0; i < n; i++)
cout << a[i] << " \n"[i == n - 1];
}
```
:::
## pB. 食物組合 (combination)
### Subtask 2
> $k=1$
$k = 1$ 就是只能選擇一種食物，所以就是所有攤位的食物好吃程度。要記得由小到大排序，在這裡可以使用任何 $\mathcal{O}(n^2)$ 或 $\mathcal{O}(n \log n)$ 的排序演算法。
### Subtask 3
> $k \leq 4$
可以寫好幾層迴圈去枚舉所有的食物組合，$k$ 是幾就寫幾層迴圈，然後把所有找到的滿足程度推到一個 `std::vector` 裡面。只是在這裡排序不能使用 $\mathcal{O}(n^2)$ 的做法了，需要使用 $\mathcal{O}(n \log n)$ 的排序演算。最簡單的方法就是引用 `std::sort`。
### Subtask 4
> $n \leq 20$
使用位元枚舉枚舉所有 $2^n$ 食物的選法，之後看枚舉到的數字是否包含恰好 $k$ 個位元是 $1$，是的話就推到一個 `std::vector` 裡面，之後再把那個 `std::vector` 排序。
### Subtask 5
> 無額外限制
跟 Subtask 4 一樣，只是要改成使用遞迴枚舉。遞迴枚舉的話，可以寫一個函式 `recursion(int idx, int selected, int sum)`，代表最後一個被選的編號是 `idx`、已經選了幾個以及目前選到的數字總和。
遞迴枚舉的時候要注意不要遞迴到實際上不存在的狀態（也就是從目前的參數遞迴下去不會找到一個合法的 $k$ 個數字的選法，例如 `idx = n`、`selected = 0`）只要這一點做到了，runtime 就是可以被保證的。
:::spoiler Sample solution
```cpp=
#include <bits/stdc++.h>
using namespace std;
int n, k;
vector<int> a, v;
void recursion(int idx, int selected, int sum) {
if (selected > 0)
sum += a[idx];
if (selected == k) {
v.emplace_back(sum);
return;
}
for (int i = idx + 1; i < n; i++)
if (n - i >= k - selected)
recursion(i, selected + 1, sum);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> k;
a.resize(n);
for (int &i : a)
cin >> i;
recursion(-1, 0, 0);
sort(v.begin(), v.end());
int m = v.size();
for (int i = 0; i < m; i++)
cout << v[i] << " \n"[i == m - 1];
}
```
:::
## pC. 搭公車 (bus)
### Subtask 2
> $n=1, q \leq 1000, m_1 \leq 1000$
應該容易發現答案一定是 $s_{1,1}, s_{1,2},\ldots,s_{1, m_1}$ 其中一個（這點對於所有 Subtask 都成立）。在這個 Subtask 中，對於每筆詢問，可以直接枚舉所有 $s_{1,1}, s_{1,2},\ldots,s_{1, m_1}$，看他加上 $d_1$ 以後會不會超過詢問值，如果不會遲到就表示可以搭那班公車。
### Subtask 3
> $n \leq 1000, q \leq 1000, \sum m_i \leq 1000$
同樣對於每筆詢問，可以直接枚舉所有 $s_{1,1}, s_{1,2},\ldots,s_{1, m_1}$，看到達公車站 $n+1$ 的時候會不會遲到。方法就是每次到一個公車站，就直接選下一班可以搭的公車搭上去，最後就可以算出到達公車站 $n+1$ 的時間。
### Subtask 4
> $n=1$
和 Subtask 2 一樣，只是這次不能夠一個一個枚舉 $s_{1,1}, s_{1,2},\ldots,s_{1, m_1}$ 了。注意到當 $x$ 越大的時候，從 $s_{1,x}$ 出發，到達公車站 $n+1$ 的時間就會越晚（這點對於所有 Subtask 都成立）。以上這個性質讓我們可以二分搜。
二分搜的方法有兩個，一個是對 $x$ 二分搜，看在 $s_{1,x}$ 出發，到達公車站 $n+1$ 的時間 $s_{1,x} + d_1$ 會不會超時。另一個是直接找 $s_{1,1}, s_{1,2},\ldots,s_{1, m_1}$ 中最後一個不超過詢問值減去 $d_1$ 的數字。
### Subtask 5
> $m_1 = m_2 = \cdots = m_n$
從每個 $s_{n,1}, s_{n,2},\ldots,s_{n, m_n}$ 往回找，找到要在 $s_{n, x} + d_n$ 抵達公車站，最早需要什麼時候從公車站 $1$ 出發才行，往回找的時候一樣是二分搜。之後在詢問的時候就對 $s_{n,1} + d_n, s_{n,2} + d_n,\ldots,s_{n, m_n} + d_n$ 二分搜，找到最後一個不超過詢問值的數字，就可以找到相對應的答案。
### Subtask 6
> 無額外限制
我們對於每條路線的每個發車時間紀錄一個值 arrival，代表如果從這條路線的這個時間點出發，什麼時候會抵達公車站 $n + 1$。從後面往回推：
* 一開始時，$s_{n,j}$ 的 arrival time 就是 $s_{n,j} + d_n$。
* 當要找第 $i$ 條路線第 $j$ 個發車時間的 arrival time 時，就去找到 $s_{i+1,1},\ldots,s_{i+1,m_{i+1}}$ 中第一個大於等於 $s_{i,j} + d_i$ 的數字，找到他的 arrival time 就是答案。
最後處理詢問的時候，就對 $s_{1,1},\ldots,s_{1,m_1}$ 的 arrival 二分搜。
:::spoiler Sample Solution
```cpp=
#include <bits/stdc++.h>
using namespace std;
constexpr int INF = 2'100'000'000;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, q;
cin >> n >> q;
vector<int> m(n), l(n);
vector<vector<int>> bus(n), arrival(n);
for (int i = 0; i < n; i++) {
cin >> m[i] >> l[i];
bus[i].resize(m[i]);
for (int &j : bus[i])
cin >> j;
}
for (int i : bus[n - 1])
arrival[n - 1].emplace_back(l[n - 1] + i);
for (int i = n - 2; i >= 0; i--) {
for (int j : bus[i]) {
auto idx = lower_bound(bus[i + 1].begin(), bus[i + 1].end(), j + l[i]) -
bus[i + 1].begin();
if (idx >= m[i + 1])
arrival[i].emplace_back(INF);
else
arrival[i].emplace_back(arrival[i + 1][idx]);
}
}
for (int i = 1; i <= q; i++) {
int x;
cin >> x;
auto idx = upper_bound(arrival[0].begin(), arrival[0].end(), x) -
arrival[0].begin();
if (idx == 0)
cout << -1 << " \n"[i == q];
else
cout << bus[0][idx - 1] << " \n"[i == q];
}
}
```
:::
## pD. 電力供給 (power-supply)
### Subtask 2
> $m = n-1$
以下題解都使用圖論的術語講解：房間 = 節點、電線 = 邊、公司 = 顏色、邊的價錢 = 權重。
這題的本質是要求出一個圖上的生成樹。因為給出的圖是一棵樹，所以很自然的就是全部的邊都選。然後根據題意，如果至少有一個 $c_i =j$，就要把 $p_j$ 加到答案裡。
### Subtask 3
> $k = 1$
裸的[最小生成樹（MST）](https://oi-wiki.org/graph/mst/)問題。最後記得要把 $p_1$ 加到答案裡面。任何你會的 MST 演算法都可以用。
### Subtask 4
> $k \leq 8$
枚舉所有的顏色集合。對於每個顏色集合，找到所有是那些顏色的邊，對他做 MST，這個顏色集合對應的花費就是 (MST $w_i$ 權重和 + 顏色 $p_i$ 總和)。取所有顏色集合中答案最小的就好。如果用 Kruskal's Algorithm 做 MST，總時間複雜度是 $\mathcal{O}(m \log m + 2^k m \alpha(n))$。
### Subtask 5
> $k \leq 12$
以下兩個 Subtask 都需要用到以下關鍵性質：
:::success
性質：假設 $E_1, E_2$ 是兩個邊的集合，且令 $S(E_1), S(E_2)$ 分別是兩個邊的集合的最小生成森林（每個 connected component 的最小生成樹的聯集），則兩個邊集合的聯集的最小生成森林 $S(E_1 \cup E_2)$ 中的任意一條邊都是 $S(E_1)$ 或 $S(E_2)$ 中的邊。換句話說，假如 $e$ 不在 $E_1$ 或 $E_2$ 的最小生成森林中，他就不會出現在 $E_1 \cup E_2$ 的最小生成森林中。
證明：可以直接由 [Cut Property](https://www.csie.ntu.edu.tw/~sprout/algo2023/ppt_pdf/week12/Minimum_spanning_tree.pdf) 得證。
:::
根據以上性質，我們可以先對每個顏色做一次 MST，留下最多 $n-1$ 條邊。之後枚舉所有顏色集合的時候，就選取那個顏色留下來的邊就好，每次就考慮最多 $k(n-1)$ 條邊。總時間複雜度是 $\mathcal{O}(m (\log m + \alpha(n)) + 2^k nk \alpha(n))$ 或 $\mathcal{O}(m (\log m + \alpha(n)) + 2^k nk \log k \alpha(n))$，視實作而定。
### Subtask 6
> 無額外限制
其實以上的作法可以再進一步延伸，我們對於每個顏色集合都去維護他的 MST 的邊集合。當要找出一個顏色集合的邊集合 $E$ 的 MST 時，如果他只包含一種顏色，就直接做；否則把第一種顏色的邊 $E_1$ 和其他邊 $E_2$ 拆開，把他們各自 MST 上的邊抓過來做 MST，這樣子最多只需要考慮 $2(n-1)$ 條邊。總時間複雜度變成 $\mathcal{O}(m (\log m + \alpha(n)) + 2^k n \alpha(n))$。
實作的時候，需要注意不要使用多餘的排序操作。例如說當要合併兩個邊集合的 MST 時，可以直接使用 `std::merge` 把兩個已經照邊權大小排的 sequence 合併起來。這個操作是線性的，不需要再依照邊權大小再排序一次。
:::spoiler Sample Solution
```cpp=
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll INF = 1'000'000'000'000'000'000LL;
struct edge {
int u, v, w;
edge(int _u, int _v, int _w) : u(_u), v(_v), w(_w) {}
bool operator<(const edge &rhs) const { return w < rhs.w; }
};
struct DSU {
vector<int> p, sz;
void reset(int n) {
p.resize(n);
sz.resize(n);
for (int i = 0; i < n; i++)
p[i] = i, sz[i] = 1;
}
int Find(int x) { return p[x] == x ? x : p[x] = Find(p[x]); }
bool Same(int x, int y) { return Find(x) == Find(y); }
void Union(int x, int y) {
x = Find(x), y = Find(y);
if (x == y)
return;
if (sz[x] > sz[y])
swap(x, y);
sz[y] += sz[x], p[x] = y;
}
} dsu;
ll run_kruskal(int n, vector<edge> &edges) {
dsu.reset(n);
ll ret = 0;
vector<edge> new_edges;
for (auto [u, v, w] : edges) {
if (!dsu.Same(u, v)) {
ret += w;
new_edges.emplace_back(u, v, w);
dsu.Union(u, v);
}
}
edges.swap(new_edges);
return ((int)edges.size() == n - 1 ? ret : INF);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m, k;
cin >> n >> m >> k;
vector<int> p(k);
vector<int> u(m), v(m), w(m), c(m);
vector<vector<edge>> edges(1 << k);
vector<ll> sum1(1 << k), sum2(1 << k);
for (int &i : p)
cin >> i;
for (int i = 0; i < m; i++) {
cin >> u[i] >> v[i] >> w[i] >> c[i];
u[i]--, v[i]--, c[i]--;
edges[1 << c[i]].push_back(edge(u[i], v[i], w[i]));
}
for (int i = 0; i < k; i++) {
sort(edges[1 << i].begin(), edges[1 << i].end());
sum1[1 << i] = run_kruskal(n, edges[1 << i]);
}
for (int i = 1; i < (1 << k); i++) {
if (!edges[i].empty())
continue;
int b = (i & (-i));
merge(edges[b].begin(), edges[b].end(), edges[i ^ b].begin(),
edges[i ^ b].end(), back_inserter(edges[i]));
sum1[i] = run_kruskal(n, edges[i]);
}
for (int i = 1; i < (1 << k); i++) {
for (int j = 0; j < k; j++)
if ((i >> j) & 1)
sum2[i] += p[j];
}
ll ans = INF;
for (int i = 1; i < (1 << k); i++)
ans = min(ans, sum1[i] + sum2[i]);
cout << ans << '\n';
}
```
:::
## pE. 區間中位數 (median)
### Subtask 2
> $n \leq 100$
枚舉所有的區間，對於每個區間排序之後找出中位數。之後再對所有區間排序找到第 $k$ 小的。
時間複雜度是 $\mathcal{O}(n^3 \log n)$
### Subtask 3
> $n \leq 3000$
一樣是找到所有區間的中位數以後對所有區間排序。只是在這裡我們在固定左界的時候，需要在短時間內求出固定左界下的所有區間中位數。方法有兩種：
1. 參考動態中位數的作法。維護一個 max-heap（現在目前所有 $\leq$ 中位數的數字）和一個 min-heap（現在目前所有 $>$ 中位數的數字），在每次插入數字時保持兩邊都是恰好一半的數字，使得 max-heap 的頂端就是動態中位數。每次要插入數字的時候，看他是大於還是 $\leq$ 目前的中位數，先插入相對應的 heap，之後再去調整兩個 heap 的大小，使得 max-heap 的頂端就是動態中位數。
2. 直接使用 BIT 或線段樹之類的維護每個數字出現了幾次。因為線段樹/BIT 的特性，可以在 $\mathcal{O}(\log n)$ 時間內找出第一個 $\leq k$ 的前綴在哪裡，也就可以在 $\mathcal{O}(\log n)$ 時間內找出區間中位數。
### Subtask 4
> $a_i = i$（$1 \leq i \leq n$）
因為這個 Subtask 給出的 $a_1,a_2,\ldots,a_n$ 的特殊性，答案是可以直接 $\mathcal{O}(1)$ 算出來的。
### Subtask 5
> 無額外限制
#### 第一個數字的求法
我們嘗試二分搜找出第一個答案。給定一個 $x$，判斷答案是不是 $\leq x$ 的方法，就是算出有幾個區間的區間中位數 $\leq x$。如果把那些滿足 $a_i > x$ 的 $i$，讓他的 $b_i$ 都設成 $1$，否則就設成 $-1$，那就相當於求出有多少個區間的總和 $\leq 0$，可以使用前綴和 + 逆序數對求出。時間複雜度可能是 $\mathcal{O}(n \log n)$ 或 $\mathcal{O}(n \log^2 n)$。
#### 第二個數字的求法
假設第一個答案是 $ans_1$，那可以求出 $ans_1$ 時，每個左界有多少個區間 $\leq 0$，在算逆序數對的時候順便算出來。但是這樣子只能求出每個左界中位數 $\leq ans_1$ 的區間有幾個，我們還需要算出 $ans_1 - 1$時，每個左界中位數 $\leq ans_1 - 1$ 的區間有幾個，兩個相減以後就會得到每個左界區間中位數恰好是 $ans_1$ 的有幾個。之後就看到 $k$ 落在哪個左界就好。
#### 第三個數字的求法
因為求出 $ans_1$ 和 $ans_2$ 了，我們就可以使用 Subtask 2 中的方法，算出固定左界之下的區間中位數，看 $k$ 是在哪個右界了。
:::spoiler Sample Solution
```cpp=
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<int> start_count(vector<int> &a, int x) {
int n = a.size();
vector<int> b(n), ret(n);
for (int i = 0; i < n; i++) {
if (a[i] <= x)
b[i] = 1;
else
b[i] = -1;
}
// count range sum >= 0
map<int, int> prefix_count;
prefix_count[0] = 1;
int threshold = 0, smaller_count = 1;
int prefix_sum = 0;
for (int i = n - 1; i >= 0; i--) {
prefix_sum += b[i];
while (threshold < prefix_sum) {
threshold++;
smaller_count += prefix_count[threshold];
}
while (threshold > prefix_sum) {
smaller_count -= prefix_count[threshold];
threshold--;
}
ret[i] = smaller_count;
prefix_count[prefix_sum]++;
if (prefix_sum <= threshold)
smaller_count++;
}
return ret;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
long long k;
cin >> n >> k;
vector<int> a(n);
for (int &i : a)
cin >> i;
int ans1, ans2, ans3;
// binary search for 1st answer
int L = 0, R = n;
while (R - L > 1) {
int M = (L + R) >> 1;
auto ret = start_count(a, M);
ll total_segments = accumulate(ret.begin(), ret.end(), 0LL);
if (total_segments >= k)
R = M;
else
L = M;
}
ans1 = R;
// ans2 calculation
auto retR = start_count(a, R), retR1 = start_count(a, R - 1);
k -= accumulate(retR1.begin(), retR1.end(), 0LL);
for (int i = 0; i < n; i++) {
if (k <= (retR[i] - retR1[i])) {
ans2 = i + 1;
break;
} else
k -= (retR[i] - retR1[i]);
}
// ans3 calculation
priority_queue<int> small_numbers;
priority_queue<int, vector<int>, greater<>> large_numbers;
for (int i = ans2 - 1; i < n; i++) {
if (i == ans2 - 1 || a[i] <= small_numbers.top()) {
small_numbers.push(a[i]);
} else {
large_numbers.push(a[i]);
}
int size = i - (ans2 - 1) + 1;
while (small_numbers.size() > (size + 1) / 2) {
large_numbers.push(small_numbers.top());
small_numbers.pop();
}
while (small_numbers.size() < (size + 1) / 2) {
small_numbers.push(large_numbers.top());
large_numbers.pop();
}
int median = small_numbers.top();
if (median == ans1) {
k--;
if (k == 0) {
ans3 = i + 1;
break;
}
}
}
cout << ans1 << ' ' << ans2 << ' ' << ans3 << '\n';
}
```
:::
## pF. 典型區間詢問題 (range-query)
### Subtask 2
> $n,q \leq 3000$
直接對於每筆詢問用一個 for 迴圈算出答案就好。時間複雜度 $\mathcal{O}(nq)$
### Subtask 3
> $x_i$（$1 \leq i \leq q$） 在 $q$ 筆詢問中最多只有 $50$ 種不同的值。
對於每種 $x_i$ 算出 $(x_i \bmod a_j)$ 的前綴和，之後每筆詢問就找出對應的 $x_i$ 區間答案。
### Subtask 4
> $l_i = 1, r_i = n$（$1 \leq i \leq q$）。
我們的目標是先預處理 $x_i =1$ 到 $2 \times 10^5$ 的所有答案。
我們讓 $ans_1,ans_2,\ldots$ 代表 $x_i = 1,2,\ldots$ 的答案，並且把每個 $ans_i$ 都初始化為 $q \times i$。首先先算出每種數字在 $a$ 中出現了幾次。假設一個數字 $k$ 出現了 $b$ 次，那因為 $(x_i \bmod a_j) = x_i - a_j \lfloor \frac{x_i}{a_j} \rfloor$，可以在 $ans_{k}, ans_{2k}, ans_{3k},\ldots$ 的位置都扣掉 $k \times b$，之後再對 $ans$ 做前綴和就可以求出 $ans_1,ans_2,\ldots$ 正確的值了。
### Subtask 5
> $a_i \leq 50$（$1 \leq i \leq n$）。
對於每種數字做出現了幾次的前綴和，之後每筆詢問就掃過每個數字求他的貢獻。假如一個數字 $k$ 在區間內出現了 $b$ 次，對答案的貢獻就是 $(x_i \bmod k) \times b$。
### Subtask 6
> $a_i \geq 4000$（$1 \leq i \leq n$）。
引導性的子任務。以下提供兩種思路：
1. 對序列分塊，之後對於每一塊都去做 Subtask 4 的事情，因為這個 Subtask $a_i$ 值域都很大，所以 runtime 可以被保證。查詢的時候就分成兩邊不完整的塊和中間完整的塊分別去做查詢。完整的塊就直接戳算好答案，不完整的塊就直接一個迴圈跑過去就好。
2. 把所有詢問照 $x_i$ 由小到大排序，參考 $(x_i \bmod a_j) = x_i - a_j \lfloor \frac{x_i}{a_j} \rfloor$，用線段樹或 BIT 之類的維護 $- a_j \lfloor \frac{x_i}{a_j} \rfloor$ 的部分。由於 $\frac{C}{a_i}$ 都很小，所以 runtime 可以被保證。
### Subtask 7
> 無額外限制
把 Subtask 5 和 6 的作法結合起來，$a_i \leq \sqrt{C}$ 的部分用前者，$a_i > \sqrt{C}$ 用後者。小心實作的話，令 $m = \max(n,C,q)$，則可以做到 $\mathcal{O}(m \sqrt{m})$。如果常數小一點的話 $\mathcal{O}(m \sqrt{m \log m})$ 也有機會過。
:::spoiler Sample Solution
```cpp=
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int B = 450;
constexpr int C = 200'000;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, q;
cin >> n >> q;
vector<int> a(n);
for (int &i : a)
cin >> i;
const int nB = (n + B - 1) / B;
vector<vector<int>> small_count(B + 1, vector<int>(n));
vector<vector<ll>> large_sum(nB, vector<ll>(C + 1));
// partition the whole array into blocks of size B
// precalculation for each block, based on small (<=B) and large (>B) values
for (int i = 0; i < nB; i++) {
int l = i * B, r = min((i + 1) * B, n); // [l,r)
vector<int> large_values;
for (int j = l; j < r; j++) {
if (a[j] <= B)
small_count[a[j]][j]++;
else
large_values.emplace_back(a[j]);
}
int large_value_count = large_values.size();
for (int j : large_values)
for (int k = j; k <= C; k += j)
large_sum[i][k] -= j;
for (int j = 1; j <= C; j++)
large_sum[i][j] += large_sum[i][j - 1] + large_value_count;
}
// prefix sum on count of small values
for (int i = 1; i <= B; i++)
for (int j = 1; j <= n; j++)
small_count[i][j] += small_count[i][j - 1];
auto get_small_prefix = [&](int x, int y) {
if (y < 0)
return 0;
else
return small_count[x][y];
};
// process queries
while (q--) {
int l, r, x;
cin >> l >> r >> x;
l--, r--;
int lb = l / B, rb = r / B;
ll ans = 0;
// small block
if (lb == rb) {
for (int i = l; i <= r; i++)
ans += (x % a[i]);
cout << ans << '\n';
continue;
}
// in block
if (lb + 1 <= rb - 1) {
// small
int blockl = (lb + 1) * B, blockr = rb * B - 1;
for (int i = 1; i <= B; i++) {
ans += (x % i) * 1LL *
(get_small_prefix(i, blockr) - get_small_prefix(i, blockl - 1));
}
// large
for (int i = lb + 1; i <= rb - 1; i++) {
ans += large_sum[i][x];
}
}
for (int i = l; i < (lb + 1) * B; i++)
ans += (x % a[i]);
for (int i = rb * B; i <= r; i++)
ans += (x % a[i]);
cout << ans << '\n';
}
}
```
:::
Sign in with Wallet
Connect another wallet