AtCoder Beginner Contest 449 复盘笔记

比赛链接：AtCoder Beginner Contest 449
原始代码：7.22 目录
整理日期：2026-07-25

总结

题目	核心知识点	本次情况	复杂度
A - $\pi$	浮点数、圆面积	独立 AC	$O(1)$
B - Deconstruct Chocolate	模拟、维护当前矩形	独立 AC；因输入格式歧义感而向 AI 确认	$O(Q)$
C - Comfortable Distance	按字符分组、双指针、二分	知道双指针方向但两次写到一半；题解后复写并默写	$O(N)$（双指针）
D - Make Target 2	绝对值、分类计数、区间交	AI 题解后改看官方简洁做法，并独立过了一遍	$O(R-L+U-D+2)$
E - A += v	操作压缩、离线查询、Fenwick 树、倍增	AI 题解后抄写，再独立默写	$O(N+M\log M+Q\log Q+Q\log M)$
F - Grid Clipping	逆向思维、扫描线、区间并、multiset	AI 题解后抄写，再独立默写	$O(N\log N)$
G - Many Repunit Sum 2	repunit 恒等式、生成函数、组合恒等式	战略性放弃改错	参考实现 $O(N)$

这场最值得保留的经验：

1. 双指针不是“看到窗口就让两个指针一起走”。C 题必须先固定一个左端点，再维护它对应的合法右端点区间。
2. 面对绝对值或 max，优先按“谁取得最大值”分类。D 题按 $|x|>|y|$ 与 $|x|\le |y|$ 划分，比按八个象限讨论清楚得多。
3. 操作次数巨大时，先寻找一整段操作中不变的结构。E 题把 $10^{100}$ 次单步操作压缩成至多 $M$ 个频率阶段。
4. 统计“完全不含黑点”的方案时，可以反过来统计被至少一个黑点污染的方案并求补集。F 题进一步把二维矩形并压成扫描线上的动态一维区间并。
5. 代码短不代表题目简单。G 的五十多行实现压缩了很深的组合数学推导，当前不强行背公式是合理的。

---

A - $\pi$

题意

给定圆的直径 $D$，求圆的面积。允许绝对误差或相对误差不超过 $10^{-6}$。

约束：$1\le D\le100$。

思路

半径为

$$r=\frac D2,$$

因此面积为

$$S=\pi r^2=\pi\left(\frac D2\right)^2.$$

本题的小坑是输入给的是直径，不能直接把 $D$ 当半径。

我的代码

#include <bits/stdc++.h>
using namespace std;
const double pi=3.141592653589793;

void solve()
{
    double D;scanf("%lf",&D);
    double r=D/2;
    printf("%0.15lf",r*r*pi);
}

int main()
{
    solve();
    return 0;
}

易错点

• 题目给的是直径，不是半径。
• 输出浮点数时保留足够多的小数位即可，不要求与样例格式完全相同。
• 也可以用 acos(-1.0) 获得 $\pi$，避免手写常量。

---

B - Deconstruct Chocolate

题意

当前有一块 $H\times W$ 的矩形巧克力，共处理 $Q$ 次操作：

• 1 R：吃掉当前巧克力最底部的 $R$ 行；
• 2 C：吃掉当前巧克力最右侧的 $C$ 列。

每次输出本次吃掉的巧克力块数。题目保证每次吃完后仍至少剩一行或一列。

输入格式为什么容易误读

对话记录：B 题 DeepSeek 对话

样例中的

2 4
1 3

不是两行 (R,C)，而是两种不同的命令模板：

• 2 4 匹配 2 C，表示类型 $2$，此时 $C=4$；
• 1 3 匹配 1 R，表示类型 $1$，此时 $R=3$。

也就是说，每次查询的第一个数是操作类型，第二个数才是删除数量。原代码把它们命名为 R,C，恰好强化了误读；改成 op,x 后含义会直接很多。

模拟过程

维护当前剩余行数 $H$ 和列数 $W$：

• 类型 $1$：吃掉 $R\times W$ 块，再令 $H\leftarrow H-R$；
• 类型 $2$：吃掉 $H\times C$ 块，再令 $W\leftarrow W-C$。

关键不变量是：每次操作后剩余部分仍是一个矩形，所以只需记住当前的 $H,W$，不需要真的建立网格。

我的代码（整理变量名）

#include <bits/stdc++.h>
using namespace std;

void solve()
{
    int H,W,Q;
    cin>>H>>W>>Q;
    while(Q--)
    {
        //第一个数是操作类型,第二个数才是删除数量
        int op,x;
        cin>>op>>x;
        if(op==1)
        {
            cout<<W*x<<"\n";
            H-=x;
        }
        else
        {
            cout<<H*x<<"\n";
            W-=x;
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    solve();
    return 0;
}

易错点

• 面积使用的是操作发生前的当前尺寸。
• 类型 $1$ 删除行，所以乘当前列数；类型 $2$ 删除列，所以乘当前行数。
• R+1、C+1 是题目对剩余尺寸的保证，不是实际要删除的数量。

---

C - Comfortable Distance

题意

给定长度为 $N$ 的小写字符串 $S$，统计满足下列条件的下标对 $(i,j)$：

$$1\le i\le j\le N, \qquad S_i=S_j, \qquad L\le j-i\le R.$$

由于 $L\ge1$，实际一定有 $i<j$。

约束：$N\le5\times10^5$。

我的两次尝试为什么断层

对话记录：C 题 DeepSeek 对话

第一版知道要用双指针，但试图只维护一对全局的 i,j：找到一对相同字符后同时移动指针。问题是一个左端点可能对应很多合法右端点，只保留一对指针会漏掉大部分配对。

此外，原代码还有几个实现问题：

1. char s[] 是 base-0，却用 i=1..n 访问，跳过了 s[0] 并访问到 s[n]；
2. while(s[j]!=s[i]&&j<=n) 先访问 s[j] 再判断边界，条件顺序反了；
3. if(j>n) continue 没有推进 i，可能死循环；
4. 答案最多接近 $N(N-1)/2$，int ans 会溢出。

第二版按字符保存位置已经走到了正确方向，但 p1,p2 的语义没有定义清楚，也没有建立“固定左端点后统计整个合法右端点区间”的循环。

正确转化：先按字符分组

为每个字母保存它在字符串中的全部位置。设某个字母的位置数组为

$$p_0<p_1<\cdots<p_{m-1}.$$

其中 $p_j$ 表示这个字母第 $j+1$ 次出现时的字符串下标；上式只是说这些下标按从左到右严格递增。

固定左端点 $p_i$ 后，合法右端点满足

$$p_i+L\le p_j\le p_i+R.$$

如果第一个满足下界的位置为 p1，最后一个满足上界的位置为 p2，那么本次贡献就是

$$\max(0,p2-p1+1).$$

这一步是原思路缺失的核心：不是找“一对”下标，而是为每个左端点统计一整段右端点。

二分写法

有序数组上可直接使用：

int left=lower_bound(v.begin(),v.end(),v[i]+L)-v.begin();
int right=upper_bound(v.begin(),v.end(),v[i]+R)-v.begin();
ans+=right-left;

lower_bound(x) 返回第一个 >=x 的位置；upper_bound(x) 返回第一个 >x 的位置。因此 [left,right) 恰好包含所有 $\le v_i+R$ 的位置，不必判断 $v_i+R$ 是否真的出现在数组中，也不必手动决定是否加一。

复杂度为 $O(N\log N)$。

双指针为什么能做到线性

当 $i$ 向右移动时：

• 第一个满足 $p_j-p_i\ge L$ 的位置不会向左；
• 最后一个满足 $p_j-p_i\le R$ 的位置也不会向左。

所以两个边界指针在一个字符的位置数组中都只向右移动，总移动次数为 $O(m)$。

这里有一个容易漏掉的边界：把 p2 强制推进到 i+1 后，pos[p2]-pos[i] 可能已经大于 $R$。此时连最靠近的右端点都太远，本轮没有合法上界，应把 p2=i 设为无效状态。

对 AI 改错过程的复盘

这段对话很有价值，因为 AI 并没有第一次就找对 WA 根因：

1. 第一次把 22/23 WA 归因于 int 溢出，但它此前给出的代码本来已经使用 long long ans，这个解释与实际代码不一致；
2. 第二次发现循环枚举到 i=m-1 会令 i+1=m，把循环改成 i<m-1 后只剩一个点 WA；
3. 第三次才用反例 pos=[1,4,10,12], L=2, R=5 定位到真正剩余问题：p2 被强制推进后可能不满足上界。

这里的经验不是“AI 最终给出了 AC 代码”，而是：测试结果与当前代码永远比解释本身更可靠。 一个修复只让错误数量减少，并不证明剩余 WA 仍来自同一根因；应重新构造能触发当前逻辑的最小反例。

复写代码（双指针）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> cnt[26];
int n,L,R;
string s;
ll ans;

void solve()
{
    cin>>n>>L>>R;
    cin>>s;
    for(int i=0;i<n;i++)
    {
        cnt[s[i]-'a'].push_back(i);
    }

    for(int c=0;c<26;c++)
    {
        auto& v=cnt[c];
        int m=v.size();
        if(m<2) continue;

        int p1=0,p2=0;
        for(int i=0;i<m-1;i++)
        {
            //右端点必须在i的右边
            if(p1<i+1) p1=i+1;
            if(p2<i+1) p2=i+1;

            //最靠近的右端点都超过R时,本轮没有合法上界
            if(v[p2]-v[i]>R) p2=i;
            else
            {
                //找到满足上界的最右位置
                while(p2+1<m&&v[p2+1]-v[i]<=R) p2++;
            }

            //找到满足下界的最左位置
            while(p1<m&&v[p1]-v[i]<L) p1++;

            if(p1<=p2) ans+=(p2-p1+1);
        }
    }

    cout<<ans<<"\n";
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    solve();
    return 0;
}

复杂度

每个位置只进入一个字符数组，两个边界指针在各自数组中单调右移：

$$T=O(N),\qquad S=O(N).$$

可迁移经验

对于“固定左端点，统计值落在区间 $[L,R]$ 的右端点数”问题：

• 静态有序数组可以用 lower_bound + upper_bound；
• 如果所有查询边界随左端点单调移动，可以把两次二分优化成两个指针；
• 两个指针必须分别拥有明确语义，不能只写成模糊的“窗口左右端点”。

---

D - Make Target 2

本题为看题解后复写。最初 AI 给出的八类象限与前缀和做法过重，后来改用官方的两类划分。

题意

平面格点 $(x,y)$ 在

$$\max(|x|,|y|)$$

为偶数时染黑，否则染白。统计矩形

$$L\le x\le R,\qquad D\le y\le U$$

中的黑点数。

坐标绝对值不超过 $10^6$，因此允许扫描一个坐标轴，但不能扫描整个二维矩形。

为什么坐标整体偏移不解决问题

对话记录：D 题 DeepSeek 对话

把坐标统一加上 $10^6$ 虽然能让下标非负，但染色条件仍然是

$$\max(|x'-10^6|,|y'-10^6|),$$

并不会变成简单的 $\max(x',y')$。平移只改变存储下标，不能消除绝对值结构。

官方划分：谁取得最大值

把所有点分成两个互不重叠且完整覆盖的集合：

1. $|x|>|y|$；
2. $|x|\le |y|$。

等号只放在第二类，所以不会重复计数。

第一类：$|x|>|y|$

此时

$$\max(|x|,|y|)=|x|.$$

格点为黑色等价于 $x$ 为偶数。固定一个偶数 $x$，条件

$$|y|<|x|$$

等价于

$$-|x|+1\le y\le |x|-1.$$

再与题目给出的 $[D,U]$ 取交集：

$$\max(D,-|x|+1)\le y\le\min(U,|x|-1).$$

第二类：$|x|\le |y|$

此时最大值为 $|y|$，所以只枚举偶数 $y$。合法 $x$ 满足

$$-|y|\le x\le |y|,$$

再与 $[L,R]$ 取交集即可。

为什么区间长度要与 0 取最大值

两个区间可能没有交集。例如 $L=R=D=U=0$，第一类枚举 $x=0$ 时：

$$\text{bottom}=\max(0,1)=1, \qquad \text{top}=\min(0,-1)=-1,$$

于是

$$C=-1-1+1=-1.$$

这代表交集为空，真实点数应为 $0$，所以必须写 max(C,0)。

复写代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ans;

void solve()
{
    int l,r,d,u;
    cin>>l>>r>>d>>u;

    //第一类: |x|>|y|,最大值由x决定
    for(int x=l;x<=r;x++)
    {
        if(x%2==0)
        {
            int abs_x=abs(x);
            int bottom=max(d,1-abs_x);
            int top=min(u,abs_x-1);
            int C=top-bottom+1;
            ans+=max(C,0);
        }
    }

    //第二类: |x|<=|y|,最大值由y决定
    for(int y=d;y<=u;y++)
    {
        if(y%2==0)
        {
            int abs_y=abs(y);
            int bottom=max(l,-abs_y);
            int top=min(r,abs_y);
            int C=top-bottom+1;
            ans+=max(C,0);
        }
    }

    cout<<ans<<"\n";
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    solve();
    return 0;
}

复杂度

$$T=O(R-L+U-D+2),\qquad S=O(1).$$

最大约扫描 $4\times10^6$ 个坐标，能够通过。

---

E - A += v

本题为 AI 题解后抄写，再独立默写。Fenwick 树是本场第一次接触的数据结构。

题意

序列 $A$ 的元素都在 $1\sim M$。每次选择当前出现次数最少的值 $v$；若并列，选择数值最小者，并把 $v$ 追加到序列末尾。操作执行 $10^{100}$ 次，回答最终序列第 $X_i$ 项。

约束中 $X_i\le10^{18}$，所以不能逐次模拟。

对话记录：E 题 DeepSeek 对话

第一步：把操作压缩成阶段

统计每个值的初始频率，把数值 $1,2,\ldots,M$ 按 (频率, 数值) 升序排列，得到

$$P_1,P_2,\ldots,P_M,$$

对应频率满足

$$V_1\le V_2\le\cdots\le V_M.$$

阶段 $k$ 的目标是把当前最低频率集合 $P_1,\ldots,P_k$ 的频率从 $V_k$ 一起提升到 $V_{k+1}$。

因为并列时选择数值最小者，在这个阶段中实际反复追加的是

$$\operatorname{sort}(P_1,P_2,\ldots,P_k),$$

即当前集合按数值升序形成的长度为 $k$ 的循环节。

每完成一轮，这 $k$ 个值的频率都增加 $1$。共需

$$V_{k+1}-V_k$$

轮，所以阶段 $k$ 新增长度为

$$k(V_{k+1}-V_k).$$

这就是对巨大操作次数的压缩：不执行每次追加，只记录每个阶段结束后的总长度。

需要区分“生成序列实际新增了多少项”和“算法花多少时间”。某阶段长度是 $k(V_{k+1}-V_k)$，这个数可能非常大，但代码只用一次乘法算出它；预处理仍只枚举 $M$ 个阶段，是 $O(M)$，不能因为公式中有乘法就称为 $O(M^2)$ 算法。

阶段结束长度 r[k]

定义 r[k] 为阶段 $k$ 结束后的序列总长度，初始

$$r_0=N.$$

于是

$$r_k=r_{k-1}+k(V_{k+1}-V_k).$$

代码中 ord 是 base-0，因此 ord[k-1].first=V_k，ord[k].first=V_{k+1}：

r[k]=r[k-1]+1LL*k*(ord[k].first-ord[k-1].first);

当 $k=M$ 时，所有值频率相等，此后永远按 $1,2,\ldots,M$ 循环，阶段没有有限终点，所以令

$$V_{M+1}=+\infty$$

并在代码中把 r[M] 设成足够大的数。

第二步：定位查询所在阶段

如果 $X\le N$，答案就是原数组 A[X-1]。

否则二分找到最小的 $k$，满足

$$r_k\ge X.$$

此时 $X$ 落在阶段 $k$。阶段内循环节长度为 $k$，所以相对位置为

$$\text{offset}=(X-r_{k-1}-1)\bmod k.$$

问题变为：在集合 $\{P_1,\ldots,P_k\}$ 中找第 offset+1 小的数值。

第三步：离线 Fenwick 树查询第 $k$ 小

把所有查询按阶段 k 排序，逐渐把 $P_1,P_2,\ldots$ 加入 Fenwick 树：

fw.add(ord[cur].second,1);

这里下标是原数值，加入的 1 表示这个数值已经进入当前集合。于是 Fenwick 前缀和表示“不大于某个数值的已激活元素数量”。

lower_bound(target) 找到最小下标 idx，使得

$$\operatorname{sum}(idx)\ge target,$$

也就是当前集合中第 target 小的数值。

Fenwick 树与线段树是两种不同的数据结构。Fenwick 更轻，适合本题的单点加入、前缀计数和第 $k$ 小查询；不能把它理解为线段树的一个节点写法。

复写代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;

class Fenwick
{
    int n;
    vector<int> b;

    inline int lowbit(int x)
    {
        //x在二进制下最低位的1所代表的值
        return x&(-x);
    }

public:
    Fenwick(int _n):n(_n),b(_n+1){};

    //把原数组pos位置增加val
    void add(int pos,int val)
    {
        while(pos<=n)
        {
            b[pos]+=val;
            pos+=lowbit(pos);
        }
    }

    //查询原数组[1,pos]的前缀和
    ll sum(int pos)
    {
        ll ret=0;
        while(pos>0)
        {
            ret+=b[pos];
            pos-=lowbit(pos);
        }
        return ret;
    }

    //返回最小的idx,使得前缀和sum(idx)>=target
    int lower_bound(int target)
    {
        int idx=0;
        int step=1;
        //找到不超过n的最大2的幂
        while((step<<1)<=n) step<<=1;

        //先构造出前缀和仍然小于target的最大idx
        while(step)
        {
            int nxt=idx+step;
            if(nxt<=n&&b[nxt]<target)
            {
                target-=b[nxt];
                idx=nxt;
            }
            step>>=1;
        }
        return idx+1;
    }
};

struct Query
{
    int k;//所在阶段
    ll pos;//阶段循环节内的base-0位置
    int id;//原查询编号
};

void solve()
{
    int n,m;
    cin>>n>>m;
    vector<int> A(n);
    vector<int> cnt(m+1);
    for(int i=0;i<n;i++)
    {
        cin>>A[i];
        cnt[A[i]]++;
    }

    //按(初始频率,数值)升序排列
    vector<PII> ord;
    ord.reserve(m);
    for(int val=1;val<=m;val++)
    {
        ord.emplace_back(cnt[val],val);
    }
    sort(ord.begin(),ord.end());

    //r[k]:阶段k结束时的序列总长度
    vector<ll> r(m+1);
    r[0]=n;
    for(int k=1;k<m;k++)
    {
        r[k]=r[k-1]+1LL*k*(ord[k].first-ord[k-1].first);
    }
    r[m]=(1LL<<62);

    int Q;cin>>Q;
    vector<int> ans(Q,-1);
    vector<Query> queries;

    for(int i=0;i<Q;i++)
    {
        ll x;cin>>x;
        if(x<=n)
        {
            ans[i]=A[x-1];
            continue;
        }

        int L=0,R=m;
        while(L<R)
        {
            int mid=L+(R-L)/2;
            if(r[mid]>=x) R=mid;
            else L=mid+1;
        }
        int k=L;
        ll offset=(x-r[k-1]-1)%k;
        queries.push_back({k,offset,i});
    }

    //按阶段处理,让Fenwick中的集合逐步扩大
    sort(queries.begin(),queries.end(),[](const Query& a,const Query& b){
        return a.k<b.k;
    });

    Fenwick fw(m);
    int cur=0;
    for(const auto& q:queries)
    {
        while(cur<q.k)
        {
            //该数值进入集合,其位置计数加1
            fw.add(ord[cur].second,1);
            cur++;
        }
        ans[q.id]=fw.lower_bound(q.pos+1);
    }

    for(int i=0;i<Q;i++) cout<<ans[i]<<"\n";
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    solve();
    return 0;
}

默写时的连续错误

这部分在对话摘要和本地 默写过一遍思路.cpp 的注释中都很典型。对于 $X\le N$ 的查询，答案就在原数组中，根本不应进入离线 Fenwick 查询。

错误 1：把原数组查询塞进 queries

最初曾写成类似：

queries[i]={0,x-1,i};

这里同时有两个问题：

1. queries 还是空 vector，直接访问 queries[i] 已经越界；
2. 即使改成 push_back，它的阶段 k=0，处理时 cur<k 永远为假，Fenwick 树中一个元素都不会加入。

随后调用

fw.lower_bound(pos+1);

相当于在全零的空 Fenwick 树上查第一个正排名。倍增会一路认为前缀和仍小于 target，最终返回 m+1，这是无效下标。

错误 2：直接答案连续取错对象

这段逻辑连续出现过：

ans[i]=x;    //错: x是查询位置,不是该位置的值
ans[i]=A[i]; //错: i是查询编号,不是查询位置

正确下标取决于数组采用哪一种编号：

ans[i]=A[x-1];//A是base-0
ans[i]=A[x];  //A是base-1

不能只记住 x-1 或 x，必须先确认当前 A 的编号方式。本笔记最终代码使用 vector<int> A(n)，因此写 A[x-1]。

错误 3：用 Q 遍历离线查询

原数组中的查询已经直接回答，没有放进 queries，所以通常有

$$\operatorname{queries.size()}<Q.$$

若仍写 for(int i=0;i<Q;i++) 就会访问越界。应写范围 for：

for(const auto& q:queries)
{
    //只处理真正进入离线阶段的查询
}

这一串错误的共同根因是混淆了三种编号：原数组位置 $x$、查询编号 $i$、离线阶段编号 $k$。写代码前先给三者分别命名，比出错后盯着 ans[i] 改下标有效得多。

emplace_back 与结构体初始化

ord.emplace_back(cnt[val],val);

这里 ord 的元素是 pair<int,int>，emplace_back 用两个参数直接调用 pair 的构造函数。写成

ord.push_back({cnt[val],val});

效果相同。

Query 在这份 C++17 代码中只是聚合结构体，没有接收三个参数的构造函数，所以使用

queries.push_back({k,offset,i});

最直接。若想写 queries.emplace_back(k,offset,i)，应显式提供相应构造函数。

复杂度

排序与 Fenwick 查询占主导：

$$T=O(N+M\log M+Q\log Q+Q\log M), \qquad S=O(N+M+Q).$$

---

F - Grid Clipping

本题为 AI 题解后抄写，再独立默写。下面保留 copy1.cpp 的专门扫描线做法，而不是更通用但更重的线段树矩形并模板。

题意

$H\times W$ 的网格中有 $N$ 个黑格。统计有多少个 $h\times w$ 的矩形区域全部为白色。

虽然 $H,W\le10^9$，但黑格只有 $N\le2\times10^5$ 个。

对话记录：F 题 DeepSeek 对话

逆向思维：统计被污染的左上角

一个 $h\times w$ 矩形由其左上角 $(r_0,c_0)$ 唯一确定。合法左上角总数为

$$(H-h+1)(W-w+1).$$

设某个黑格为 $(R,C)$。包含它的矩形左上角必须满足

$$R-h+1\le r_0\le R, \qquad C-w+1\le c_0\le C.$$

所以每个黑格会在“左上角坐标系”中污染一个 $h\times w$ 的矩形；实际统计时还要与合法左上角区域取交。问题变为：求这些污染矩形的并集大小，再用总数减去并集。

图中最重要的区分是：原网格坐标描述黑格在哪里；块坐标描述一个候选矩形的左上角在哪里。令

$$X=H-h+1,\qquad Y=W-w+1,$$

则 base-0 的合法左上角范围为

$$r_0\in[0,X),\qquad c_0\in[0,Y).$$

这里 $Y$ 是合法列坐标的数量和右边界，不是一个仍可取到的列下标；最大合法下标是 $Y-1$。

扫描线事件

把黑格转成 base-0 的 $(r,c)$。它在左上角坐标系中的污染范围是

$$[r-h+1,r]\times[c-w+1,c].$$

沿行方向扫描时，这个污染区间：

• 在 $r-h+1$ 行开始生效；
• 在 $r+1$ 行失效。

因此每个黑格生成两个事件 (行, 列区间左端点, 加入/删除)。

为什么只保存区间左端点

所有活动污染区间长度都等于 $w$。若左端点为 $x$，它覆盖半开区间

$$[x,x+w).$$

把所有活动区间左端点排序。相邻左端点 $l<r$ 之间没有被覆盖的空隙长度为

$$\operatorname{gap}(l,r)=\max(0,r-l-w).$$

因此只需动态维护有序左端点，就能维护当前行的合法列数。

multiset 与哨兵

不同黑格可能产生相同的列左端点，所以必须允许重复元素，使用 multiset 而不是 set。

两个永久哨兵为

lefts.insert(-w);
lefts.insert(Y);

• 虚拟区间 [-w,0) 让左边界空隙也能写成 gap(-w,x)=x；
• 右哨兵 $Y$ 让右边界空隙写成 gap(x,Y)=Y-x-w。

它们把“左边界、中间、右边界”统一成同一个相邻端点公式，类似 DP 使用 base-1 哨兵减少边界特判。

good 的精确定义

good 表示当前扫描带中，$[0,Y)$ 内仍然合法的左上角列数，也就是所有 gap 之和。没有活动污染区间时

$$good=\operatorname{gap}(-w,Y)=Y,$$

所以初始 good=Y，不是 $0$。

共享对话中的一版代码注释把 good 写成“当前行被覆盖的列数”，但紧接着又令 good=Y 并使用空隙增量更新，两者矛盾。判断变量含义应以初始化、更新公式和最终用途三者共同为准：这里 Y-good 才是被污染的列数。

在相邻端点 $l,r$ 中插入新左端点 $x$ 时，旧空隙 gap(l,r) 被两个新空隙替代：

$$\Delta=\operatorname{gap}(l,x)+\operatorname{gap}(x,r)-\operatorname{gap}(l,r).$$

加入污染区间后合法空隙不会增加，所以 $\Delta$ 通常小于等于 $0$。删除时做相反更新。

行带面积为什么乘 nx-pre

事件只在若干行发生。在相邻事件行 pre 与 nx 之间，活动区间集合完全不变，所以每一行被污染的列数都相同，等于

$$Y-good.$$

这一整段共有 nx-pre 行，因此要从答案中减去

$$(nx-pre)(Y-good).$$

这统计的是上一批事件生效后直到当前事件前的整段行带，不是只统计 nx 那一行。

复写代码

#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve()
{
    int H,W,h,w,n;
    cin>>H>>W>>h>>w>>n;

    //事件: (生效行,污染列区间左端点,是否加入)
    vector<tuple<int,int,bool>> events;
    events.reserve(2*n);

    for(int i=0;i<n;i++)
    {
        int r,c;
        cin>>r>>c;
        r--,c--;//转成base-0

        int left=c-w+1;
        events.emplace_back(r-h+1,left,true);
        events.emplace_back(r+1,left,false);
    }

    sort(events.begin(),events.end());

    const int X=H-h+1;
    const int Y=W-w+1;

    //总候选左上角数,之后减去被污染的部分
    int ans=X*Y;

    //活动污染区间左端点;允许重复并自动排序
    multiset<int> lefts;
    lefts.insert(-w);
    lefts.insert(Y);

    //相邻等长区间之间仍未被覆盖的空隙(合法左上角的个数)
    auto gap=[&](int l,int r)
    {
        return max(0LL,r-l-w);
    };

    //当前扫描带仍合法的左上角列数
    int good=Y;

    auto add=[&](int x)
    {
        auto it=lefts.lower_bound(x);
        int r=*it;
        int l=*prev(it);

        //旧空隙被(l,x)与(x,r)两个新空隙替代
        good+=gap(l,x)+gap(x,r)-gap(l,r);
        lefts.insert(x);
    };

    auto del=[&](int x)
    {
        //erase(it)只删除一个重复元素
        auto it=lefts.find(x);
        int r=*next(it);
        int l=*prev(it);

        good-=gap(l,x)+gap(x,r)-gap(l,r);
        lefts.erase(it);
    };

    int pre=0;
    int i=0;
    while(i<2*n)
    {
        int x=get<0>(events[i]);
        int nx=min(x,X);

        //上一批事件在[pre,nx)中持续生效
        if(pre<nx)
        {
            ans-=(nx-pre)*(Y-good);
            pre=nx;
        }

        //同一行的事件必须作为一批处理
        while(i<2*n&&get<0>(events[i])==x)
        {
            //C++17结构化绑定
            auto [row,c,is_add]=events[i];
            if(is_add) add(c);
            else del(c);
            i++;
        }
    }

    cout<<ans<<"\n";
}

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    solve();
    return 0;
}

所有事件处理完后，每个加入事件都有对应删除事件，活动集合重新为空，good=Y。因此官方代码末尾用于处理最后行带的语句最终只会减去 $0$；保留它便于套用通用扫描线模板，删掉也不影响本题。

tuple、结构化绑定与 lambda

vector<tuple<int,int,bool>> events;

一个事件同时保存三个不同含义的字段。tuple 默认按第一个、第二个、第三个字段依次进行字典序比较，所以可以直接 sort(events.begin(),events.end())。

读取字段有两种方式：

int x=get<0>(events[i]);
auto [row,c,is_add]=events[i];

第二种是 C++17 的结构化绑定。

lambda 的基本格式为

[捕获列表](参数列表){ 函数体 };

本题的 [&] 表示按引用捕获外部局部变量，所以 add、del 可以直接修改 good 和 lefts。它适合只在当前函数中使用、又依赖多个局部状态的小操作。

复杂度

排序 $2N$ 个事件，且每次 multiset 插入、查找、删除都是 $O(\log N)$：

$$T=O(N\log N),\qquad S=O(N).$$

并查集擅长维护连通块合并，不能高效维护动态区间的有序相邻关系和删除事件，因此不适合本题。

---

G - Many Repunit Sum 2（战略性放弃）

题意

长度为 $d$ 的 repunit（循环单位数）定义为

$$R_d=\sum_{i=0}^{d-1}10^i=\frac{10^d-1}{9}.$$

从 $R_1,R_2,\ldots,R_M$ 中可重复选择 $N$ 个并求和，问能够得到多少个不同整数，答案对 $998244353$ 取模。

对话记录：G 题 DeepSeek 对话

第一层数学结构：repunit 的进位恒等式

对 $2\le d\le M-1$，有

$$11R_d=10R_{d-1}+R_{d+1}.$$

两边都由 $11$ 个 repunit 构成，所以替换既不改变总和，也不改变所选 repunit 的数量。它允许把某个中间长度出现 $11$ 次的情况向相邻长度“进位”。

当 $M=1$ 时只有 $R_1$ 可选，答案显然为 $1$。以下讨论 $M\ge2$。

归一化后，可把中间长度的使用次数限制为

$$0\le c_d\le10\qquad(2\le d\le M-1),$$

而两端 $c_1,c_M$ 不受这个限制。于是答案对应生成函数系数

$$[x^N]\frac{(1+x+x^2+\cdots+x^{10})^{M-2}}{(1-x)^2}.$$

再利用

$$1+x+\cdots+x^{10}=\frac{1-x^{11}}{1-x},$$

可改写为

$$[x^N](1-x^{11})^{M-2}(1-x)^{-M}.$$

从这里继续到本地五十多行代码，还需要容斥展开、组合数的上升/下降阶乘，以及按模 $9$ 同余类复用前缀和。这些才是代码真正压缩掉的难度。

本地参考代码的模块地图

不逐行背实现，只记录各数组职责：

• inv[i]：$i$ 在模 $998244353$ 下的逆元；
• ifac[i]：$1/i!$；
• fad[i]：下降阶乘，用于计算 $\binom{M-1}{i}$；
• fai[i]：上升阶乘，用于计算 $\binom{M+i-1}{i}$；
• res[l]：按 $l\bmod9$ 复用的组合数前缀和；
• sgn[l]：容斥展开中的正负号。

代码中的 l-=9 与十进制恒等式产生的 $9$ 有关；它不是一个能从语法层面猜出的优化，而是推导后的结果。

为什么现在不继续改错

这题的主要门槛不是 C++，而是：

1. 证明归一化表示与不同整数之间的对应关系；
2. 从生成函数得到可计算的组合恒等式；
3. 理解为什么按模 $9$ 的递推不会重算或漏算；
4. 在模意义下正确实现上升、下降阶乘与容斥符号。

当前刚接触 Fenwick 树、扫描线和基础离线思想时，继续逐行修这份代码很容易变成记变量而不理解公式。战略性放弃是合理的学习顺序，不是因为代码行数少就必须掌握。

以后回看的前置路线

1. 熟练组合数预处理、逆元和容斥原理；
2. 学习普通生成函数及系数提取；
3. 练习有上界的非负整数解计数；
4. 理解上升阶乘、下降阶乘；
5. 最后再回来完整证明本题的模 $9$ 递推。

---

新知识专题

1. Fenwick 树（树状数组）

Fenwick 树不是线段树的一种。二者都是处理区间信息的数据结构，但 Fenwick 树结构更轻，适合满足可逆前缀运算的场景，例如：

• 单点修改；
• 前缀和；
• 区间和 sum(r)-sum(l-1)；
• 在所有频率非负时，倍增查找第一个达到目标的前缀。

base-1 的 b[x] 管理长度为

$$\operatorname{lowbit}(x)=x\&(-x)$$

的一段区间。更新不断跳到父节点 x+=lowbit(x)，查询不断剥掉当前管理段 x-=lowbit(x)。

E 题中 Fenwick 树保存的是 $1\sim M$ 哪些数值已经加入当前阶段集合：叶子值只有 $0/1$，前缀和就是已加入数值的排名计数。

完整文件：Fenwick 树模板

下面把模板整理成可直接复用的版本。它采用 base-1，并修正了原注释中“最大 / 最小二次幂”与 lower_bound 含义不够准确的问题：

#include <bits/stdc++.h>
using namespace std;

//base-1
class Fenwick
{
    int n;
    vector<int> b;

    //二进制中最低位的1所代表的值
    inline int lowbit(int x)
    {
        return x&(-x);
    }

public:
    Fenwick(int _n):n(_n),b(_n+1){};

    //原数组pos位置增加val
    void add(int pos,int val)
    {
        while(pos<=n)
        {
            b[pos]+=val;
            pos+=lowbit(pos);
        }
    }

    //查询原数组[1,pos]的前缀和
    long long sum(int pos)
    {
        long long ret=0;
        while(pos>0)
        {
            ret+=b[pos];
            pos-=lowbit(pos);
        }
        return ret;
    }

    //查询原数组[l,r]的区间和
    long long sum(int l,int r)
    {
        return sum(r)-sum(l-1);
    }

    //要求所有频率非负且1<=target<=sum(n)
    //返回最小的idx,使得sum(idx)>=target
    int lower_bound(int target)
    {
        int idx=0;
        int step=1;
        //不超过n的最大2的幂
        while((step<<1)<=n) step<<=1;

        //构造前缀和仍小于target的最大idx
        while(step)
        {
            int nxt=idx+step;
            if(nxt<=n&&b[nxt]<target)
            {
                target-=b[nxt];
                idx=nxt;
            }
            step>>=1;
        }
        return idx+1;
    }
};

模板使用时必须记住：

• add、sum 的位置都是 base-1；
• lower_bound 查询的是前缀和，不是普通数组中第一个大于某值的元素；
• lower_bound 的 target 必须存在。若树为空却查询正数排名，它会返回 n+1；
• 若只需要普通前缀和与区间和，可以不保留 lower_bound。

2. multiset

multiset 是自动排序、允许重复元素的平衡搜索树容器，常用操作复杂度为 $O(\log N)$：

//头文件<set>,bits/stdc++.h已经包含
//有序容器,允许重复元素
multiset<int> lefts;

lefts.insert(x);//插入一个x
auto it=lefts.find(x);//第一个等于x的位置;不存在则返回end()
auto it1=lefts.lower_bound(x);//第一个>=x的位置
auto it2=lefts.upper_bound(x);//第一个>x的位置
int cnt=lefts.count(x);//x出现的次数

lefts.erase(it);//只删除it指向的一个元素
lefts.erase(x);//删除所有等于x的元素

auto first=lefts.begin();//最小元素
auto last=prev(lefts.end());//最大元素
auto pre=prev(it);//it的前驱
auto nxt=next(it);//it的后继

int n=lefts.size();
bool flag=lefts.empty();
lefts.clear();//清空

prev(it) 要求 it!=begin()，next(it) 要求后继不是 end()。F 题放入两个哨兵后，真实区间左端点始终有前驱和后继，因此可以安全调用。

注意 lefts.erase(x) 会删除所有等于 $x$ 的元素；只想删一个时应先 find，再 erase(it)。

F 题必须保留相同的区间左端点，所以不能换成 set。

3. tuple 与结构化绑定

pair 保存两个字段，tuple 可以保存任意多个字段：

tuple<int,int,bool> event={row,left,is_add};
int row=get<0>(event);
auto [r,c,flag]=event;

tuple 的默认比较是字典序，适合按多个关键字排序的轻量记录。字段含义很多或需要在多处使用时，具名 struct 会比 tuple 更清楚。

4. lambda 表达式

lambda 是局部匿名函数：

auto gap=[&](int l,int r)
{
    return max(0LL,r-l-w);
};

常见捕获方式：

• []：不捕获外部变量；
• [&]：按引用捕获，能够修改外部变量；
• [=]：按值捕获一份副本；
• [&w]、[w]：只捕获指定变量。

排序比较器也是常见用途：

sort(queries.begin(),queries.end(),[](const Query& a,const Query& b){
    return a.k<b.k;
});

此处不依赖外部变量，所以捕获列表为空。

---

本场错因清单

题意与变量命名

• B：把查询模板 1 R / 2 C 看成了同一行的两个变量。变量名 R,C 又进一步掩盖了第一个数其实是操作类型。
• F：一度混淆原网格坐标、候选块左上角坐标、坐标数量 $Y$ 与最大下标 $Y-1$。

指针与边界

• C：没有先固定左端点并定义两个边界指针的精确含义。
• C：混用了 base-0 字符串与 base-1 循环。
• C：数组边界判断写在访问之后，并且最初答案使用 int。
• C：p2 被推进到 i+1 后，必须重新检查是否已经超过上界 $R$。

公式与分类

• D：最初按象限分类，把一道允许 $O(10^6)$ 扫描的题做成了复杂前缀和。
• D：区间交可能为空(C的结果为负数)，不能直接把 top-bottom+1 加入答案。
• F：good 的定义必须始终固定为“合法空隙数”；若一会儿称合法数、一会儿称覆盖数，所有正负号都会混乱。

新数据结构

• E：Fenwick 的 lower_bound 查的是前缀和位置，不是普通数组元素。
• E：add(value,1) 的 1 是存在标记，不是把原始频率加入树中。
• F：multiset 的必要性来自重复左端点；删除时只能删一个实例。
• F：哨兵不是待处理数据，而是永久边界锚点。

---

赛后训练清单

• 不看代码重写 C 的二分版本，并解释为什么使用 upper_bound(v[i]+R)。
• 不看代码重写 C 的双指针版本，先在纸上写清 p1、p2 的不变量。
• 手算 D 中 $x=0$、$x=2$ 时两个区间的交，并写出空集判断。
• 用频率 [0,1,2] 和 [0,0,2] 手推 E 的全部阶段、r[k] 与循环节。
• 在纸上画一个 8 个位置的 Fenwick 树，分别写出 add(3,1) 与 sum(7) 经过的下标。
• 手推 Fenwick lower_bound(第3小) 的倍增过程，明确 target 为什么会逐段扣减。
• 重新画 F 的左上角坐标系，并标出 $X,Y$、两个事件行与污染列区间。
• 用三个重叠等长区间手算 gap、add、del 对 good 的影响。
• G 暂不改错；先完成组合数、容斥和普通生成函数的基础练习。