???+note "[TIOJ 2221 . 足球場](https://tioj.ck.tp.edu.tw/problems/2221)"
給 $n$ 個二維座標點，問能組成多少個矩形
$1\le n\le 1000,0\le x_i, y_i \le 10^9$
??? note "思路"
矩形由「對角線長度」和「中心座標」決定。所以我們枚舉 $i,j$，將 pair(i 跟 j 的距離, i 跟 j 的中點)++，最後對於每個 distinct pair 的方法數就是 $C^k_2$
??? note "code"
```cpp linenums="1"
#include <bits/stdc++.h>
#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0);
#define mp(a, b) make_pair(a, b)
#define F first
#define S second
using namespace std;
typedef long long ll;
using pll = pair<ll, ll>;
ll dis(pll a, pll b){
ll x = a.F - b.F;
ll y = a.S - b.S;
return x * x + y * y;
}
pll operator+(pll a, pll b){
return mp(a.F + b.F, a.S + b.S);
}
int main(){
StarBurstStream
int n;
cin >> n;
vector<pll> p(n);
for(int i = 0; i < n; i++){
cin >> p[i].F >> p[i].S;
}
map<pair<pll, ll>, ll> cnt;
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
cnt[mp(p[i] + p[j], dis(p[i], p[j]))]++;
}
}
ll ans = 0;
for(auto i : cnt){
ans += i.S * (i.S - 1) / 2;
}
cout << ans << "\n";
return 0;
}
```
???+note "[Atcoder abc218 D. Rectangles](https://atcoder.jp/contests/abc218/tasks/abc218_d)"
給 $n$ 個二維座標點，問能組成多少個矩形滿足該矩形平行 $x$ 軸和 $y$ 軸
$4\le n\le 2000,0\le x_i,y_i\le 10^9$
??? note "思路"
跟上一題的差別是我們在枚舉 i, j 時需要固定一個維度，然後去做一樣的事情
??? note "code"
```cpp linenums="1"
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define mk make_pair
#define F first
#define S second
#define ALL(x) x.begin(), x.end()
using namespace std;
using pii = pair<int, int>;
struct Node {
int x, y;
};
const int N = 2005;
int n;
Node a[N];
signed main() {
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i].x >> a[i].y;
}
map<pii, int> mp;
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (a[i].y == a[j].y) {
int len = abs(a[j].x - a[i].x);
int point = (a[i].x + a[j].x);
mp[{len, point}]++;
}
}
}
int ans = 0;
for (auto it : mp) {
ans += it.S * (it.S - 1) / 2;
}
cout << ans << '\n';
}
```
???+note "[2016 全國賽 p3. 框架區間](https://tioj.ck.tp.edu.tw/problems/1913)"
給一個 $1 \ldots n$ 的 permutation $p$，問有幾個 $(i,j)$ 滿足 $i$ 在 $p$ 內與 $j$ 在 $p$ 內的位置所形成的區間內，數字集合恰好是 $\{ i,\ldots ,j \}$
$n\le 5000$
??? note "思路"
枚舉 i, j，看 pos[i], ..., pos[j] 的 min 是否為 pos[i] 且 max 是否為 pos[j]
???+note "[2022 全國賽 pD. 文字編輯器 (editor)](https://nhspc2022.twpca.org/release/problems/problems.pdf#page=11)"
有一個由 $\texttt{+}, \texttt{[}, \texttt{]}, \texttt{x}$ 組成合法序列，此時將其中一個 $\texttt{+}$ 改成 $\texttt{|}$，並將所有 $\texttt{[}, \texttt{]}$ 換成 $\texttt{|}$。給你這個改完的序列 $s$，輸出任意一個原來的合法序列。
$|s| \le 10^6$
??? note "思路"
兩個 $\texttt{x}$ 中一定要有 $\texttt{+}$，看哪兩個 $\texttt{x}$ 之間沒有 $\texttt{+}$，Greedy 的放即可
???+note "[全國賽模擬賽 2022 pI. 子集合和 (SOS)](https://www.csie.ntu.edu.tw/~b11902109/PreNHSPC2022/IqwxCSqc_Pre_NHSPC_zh_TW.pdf#page=25)"
令函數 $f(S)=S\times \prod\limits_{x\in S}x$，問 $\sum\limits_{S\subseteq A} f(S)$
$1\le n\le 10^6, 1\le a_i\le 10^9$
??? note "思路"
令 $G(S)=\prod \limits_{x\in S} x,\space F(S) =|S| \times \prod \limits_{x\in S} x$
則
$\begin{align}F(S \cup \{t \}) &= (|S|+1)\times \left(\prod \limits_{x\in S} x \right)\times t \\ &= F(S) \times t+G(S)\times t\end{align}$
$G(S \cup \{ t\})=G(S)\times t$
假設我們已知 $\sum \limits_{S \subseteq A}F(S)$ 和 $\sum \limits_{S \subseteq A}G(S)$，則我們可將新的 $F=$ 沒有 $t$ + 有 $t$
$\begin{align}\sum \limits_{S \subseteq (A + \{t \})}F(S) &= \sum \limits_{S \subseteq A}F(S)+\sum \limits_{S \subseteq A}F(S+\{ t \}) \\ &= \sum \limits_{S \subseteq A}F(S)+\left(\sum \limits_{S \subseteq A}F(S) \right)\times t + \left(\sum \limits_{S \subseteq A}G(S) \right)\times t\end{align}$
$\sum \limits_{S \subseteq (A + \{t \})}G(S)=\sum \limits_{S \subseteq A}G(S)+\left(\sum \limits_{S \subseteq A}G(S) \right)\times t$
---
> 參考自 : <https://hackmd.io/@victor26/Bkc_YXpdo>
觀察到可能跟 $(a_1 + 1)(a_2 + 1)(a_3 + 1) \ldots (a_n + 1)$ 有關
答案為
$$a_1(a_2 + 1)(a_3 + 1) \ldots (a_n + 1)+a_2(a_1 + 1)(a_3 + 1) \ldots (a_n + 1) + a_n(a_1 + 1)(a_2 + 1) \ldots (a_{n-1} + 1)$$
預處理 $(a_1+1)(a_2+1)(a_3+1)...(a_n+1)$ 即可
???+note "[CF 1886 D. Monocarp and the Set](https://codeforces.com/contest/1886/problem/D)"
問符合條件的 $1\ldots n$ 的 permutation $p$ 有幾個。給一個長度為 $(n-1)$ 的序列 $s$，$s_i$ 的意義如下 :
- 若 $s_i=$ `>`，則 $p_i$ 是前綴的 max
- 若 $s_i=$ `<`，則 $p_i$ 是前綴的 min
- 若 $s_i=$ `?`，則 $p_i$ 兩者皆不是
現在有 $q$ 筆對 $s$ 的單點修改，每次修改完輸出答案是多少
$2\le n\le 3\times 10^5, 1\le m\le 3\times 10^5$
??? note "思路"
考慮列出 $p_0,\ldots ,p_{n-1}$ 的大小關係，例如 $[2,1,5,3,4]$ 的大小關係為 $p_1<p_0<p_3<p_4<p_2$。
- 若當前加入一個 `>` ，他只能放在大小關係的最後面。
- 若當前加入一個 `<`，他只能放在大小關係的最前面。
- 若當前加入一個 `?`，他可以放在大小關係的中間。
所以實際上整體的變動是由 `?` 決定的，因此，總可能性是所有 $(i-1)$ 的乘積，其中 $s_i$ == `?`（1-based）
舉例來說，$s=$ `<?>?`
- $s_1=$ `<` 則 $p_1<p_0$
- $s_2=$ `?` 則 $p_2$ 只能插入在 $p_1,p_0$ 之間，所以 $p_1<p_2<p_0$
- $s_3=$ `>` 則 $p_1<p_2<p_0<p_3$
- $s_4=$ `?` 則 $p_4$ 可以插入在中間 $3$ 個空隙中
所以答案為 $(2-1)\times (4-1)=3$
???+note "[2021 附中模競 III pF. 歡樂耶誕城 (Christmas)](https://codeforces.com/group/3Xn3T5DO0a/contest/375522/problem/F)"
有 $n$ 條燈飾，一開始上面都沒燈泡，燈泡有 $m$ 種顏色，有以下 $q$ 次操作:
1. 將指定顏色的燈泡加到指定燈飾的尾端
2. 移除某條燈飾的最後一個燈泡
3. 把某條燈飾變成跟另一條一模一樣
4. 問某條燈飾的某個燈泡是什麼顏色
$n,q\le 2\times 10^5, m\le 10^9$
??? note "思路"
把某條燈飾複製後，各自可以再延伸 ⇒ 類似 Tree 的結構
用 1. 2. 3. 操作讀進來後建立完 tree 後，建 lca，對於 4. O(log n) 回答
???+note "[CF 1644 E. Expand the Path](https://codeforces.com/problemset/problem/1644/E)"
有一個 n * n 的 Grid，給一個字串 s，包含 D, R，代表當前行走的路徑。可任意次的將 s 的某一項複製，但 s 不能超界，問能走到的 distinct 格子數量
$n\le 10^8, |s| \le 2\times 10^5$
??? note "思路"
【套路】: 對於每一個 s 的走過的位置，計算對全局的貢獻
首先，我們按照給定的操作序列執行，到達目標格子 (x, y)。然後，計算在該位置最多可以向橫向或縱向移動多少格，以達到目標位置 (n, m)。設需要向右移動 x 格，向下移動 y 格。
在接下來的分析中，為方便起見，我們將格子與格子之間的操作轉化為格子內部的操作。例如，如果當前在 (1, 1)，需要向右移動，則我們將該格子標記為右移。當然，這樣做可能會漏掉一個格子，但後面會進行補充。
考慮計算答案。對於每個格子，我們最多可以向相對方向（例如，如果格子是向右的，則考慮向下移動）移動 x 或 y 格。由於移動一定是向右或向下的，擴展過程不會超出邊界或與其他格子重疊，因此我們可以直接將這些貢獻添加到答案中。
需要注意的是，只有在第一次轉向及以後才能執行這樣的操作（因為沒有辦法複製另一種方向的操作）。
然後，考慮最後一個格子。不難發現，從右下角開始的 n * m 個格子都可以到達，我們直接將其添加到答案中。
??? note "code"
```cpp linenums="1"
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 5;
char s[N];
int n, ans;
void work() {
bool flag = 1;
cin >> n >> s + 1;
int x = 1, y = 1;
for (int i = 1; s[i]; i++) {
if (s[i] == 'R') {
x++;
} else {
y++;
}
if (s[i] != s[i - 1] && i != 1) flag = 0;
}
if (flag == 1) {
cout << n << '\n';
return;
}
x = n - x, y = n - y;
int i = 2;
ans = 1;
while (s[i] == s[i - 1]) {
ans++;
i++;
}
for (i; s[i]; i++) {
ans++;
if (s[i] == 'R') {
ans += y;
} else {
ans += x;
}
if (s[i + 1] == 0) ans += (x + 1) * (y + 1);
}
cout << ans << '\n';
}
int main() {
int t;
cin >> t;
while (t--) work();
}
```
???+note "[CF 1644 D. Cross Coloring](https://codeforces.com/contest/1644/problem/D)"
給一個 n * m 的 grid，每格最初都是白色的。有 q 筆操作:
- color$(x_i, y_i):$ 選擇 k 種非白色的顏色的其中一種，然後將 row $x_i$ 與 $y_i$ 塗色
問整張 grid 有幾種塗色方案數
$n,m,k,q\le 2\times 10^5$
??? note "思路"
如果倒著考慮，題目就變成: 每次選一行一列，然後染成一個顏色，後染的色不會覆蓋原來染得顏色。
那麼當一次操作會沒有貢獻，當且僅當 row 跟 column 都被完全覆蓋，否則，答案就需要乘上 k。
同時我們還需要考慮一種情況，當有 n 行全部被覆蓋時，實際上相當於 m 列全部被覆蓋了；反之亦然。此後的所有操作都將變為無效操作。
??? note "code"
```cpp linenums="1"
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 2e5 + 5;
const int mod = 998244353;
bool row[MAXN], col[MAXN];
int x[MAXN], y[MAXN];
int fpow(int a, int b) {
int res = 1;
while (b) {
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
int main() {
int t;
cin >> t;
while (t--) {
memset(row, 0, sizeof(row));
memset(col, 0, sizeof(col));
int n, m, k, q;
cin >> n >> m >> k >> q;
for (int i = 1; i <= q; i++) {
cin >> x[i] >> y[i];
}
int cnt = 0, crow = 0, ccol = 0;
for (int i = q; i >= 1; i--) {
bool ok = 0;
if (crow < n && ccol < m && !row[x[i]]) {
row[x[i]] = 1, crow++, ok = 1;
}
if (crow < n && ccol < m && !col[y[i]]) {
col[y[i]] = 1, ccol++, ok = 1;
}
if (ok) cnt++;
}
cout << fpow(k, cnt) << '\n';
}
}
```
???+note "[CF 1928 D. Lonely Mountain Dungeons](https://www.luogu.com.cn/problem/CF1928D)"
有 $n$ 類人，第 $i$ 類人有 $c_i$ 個。你需要 $x\cdot(k-1)$ 的代價把他們分成 $k$ 組。在一種分組下，每兩個同類的人被分到不同的組，會產生 $b$ 的貢獻。問最大收益。
$n\leq 2\times 10^5, 1\leq c_i \leq 2\times 10^5, b\leq 10^6, x\leq 10^9, \sum c_i \leq 2\times 10^5$
??? note "思路"
設 f(n, m) 是將 n 個同種族的人放到 m 組中可以獲得的貢獻。可以發現在同組的人不能互相產生貢獻，所以盡可能平均分配是最優的。設 p = (n / m), q = n % m，則有 m - q 的隊伍有 p 人，q 個隊伍有 p + 1 人，所以貢獻是
$$
f(n, m) =\dfrac{n(n+1)}{2}-(m-q)\times\dfrac{p(p+1)}{2}-q\times\dfrac{(p+1)(p+2)}{2}
$$
一種想法是因為 $\sum c_i \le 2\times 10^5$，所以 distinct 的 $c_i$ 總共也就 $\sqrt{2\times 10^5}$ 種，所以我們枚舉分成幾組，然後枚舉每種種族的人， 將他們的 f(n, m) 算進去答案，最後取 max 就好，複雜度 $O(n \sqrt{\sum c_i})$。
另一種想法是對於一個種族，直接枚舉 $m=1\ldots c_i$ 代表要分成 $m$ 組能產生的貢獻，利用前綴和單點加值的想法，對於 $m=1\ldots c_i$ 我們就直接套上面 f(n, m) 分別計算就好，而 $m>c_i$ 就相當於 f(c[i], c[i])，複雜度 $O(\sum c_i)$。
> 參考自: <https://www.cnblogs.com/int-R/p/18013982/CF1928D>