三角形即:x>i 并且 x − i ≥ |y - j|
二维树状数组:与一维相似
注意:i + j 可能大于n,开两倍数组
以CF1864D为例
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 3010, M = N * 2;
int n, m;
bool p[N][N], tr[M][M];
void modify(int l, int r)
{
for (int i = l; i <= m; i += i & -i)
for (int j = r; j <= m; j += j & -j)
tr[i][j] ^= 1;
}
bool query(int l, int r)
{
bool res = 0;
for (int i = l; i; i -= i & -i)
for (int j = r; j; j -= j & -j)
res ^= tr[i][j];
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T -- )
{
cin >> n;
m = n * 2 - 1;
for (int i = 1; i <= n; i ++ )
{
string s;
cin >> s;
for (int j = 1; j <= n; j ++ ) p[i][j] = s[j - 1] - '0';
}
for (int i = 1; i <= m; i ++ )
for (int j = 1; j <= m; j ++ )
tr[i][j] = 0;
int ans = 0;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
if (p[i][j] ^ query(i + j - 1, i - j + n))
{
ans ++ ;
modify(i + j - 1, i - j + n);
}
cout << ans << '\n';
}
}
注注:1.为什么选择i + j - 1, i - j + n:可以理解为使r <= i + j - 1取反,l <= i - j + n, 即l >= j - i + n取反