题目链接：点我啊╭(╯^╰)╮
n ∗ n n * n n∗n 的图， m m m 次操作，规定第 k k k 列为特殊列 每次操作选定一个 ( x , y ) (x, y) (x,y)，若没有棋子则出现一颗棋子，反之消失 棋子 ( x , y ) (x, y) (x,y) 只能往 ( x + 1 , y − 1 ) 、 ( x + 1 , y ) 、 ( x + 1 , y + 1 ) (x+1, y-1)、(x+1, y)、(x+1, y+1) (x+1,y−1)、(x+1,y)、(x+1,y+1) 三个方向走 所有棋子都必须走到第 k k k 列，若棋盘的行数不够，可以增加行 每个位置最多只能放一颗棋子 问所有棋子都到第 k k k 列后，增加的最小行数
棋子 ( x , y ) (x, y) (x,y) 走到第 k k k 列时，最小的行数为 x + a b s ( y − k ) x + abs(y - k) x+abs(y−k) 这样就知道了所有棋子走到第 k k k 列时行的位置 但是重复的位置要继续往上走，彼此之间相互影响，很难维护
设 f ( j ) f(j) f(j) 为 第 j j j 行以上有多少颗棋子 那么 n n n 行的棋盘能装下的话，需满足： f ( j ) < = n − j + 1 f(j) <= n - j + 1 f(j)<=n−j+1 转移过来就是 f ( j ) − n + j − 1 f(j) - n + j - 1 f(j)−n+j−1，表示的就是至少需要增加的行数 答案就是： max 1 < = j < = p o s m a x f ( j ) − n + j − 1 \max\limits_{1<=j<=pos_{max}} f(j) - n + j - 1 1<=j<=posmaxmaxf(j)−n+j−1 因此每次增加或删除一颗棋子，更新前缀 + 1 +1 +1 或 − 1 -1 −1 即可 用线段树维护，初始值为 j − 1 j-1 j−1，最后 − n -n −n p o s m a x pos_{max} posmax表示出现的棋子里最大的行
#include<bits/stdc++.h> #define rint register int #define deb(x) cerr<<#x<<" = "<<(x)<<'\n'; using namespace std; typedef long long ll; typedef pair <int,int> pii; const int maxn = 4e5 + 5; int n, m, k, t[maxn<<2]; int lz[maxn<<2], cnt[maxn]; void build(int l, int r, int rt) { if(l == r) { t[rt] = l - 1; return; } int mid = l + r >> 1; build(l, mid, rt<<1); build(mid+1, r, rt<<1|1); t[rt] = max(t[rt<<1], t[rt<<1|1]); } void pushdown(int rt) { if(lz[rt] != 0) { t[rt<<1] += lz[rt], t[rt<<1|1] += lz[rt]; lz[rt<<1] += lz[rt], lz[rt<<1|1] += lz[rt]; lz[rt] = 0; } } void update(int L, int R, int c, int l, int r, int rt) { if(l>R || r<L) return; if(l>=L && r<=R) { t[rt] += c, lz[rt] += c; return; } pushdown(rt); int mid = l + r >> 1; update(L, R, c, l, mid, rt<<1); update(L, R, c, mid+1, r, rt<<1|1); t[rt] = max(t[rt<<1], t[rt<<1|1]); } int query(int L, int R, int l, int r, int rt) { if(l>R || r<L) return 0; if(l>=L && r<=R) return t[rt]; pushdown(rt); int mid = l + r >> 1, ret = 0; ret = max(ret, query(L, R, l, mid, rt<<1)); ret = max(ret, query(L, R, mid+1, r, rt<<1|1)); t[rt] = max(t[rt<<1], t[rt<<1|1]); return ret; } signed main() { scanf("%d%d%d", &n, &k, &m); build(1, n<<1, 1); set <pii> p; set <int> mx; while(m--) { int x, y; scanf("%d%d", &y, &x); int pos = x + abs(y - k); if(p.count({x, y})) { cnt[pos]--; if(cnt[pos] == 0) mx.erase(pos); p.erase({x, y}); update(1, pos, -1, 1, n<<1, 1); } else { cnt[pos]++; mx.insert(pos); p.insert({x, y}); update(1, pos, 1, 1, n<<1, 1); } if(mx.empty()) puts("0"); else printf("%d\n", max(query(1, *mx.rbegin(), 1, n<<1, 1) - n, 0)); } }