牛客練習賽125 E 聯誼活動（枚舉，分討）

????????? 題面：

題目

分析：

????????? 發現選用距離矩形越近的關鍵點答案會越優。注意到 $x,y$ 的取值范圍很小，我們對于每一個位置處理出 在它所在的行中，離它最近的左邊 / 右邊 的關鍵點，然后每次詢問可以掃描 $S_x～E_x$ 行，設當前行是 $line$，查詢 $(line,S_y)$ 這個位置左右最近的關鍵點，分別拿這兩個關鍵點去更新答案即可。時間復雜度 $O(m\times x+x\times y)$。
CODE：

#include<bits/stdc++.h>
using namespace std;
const int M = 1100;
const int N = 1e5 + 10;
int n, m, sx, sy, ex, ey, px[N], py[N];
int Left[M][M], Right[M][M];
bool f[M][M];
void pre_work() {memset(Left, -1, sizeof Left);memset(Right, -1, sizeof Right);for(int i = 1; i <= 1000; i ++ ) {int now = -1;for(int j = 1; j <= 1000; j ++ ) {if(f[i][j]) now = max(now, j);Left[i][j] = now;}now = 1001;for(int j = 1000; j >= 1; j -- ) {if(f[i][j]) now = min(now, j);Right[i][j] = (now == 1001 ? -1 : now);}}
}
int solve(int sx, int sy, int ex, int ey) {int res = 1e9, c = abs(sx - ex) + abs(sy - ey);for(int i = 1; i <= 1000; i ++ ) { // 掃描每一層 if(i < min(sx, ex)) {int tx = i, ty = min(sy, ey);if(Left[tx][ty] != -1) res = min(res, 2 * (min(sy, ey) - Left[tx][ty]) + 2 * (min(sx, ex) - i) + c);if(Right[tx][ty] != -1) {if(Right[tx][ty] <= max(sy, ey)) res = min(res, 2 * (min(sx, ex) - i) + c);else res = min(res, 2 * (Right[tx][ty] - max(sy, ey)) + 2 * (min(sx, ex) - i) + c);}}else if(i >= min(sx, ex) && i <= max(sx, ex)) {int tx = i, ty = min(sy, ey);if(Left[tx][ty] != -1) res = min(res, 2 * (min(sy, ey) - Left[tx][ty]) + c);if(Right[tx][ty] != -1) {if(Right[tx][ty] <= max(sy, ey)) {res = min(res, c);break;}else res = min(res, 2 * (Right[tx][ty] - max(sy, ey)) + c);}}else {int tx = i, ty = min(sy, ey);if(Left[tx][ty] != -1) res = min(res, 2 * (min(sy, ey) - Left[tx][ty]) + 2 * (i - max(sx, ex)) + c);if(Right[tx][ty] != -1) {if(Right[tx][ty] <= max(sy, ey)) res = min(res, 2 * (i - max(sx, ex)) + c);else res = min(res, 2 * (Right[tx][ty] - max(sy, ey)) + 2 * (i - max(sx, ex)) + c);}			}}return res;
}
int main() {scanf("%d%d", &n, &m);for(int i = 1; i <= n; i ++ ) {scanf("%d%d", &px[i], &py[i]);f[px[i]][py[i]] = 1;}pre_work();for(int i = 1; i <= m; i ++ ) {scanf("%d%d%d%d", &sx, &sy, &ex, &ey);printf("%d\n", solve(sx, sy, ex, ey));}return 0;
}

牛客練習賽125 F 玻璃彈珠（類莫隊，離線詢問，數據結構）

????????? 題面：

題目

分析：
????????? 在線處理很難在允許的時間復雜度內通過，我們考慮 離線：發現題目上給的 區間不相交 這一條性質，啟示我們像莫隊一樣通過兩個 指針 來不斷更新當前維護區間的信息。具體來講：設 $lt$，$rt$ 分別是當前區間的左右端點。將查詢區間離線后按照左端點排序，通過指針的逐步跳轉實現維護區間的改變。由于指針 只會向后跳，因此最多跳 $n$ 次，這一部分復雜度是 $O(n)$ 的。我們考慮怎樣維護當前區間的信息：一個操作 $1$ 顯然會在它的左端點第一次被用到，在它的右端點處作用消失。因此我們將每一個操作 $1$ 的信息分別存進區間的做右端點內。左端點處為 添加 信息，當 $rt$ 經過左端點時將這個信息加入數據結構中。右端點處為 刪除 信息，當 $lt$ 經過右端點時將信息從數據結構中刪除。這樣就解決了 位置 這一偏序。每條信息形如 某種顏色 $c$ 在時間 $t$ 時出現。由于 只有最小的 $t$ 有用，添加時我們把 $t$ 插入 $c$ 對應的 $set$ 里， 刪除時把它從 $set$ 里刪掉。然后在 以時間為下標的樹狀數組 里更新不同最早時間出現的顏色數量。查詢時查找 小于當前查詢區間時間的前綴和 即可。
時間復雜度： $O(mlo{g}_{2}m)$。

CODE:

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef pair< int, int > PII;
const int N = 5e5 + 10;
int n, m, op, l, r, col, tot;
struct BIT {int c[N];int lowbit(int x) {return x & -x;}void add(int x, int y) {for(; x < N; x += lowbit(x)) c[x] += y;}int ask(int x) {int res = 0;for(; x; x -= lowbit(x)) res += c[x];return res;}
}t;
vector< PII > A[N], D[N];
set< int > tc[N]; // 維護當前區間所有涉及的加顏色操作所帶來的每種顏色的時間戳
struct range {int l, r, tim, ans;
}q[N];
bool cmp(range x, range y) {return x.l < y.l;
}
void add(int x) {for(auto v : A[x]) {int col = v.first, tim = v.second;if(!tc[col].empty()) {auto it = tc[col].begin();int Tim = (*it); t.add(Tim, -1);}tc[col].insert(tim);auto it = tc[col].begin();int T = (*it);t.add(T, 1);} 
}
void del(int x) {for(auto v : D[x]) {int col = v.first, tim = v.second;if(!tc[col].empty()) {auto it = tc[col].begin();int Tim = (*it);t.add(Tim, -1);}tc[col].erase(tim);if(!tc[col].empty()) {auto It = tc[col].begin();int Gm = (*It);t.add(Gm, 1);}}
}
bool cmp2(range x, range y) {return x.tim < y.tim;
}
int main() {scanf("%d%d", &n, &m);for(int i = 1; i <= m; i ++ ) {scanf("%d", &op);if(op == 1) {scanf("%d%d%d", &l, &r, &col);A[l].pb(make_pair(col, i));D[r].pb(make_pair(col, i));}else {scanf("%d%d", &l, &r);q[++ tot] = (range) {l, r, i};}}sort(q + 1, q + tot + 1, cmp);int lt = 1, rt = 0;for(int i = 1; i <= tot; i ++ ) {while(rt < q[i].r) {++ rt; add(rt);}while(lt < q[i].l) {del(lt); lt ++;}q[i].ans = t.ask(q[i].tim);}sort(q + 1, q + tot + 1, cmp2);for(int i = 1; i <= tot; i ++ ) {printf("%d\n", q[i].ans);}return 0;
}

啟示：遇到存在 時間 和 位置 兩種限制的詢問和修改，可考慮如果修改可以離線（與在線狀態無關）。那么可以將操作離線，按照位置進行 雙指針 或者 莫隊 跳動，在滿足位置限制的同時用 數據結構 來維護時間限制。

2024ccpc長春邀請賽 D Parallel Lines（隨機化）

????????? 題目

????????? 分析：考慮如果我們求出一個 斜率，如何檢驗這個斜率是否正確。一個很好的思路是對每個點算出在這個斜率下經過該點的直線的縱截距，然后判斷是否有 $k$ 個不同的縱截距以及每個縱截距是否對應大于等于 $2$ 個不同的點即可。時間復雜度 $O(n)$。如果枚舉兩個點去算斜率，那么時間復雜度為 $O(n^2)$，顯然不能接受。我們發現平行線的數量很少，意味著有較多的點在同一條直線上。直接隨機出兩個點算斜率并判斷是否合法。可以證明隨機出合法點對的最小概率為 $O(\frac{1}{k})$。所以可以在 $O(k)$ 次隨機出合法的點對，總時間復雜度為 $O(n\times k)$。

CODE:

#include<bits/stdc++.h>// 隨機化 
#define pb push_back
using namespace std;
const int N = 1e4 + 10;
const int K = 51;
typedef double db;
int n, k, tot, cnt[N];
db X[N], Y[N];
const db INF = 1e18;
map< db, int > mp;
vector< int > node[N];
int random(int n) {return ((unsigned long long)rand() * rand() % n);
}
db B(int p, int q, db x, db y) {if(X[p] == X[q]) return x;else return (X[q] - X[p]) * y - (Y[q] - Y[p]) * x;
}
bool check(int p, int q) {tot = 0; memset(cnt, 0, sizeof cnt);for(int i = 1; i <= n; i ++ ) {db b = B(p, q, X[i], Y[i]);if(!mp[b]) mp[b] = ++ tot;cnt[mp[b]] ++;}bool f = 1;for(int i = 1; i <= n; i ++ ) {db b = B(p, q, X[i], Y[i]);if(cnt[mp[b]] == 1) {f = 0; break;}}if(tot == k && f) {for(int i = 1; i <= n; i ++ ) {db b = B(p, q, X[i], Y[i]);node[mp[b]].pb(i);}return 1;}for(int i = 1; i <= n; i ++ ) {db b = B(p, q, X[i], Y[i]);mp[b] = 0;}return 0;
}
int main() {srand(time(0));scanf("%d%d", &n, &k);for(int i = 1; i <= n; i ++ ) {scanf("%lf%lf", &X[i], &Y[i]);} while(true) {int i = random(n) + 1, j = random(n) + 1;if(i == j) continue;else if(check(i, j)) {for(int i = 1; i <= tot; i ++ ) {printf("%d", node[i].size());for(int j = 0; j < node[i].size(); j ++ ) printf(" %d", node[i][j]);puts("");}break;}}return 0;
}

2024ccpc長春邀請賽 E Connected Components（單調棧）

題目

????????? 分析：
????????? 不難想到將式子移項，將只含 $i$ 的放一起，將只含 $j$ 的放一起。我們可以得到 $i$ 與 $j$ 之間有連邊，當且僅當：

$a_i?i\le a_j?j，b_i?i\ge b_j?j$ 或者 $a_i?i\ge a_j?j，b_i?i\le b_j?j$ 。這兩個式子可以看作 $j$ 往 $i$ 連邊 或 $i$ 往 $j$ 連邊。我們令 $x_i=a_i?i$， $y_i=b_i?i$，那么 $i$ 往 $j$ 連邊的條件就是 $x_i\ge x_j，y_i\le y_j$。將元素按照 $x$ 從小到大排序，那么每種元素只可能往前邊連邊。我們使用 單調棧 維護 $y$。從前往后往棧里加入元素，那么只有 $y_i$ 小于棧頂元素的 $y$ 時 $i$ 才能往棧頂元素所在連通塊連邊。我們考慮此時將棧頂元素彈出，然后接著比較直到 $y_i$ 大于棧頂元素的 $y$。接下來存在一個問題：由于棧頂元素的 $y$ 越大越容易連邊，而我們剛把 $y$ 元素較大的棧頂元素彈出，此時 $i$ 一定與剛剛彈出的棧頂元素在同一個連通塊中，如果僅僅把 $i$ 放進棧中，那么后面的元素就有可能沒有連上原來和這個連通塊的邊。想到一個連通塊的 $y$ 只有最大的有用，因此我們每次拿 $y_i$ 和棧頂元素所在聯通塊的的最大 $y$ 比較來判斷是否連邊就不會錯。注意連邊的時候更新連通塊的最大 $y$ 值。
時間復雜度 $O(n)$

CODE:

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, sz[N], bin[N], mh[N], p, q;
struct element {int x, y;
}a[N];
bool cmp(element u, element v) {return ((u.x < v.x) || (u.x == v.x && u.y > v.y));
}
stack< int > s;
int Find(int x) {return x == bin[x] ? x : bin[x] = Find(bin[x]);}
void Merge(int x, int y) {int f1 = Find(x), f2 = Find(y);bin[f2] = f1; sz[f1] += sz[f2];mh[f1] = max(mh[f2], mh[f1]);
}
int main() {scanf("%d", &n);for(int i = 1; i <= n; i ++ ) {scanf("%d%d", &p, &q);a[i].x = p - i;a[i].y = q - i;}sort(a + 1, a + n + 1, cmp);for(int i = 1; i <= n; i ++ ) {bin[i] = i; sz[i] = 1;mh[i] = a[i].y;}for(int i = 1; i <= n; i ++ ) {while(!s.empty() && a[i].y <= mh[Find(s.top())]) {Merge(i, s.top());s.pop();}s.push(i);}int cnt = 0;for(int i = 1; i <= n; i ++ ) {if(Find(i) == i) cnt ++;}cout << cnt << endl;return 0;
}

2024ccpc長春邀請賽 B Dfs Order 0.5（動態規劃）

題目

????????? 分析：
????????? 為了方便，我們把子樹大小為 偶數 的點稱作 偶點，奇數 的點稱作 奇點。 偶兒子 與 奇兒子 的稱呼類似。
????????? 容易想到狀態定義 $d{p}_{i,0/1}$ 表示 $i$ 點的 $dfn$ 序為偶數/奇數時， 以 $i$ 為根的子樹的最大權值和。考慮轉移，分兩類情況：

1. 存在 奇兒子：那么每個偶兒子可以選 $0/1$ 中較大的。設點 $i$ 的狀態為 $t$，奇兒子的數量為 $m$，那么顯然有 $?\frac{m}{2}?$ 個奇兒子需要選 $t\oplus 1$，另外的選 $t$。那么只需要將所有 $d{p}_{son,t\oplus 1}?d{p}_{son,t}$ 拿出來從大到小排序，選出前$?\frac{m}{2}?$ 大，并把所有 $d{p}_{son,t}$ 累加即可。
2. 不存在 奇兒子：那么所有兒子的狀態都只能是 $t\oplus 1$，加起來就好了。

CODE:

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 2e5 + 10; 
typedef long long LL;
int n, T, u, v, sz[N];
LL a[N], dp[N][2];
vector< int > E[N];
bool cmp(LL x, LL y) {return x > y;
}
void dfs(int x, int fa) {sz[x] = 1;if(E[x].empty()) {dp[x][0] = a[x];dp[x][1] = 0;return ;}bool flag = 0;for(auto v : E[x]) {if(v == fa) continue;dfs(v, x); sz[x] += sz[v];if(sz[v] & 1) flag = 1;}if(flag) { // 存在奇點   所有偶點取較大 LL tmp = 0, tg = 0, th = 0;int cnt = 0;vector< LL > g, h;for(auto v : E[x]) {if(v == fa) continue;if(sz[v] & 1) {g.pb(dp[v][0] - dp[v][1]);tg += dp[v][1];h.pb(dp[v][1] - dp[v][0]);th += dp[v][0];cnt ++;}else tmp += max(dp[v][0], dp[v][1]);}sort(g.begin(), g.end(), cmp);sort(h.begin(), h.end(), cmp);LL c = 0;for(int i = 1; i <= ((cnt & 1) ? (cnt + 1) / 2 : cnt / 2); i ++ ) c += h[i - 1];dp[x][0] = tmp + th + c + a[x];c = 0;for(int i = 1; i <= ((cnt & 1) ? (cnt + 1) / 2 : cnt / 2); i ++ ) c += g[i - 1];dp[x][1] = tmp + tg + c;}else {dp[x][0] = dp[x][1] = 0;dp[x][0] += a[x];for(auto v : E[x]) {if(v == fa) continue;dp[x][0] += dp[v][1];dp[x][1] += dp[v][0];}}
}
void solve() {scanf("%d", &n);for(int i = 1; i <= n; i ++ ) scanf("%lld", &a[i]);for(int i = 1; i <= n; i ++ ) dp[i][0] = dp[i][1] = 0;	for(int i = 1; i <= n; i ++ ) {vector< int > tmp; swap(tmp, E[i]);}for(int i = 1; i < n; i ++ ) {scanf("%d%d", &u, &v);E[u].pb(v); E[v].pb(u);}dfs(1, 0);printf("%lld\n", dp[1][1]);
}
int main() {scanf("%d", &T);while(T -- ) {solve();}return 0;
}

2024 CCPC東北邀請賽 H. Meet（二分答案，樹上公共祖先，樹上差分）

題目

????????? 分析：
????????? 直接求解最優答案顯然不好搞，我們發現答案越大越容易滿足，因此具有單調性，可以二分答案。設 $x$ 為二分的答案，考慮怎樣檢驗：

????????? 實際上這個問題等價于是否至少存在一個點 $p$，使得 $p$ 作為根時所有點對到它們 $lca$ 的距離都小于 $x$。

????????? 由于 $u，v$ 的 $lca$ 一定在它們的路徑上，我們考慮選取不同點作為根時 $u，v$ 的 $lca$ 有什么規律。

????????? 如果以紅色點為樹根，那么 $u,v$ 的 $lca$ 就是 $u?v$ 路徑上紅色點的祖先。也就是說：如果我們首先以任意一個點為根，那么檢驗時選取作為根的點在$u?v$路徑上哪個點的子樹中，那個點就是真正的 $lca$。如果選取的點在子樹外，那么當前的 $lca$ 就是真正的 $lca$。

????????? 對于二分出的答案 $x$，我們可以對于點對中的每個點算出 路徑上那些點可以作為 $lca$。那么這些點子樹中的點都可以作為選定根。我們把包含這些點的最小子樹加 $1$，最后判斷上是否有點的權值等于 $2\times m$ 即可。

時間復雜度 $O(nlo{g}_{2}n)$。

CODE：

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 1e5 + 10;
inline int read() {int x = 0, f = 1; char c = getchar();while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();}while(isdigit(c)) {x = (x << 1) + (x << 3) + (c ^ 48); c = getchar();}return x * f;
}
int n, m, u, v, pu[N], pv[N], dfn[N], fat[N][25], dep[N], rk;
int L[N], R[N];
vector< int > E[N];
struct BIT {int c[N];void Clean() {memset(c, 0, sizeof c);}int lowbit(int x) {return x & -x;}void add(int x, int y) {for(; x < N; x += lowbit(x)) c[x] += y;}int ask(int x) {int res = 0;for(; x; x -= lowbit(x)) res += c[x];return res;}
}t;
void dfs0(int x, int fa) {dfn[x] = ++ rk; dep[x] = dep[fa] + 1;fat[x][0] = fa; L[x] = rk;for(int i = 1; i <= 20; i ++ ) fat[x][i] = fat[fat[x][i - 1]][i - 1];for(auto v : E[x]) {if(v == fa) continue;dfs0(v, x);} R[x] = rk;
}
int LCA(int x, int y) {if(dep[x] < dep[y]) swap(x, y);for(int i = 20; i >= 0; i -- ) {if(dep[fat[x][i]] >= dep[y]) x = fat[x][i];}if(x == y) return x;for(int i = 20; i >= 0; i -- ) {if(fat[x][i] != fat[y][i]) x = fat[x][i], y = fat[y][i];}return fat[x][0];
}
int Kth(int x, int k) {for(int i = 20; i >= 0; i -- ) {if((k >> i) & 1) x = fat[x][i];}return x;
} 
void OP(int u, int v, int len) {int lca = LCA(u, v);if(dep[u] + dep[v] - 2 * dep[lca] <= len) t.add(1, 1);else if(dep[u] - dep[lca] > len) {int ancestor = Kth(u, len);t.add(L[ancestor], 1);t.add(R[ancestor] + 1, -1);}else {int ancestor = Kth(v, dep[v] - dep[lca] - (len + 1 - (dep[u] - dep[lca])));t.add(1, 1);t.add(L[ancestor], -1);t.add(R[ancestor] + 1, 1); }
}
bool check(int len) {t.Clean();for(int i = 1; i <= m; i ++ ) {OP(pu[i], pv[i], len); OP(pv[i], pu[i], len);}for(int i = 1; i <= n; i ++ ) {if(t.ask(i) == m * 2) return 1;}return 0;
}
int main() {n = read(), m = read();for(int i = 1; i < n; i ++ ) {u = read(), v = read();E[u].pb(v); E[v].pb(u);}for(int i = 1; i <= m; i ++ ) {pu[i] = read(), pv[i] = read();}dfs0(1, 0);int l = 0, r = 1e5 + 10, mid, res = -1;while(l <= r) {mid = (l + r >> 1);if(check(mid)) res = mid, r = mid - 1;else l = mid + 1;}printf("%d\n", res);return 0;
}

2024 CCPC東北邀請賽 I. Password（動態規劃）

題目

????????? 分析：
????????? 如果 $[i?k+1,i]$ 是一個 $1$ 到 $k$ 的排列，我們稱 $i$ 是一個 結尾。那么由于每個位置都需要在一個排列的區間中，因此有一個性質：兩個結尾的距離一定不超過 $k$。有了這個性質我們就可以 $dp$ 了。 設 $d{p}_i$ 表示只考慮前 $i$ 個位置，每個位置都是好的的并且第 $i$ 和位置是一個 結尾 的序列數。轉移考慮枚舉上一個結尾：

$d{p}_i={\sum }_{j=1}^{k}d{p}_{i?j}\times g_j$

????????? 這里 $g_j$ 是轉移系數。因為如果直接乘 $j！$，那么一定會有重復。這是因為沒有滿足 $i?j$ 是上一個結尾的轉移條件。如果乘 $j！$，那么會出現 $(i?j,i)$ 之間某個位置成為了一個結尾的情況，這樣就會多算。

????????? 考慮 $g_j$ 如何計算。思考 $g_j$ 的意義：現在有一個排列，你要在后面接 $j$ 個數字，使得最后一個位置作為右端點長度為 $k$ 的區間形成一個排列，并且前面沒有別的位置能作為右端點形成排列。那么根據 $g_j$ 的含義來容斥求 $g$。

$g_i=i!?{\sum }_{j=1}^{i?1}{g}_j$

????????? 這個式子可以理解為 總方案數減去不合法的方案數，其中 ${\sum }_{j=1}^{i?1}{g}_j$ 可以理解為 把不合法方案按照最前面能形成排列的位置分組 求貢獻。因為 $g_j$ 說明 $j$ 位置能形成排列，但是前面不能形成形成排列。因此是一個天然的劃分。這樣就能把所有不合法方案不重不漏計算在內了。

時間復雜度 $O(n\times k)$

#include<bits/stdc++.h> 
using namespace std;
const int N = 1e5 + 10;
const int K = 1e3 + 10;
typedef long long LL;
const LL mod = 998244353;
int n, k;
LL dp[N], g[K], fac[N];
int main() {scanf("%d%d", &n, &k);if(k > n) {puts("0"); return 0;}else {fac[0] = 1LL;for(int i = 1; i < N; i ++ ) fac[i] = (fac[i - 1] * (1LL * i)) % mod;g[1] = 1LL;for(int i = 2; i <= k; i ++ ) {g[i] = fac[i];for(int j = 1; j < i; j ++ ) { // 枚舉非法情況中，第一個提前匹配成排列的位置 g[i] = ((g[i] - g[j] * fac[i - j] % mod) % mod + mod) % mod;}}dp[k] = fac[k];for(int i = k + 1; i <= n; i ++ ) {for(int j = i - 1; j >= i - k; j -- ) {dp[i] = (dp[i] + dp[j] * g[i - j] % mod) % mod;}}printf("%lld\n", dp[n]);} return 0;
}

2024 CCPC東北邀請賽 K. Tasks（貪心，構造）

題目

????????? 分析：感覺思路挺不好想的。考慮按照煩躁值分組。首先 對于同組的，不能出現區間包含的情況。因為這樣會讓更大的那個區間不成立。然后就是在區間不互相包含的情況下，每個區間越長 越好。這樣可以讓煩躁值更大的區間更容易被包含。并且由于只需要讓每個區間的煩躁值等于包含它的區間的最大煩躁值 $+1$ 即可，因此 不需要考慮當前區間是否會包含煩躁值很大的區間從而影響合法性。知道了這兩個性質我們就可以對從小到大對每一層進行構造了。注意 每一層按照左端點排序后應從大到小 考慮，這樣才能構造出最優的方案。具體細節參見代碼。

時間復雜度：$O(n)$

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 1e6 + 10;
const int Limit = 1e6;
typedef pair< int, int > PII;
int n, l[N], b[N];
vector< int > F[N];
map< PII, int > ans;
inline int read() {int x = 0, f = 1; char c = getchar();while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();}while(isdigit(c)) {x = (x << 1) + (x << 3) + (c ^ 48); c = getchar();}return x * f;
}
void calc(int depth) {if(depth == 0) {int now = Limit;for(int i = F[depth].size() - 1; i >= 0; i -- ) {ans[make_pair(depth, F[depth][i])] = now;now --;}}else {if(F[depth - 1].empty()) {puts("-1");exit(0);}int nl = F[depth - 1].size() - 1; int nr = ans[make_pair(depth - 1, F[depth - 1][nl])];for(int i = F[depth].size() - 1; i >= 0; i -- ) {int p = F[depth][i];while(nl >= 0 && p < F[depth - 1][nl]) {nl --;if(nl != -1) nr = min(nr, ans[make_pair(depth - 1, F[depth - 1][nl])]);}if(nl == -1) {puts("-1"); exit(0);}else {if(p == F[depth - 1][nl] && nr == ans[make_pair(depth - 1, F[depth - 1][nl])]) nr --;if(nr >= p) {ans[make_pair(depth, p)] = nr;nr --;}else {puts("-1");exit(0);}}}}
}
int main() {n = read();for(int i = 1; i <= n; i ++ ) {scanf("%d%d", &l[i], &b[i]);F[b[i]].pb(l[i]);}for(int i = 0; i <= Limit; i ++ ) {sort(F[i].begin(), F[i].end());for(int j = 1; j < F[i].size(); j ++ ) {if(F[i][j] == F[i][j - 1]) {puts("-1");return 0;}}}for(int i = 0; i <= Limit; i ++ ) {if(F[i].empty()) continue;else calc(i);}for(int i = 1; i <= n; i ++ ) {printf("%d\n", ans[make_pair(b[i], l[i])]);}return 0;
}

2024 CCPC東北邀請賽 L. Bracket Generation（組合數學，數數）

題目

????????? 分析：連續的一對的 $($ 和 $)$，那它肯定是由一個 $1$ 操作產生的，其余的左括號和右括號肯定都是由 $2$ 操作產生。我們注意到所有的 $2$ 操作都有一個限制，那就是 必須在它括住的最后一個 $1$ 后才能使用。因此我們可以統計出有多少個 $1$ 操作，并統計出每個 $1$ 操作由多少個 所屬的 $2$ 操作。這里 所屬 就是必須在這個 $1$ 后才能出現的意思。那么對于每個 $1$ 操作內部的 $2$，首先有一個 階乘 的貢獻，表示內部不同的順序。由于 $1$ 操作只能向后面加，所以所有的 $1$ 操作的順序是定的，就是從左到右的順序。我們只需要再累乘起分別插入每組 $2$ 操作的貢獻即可。

時間復雜度 $O(n)$。

CODE：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
typedef long long LL;
const LL mod = 998244353;
int n, tot, cnt[N];
LL fac[N], inv[N], res;
char str[N];
LL Pow(LL x, LL y) {LL res = 1LL, k = x;while(y) {if(y & 1) res = (res * k) % mod;y >>= 1;k = (k * k) % mod;}return res;
}
LL C(int n, int m) {return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
int main() {scanf("%s", str + 1);n = strlen(str + 1);fac[0] = 1LL;for(int i = 1; i < N; i ++ ) fac[i] = fac[i - 1] * (1LL * i) % mod;inv[N - 1] = Pow(fac[N - 1], mod - 2LL) % mod;for(int i = N - 2; i >= 0; i -- ) inv[i] = inv[i + 1] * (1LL * (i + 1LL)) % mod; for(int i = 1; i <= n; i ++ ) {if(str[i] == '(' && str[i + 1] == ')') {tot ++; int c = 0;for(int j = i + 2; j <= n; j ++ ) {if(str[j] == ')') c ++;else break;}cnt[tot] = c;}}res = 1LL; int room = 0;for(int i = tot; i >= 1; i -- ) {res = (res * fac[cnt[i]]) % mod; // 內部2的貢獻 res = res * C(room + cnt[i], cnt[i]) % mod;room = room + cnt[i] + 1;}printf("%lld\n", res);return 0;
}

2024 CCPC東北邀請賽 G. Diamond（根號分治）

題目

????????? 分析：比較難的一道題。我們發現如果每次詢問的 $p$ 和 $q$ 數量比較少，那么每次詢問就可以暴力做。如果比較多，那么這樣的 $p$ 或者 $q$ 的數量就比較少。這啟示我們 根號分治。

????????? 注意到逆序對就是 小數前面的大數數量。我們給數量大于 $\sqrt{n}$ 的數編號，處理出 $f_{i,j}$ 表示第 $i$ 個位置前面編號為 $j$ 的數字個數，這個可以在 $O(n\sqrt{n})$ 的復雜度內處理出來。 然后我們處理出 $S_{i,j}$ 表示前 $i$ 個位置里每個值為 $a_i$ 的位置前面編號為 $j$ 的數字數量 的和。這個可以對每個位置記一個前驅求出來。最后計算答案是簡單的：只需要 $S$ 數組的前綴相減再減去 $[1,l?1]$ 對 $[l,r]$ 的貢獻即可。比較惡心的是這道題卡空間，可以將閾值設大來減小大數的數量。這樣可以優化空間。

時間復雜度 $O(n\sqrt{n})$。

CODE：

????????? 還沒調過就不放了。