我们注意到对如图倒三角形上的所有点操作都会影响到目标点。那么我们可以维护两个前缀和，第一个前缀和表示如下的点是否操作第二个前缀和表示这些点是否操作这样我们求出了前缀和之后，将两个前缀和异或一下就知道该点是否要操作了。#include<bits/stdc++.h>usingnamespace

https://codeforces.com/contest/1864/problem/D结论很好猜，直接从上到下做就行我们可以维护差分数组，表示对下面的影响，逐行往下推就行，当然+和-要分开，因为一个是往前推，一个往后推。时间复杂度\(O(n^2)\)#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>

CF1864DMatrixCascade题解Links洛谷CodeforcesDescription给定一个\(n\timesn\)的01矩阵。定义一次操作为：选择矩阵上第\(i\)行第\(j\)列的格子\((i,j)\)，将其取反，并取反所有满足\(x>i,x-i\ge|y-j|\)的位置\((x,y)\)。其中，“取反”的意思为：把\(0\)

首先把式子拆一下，可以知道\(x-i\ge|y-j|\)等价于\(x-y\gei-j\)和\(x+y\gei+j\)，注意到每次操作\((i,j)\)，影响到的点\((x,y)\)均要满足\(x>i\)，那么我们每次就必须要按照从上往下的顺序进行，否则上面的点无法影响到，即从第一行开始操作。又注意到对于\((i,j)\)如果执

思路第一时间想到的是暴力，因为同一行的互不影响，所以第一行的\(1\)一定都需要操作，然后把后续的状态更新，再操作第二行的所有的\(1\)，但是很可惜是\(O(n^4)\)的复杂度，必然会TLE。所以思考其他的办法，考虑到可以统计有多少操作更改了这个位置的状态，所以可以使用一个类似前缀和的