第一次打 ABC。
A
显然地输出：
\[\sum_{i=1}^ni=\dfrac{n(n+1)}2\]B
显然地 $\mathcal O\left(n^3\right)$ 模拟即可。
C
考虑维护指针 $r$，那么 $i$ 从 $1$ 到 $\min(r,n)$ 遍历。
对于 $i$，令 $r\leftarrow\max(r,i+a_i-1)$ 即可。
最终答案即最大的 $i$。
赛时代码
```cpp //#include<bits/stdc++.h> #include-
using namespace std;
constexpr const int N=5e5;
int n,a[N+1];
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
int ans=1;
for(int i=2,r=a[1];i<=r&&i<=n;i++){
ans++;
r=max(r,i+a[i]-1);
}
cout<<ans<<'\n';
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
```
</details>
# [D](https://www.luogu.com.cn/problem/AT_abc435_d)
考虑 $x$ 染黑，那么所有能够抵达 $x$ 的节点的答案都需要更改。考虑从 $x$ 开始反向 DFS，标记这些点即可。如果走到的点 $y$ 已经染色过了，则跳出递归。
时间复杂度 $\mathcal O(n+m+q)$。
赛时代码
```cpp //#include<bits/stdc++.h> #include-
using namespace std;
constexpr const int N=3e5;
int n;
bool vis[N+1];
vector
赛时代码
```cpp //#include<bits/stdc++.h> #include-
using namespace std;
constexpr const int N=1e9,Q=2e5;
struct segTree{
int size;
struct node{
int l,r,value;
int lChild,rChild;
bool tag;
int size(){
return r-l+1;
}
}t[Q*100];
int create(node x){
t[++size]=x;
return size;
}
void build(int l,int r){
create({l,r,r-l+1});
}
void up(int p){
t[p].value=t[t[p].lChild].value+t[t[p].rChild].value;
}
void down(int p){
int mid=t[p].l+t[p].r>>1;
if(!t[p].lChild){
t[p].lChild=create({t[p].l,mid,mid-t[p].l+1});
}
if(!t[p].rChild){
t[p].rChild=create({mid+1,t[p].r,t[p].r-mid});
}
if(t[p].tag){
t[t[p].lChild].value=0;
t[t[p].lChild].tag=true;
t[t[p].rChild].value=0;
t[t[p].rChild].tag=true;
t[p].tag=false;
}
}
void update(int p,int l,int r){
if(l<=t[p].l&&t[p].r<=r){
t[p].value=0;
t[p].tag=true;
return;
}
down(p);
if(l<=t[t[p].lChild].r){
update(t[p].lChild,l,r);
}
if(t[t[p].rChild].l<=r){
update(t[p].rChild,l,r);
}
up(p);
}
int query(int p,int l,int r){
if(l<=t[p].l&&t[p].r<=r){
return t[p].value;
}
down(p);
int ans=0;
if(l<=t[t[p].lChild].r){
ans+=query(t[p].lChild,l,r);
}
if(t[t[p].rChild].l<=r){
ans+=query(t[p].rChild,l,r);
}
return ans;
}
}t;
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n,q;
cin>>n>>q;
t.build(1,n);
while(q--){
int l,r;
cin>>l>>r;
t.update(1,l,r);
cout<<t.query(1,1,n)<<'\n';
}
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
```
</details>
# [F](https://www.luogu.com.cn/problem/AT_abc435_f)
记 $a_i$ 为原题中 $P_i$。
显然，移走猫所在的塔更优。
容易想到，塔 $i$ 被删除后，只能移动到左边或者右边。因此完全等价于把剩下的另一段前缀/后缀全部删除。
因此可以想到这就是把整个序列建成一棵二叉树，删除一个塔就相当于走入一棵子树（删除另一棵子树）。
因此设 $\textit{dp}_x$ 为从 $x$ 开始走的答案。记 $l,r$ 分别为 $x$ 的左右子节点，则有：
$$
\textit{dp}_x=\max(\textit{dp}_l+\vert x-l\vert,\textit{dp}_r+\vert x-r\vert)
$$
之后考虑如何建树是合法的。每次必须跳到最高的塔，等价于要求树根的 $a$ 最大，即大根堆。并且下标应当满足 BST 性质，这就是一棵笛卡尔树。
时间复杂度 $\mathcal O(n)$。
赛时代码
```cpp //#include<bits/stdc++.h> #include-
using namespace std;
typedef long long ll;
constexpr const int N=2e5;
int n,a[N+1],lChild[N+1],rChild[N+1];
ll dfs(int x){
ll ans=0;
if(lChild[x]){
ans=max(ans,abs(x-lChild[x])+dfs(lChild[x]));
}
if(rChild[x]){
ans=max(ans,abs(x-rChild[x])+dfs(rChild[x]));
}
return ans;
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
vector
