你需要在平面直角坐标系上进行 \(q\) 次操作。每次操作有两种，要么放置一个两条直角边平行于坐标轴的等腰直角三角形，要么查询某一个点被多少个三角形覆盖。保证所有点的坐标都是整数且 \(\in [1,n]\)。\(n \le 5 \times 10^3, q \le 10^5\)。
考虑到四种方向是对称的，我们只考虑其中一种情况，比如说直角顶点在左下角的情况，令三个顶点为 \((x,y), (x+l,y), (x,y+l)\)。
首先我们发现需要加的所有点 \((x',y')\)，都满足 \(x+y\le x'+y'\le x+y+l\)，这个东西用一棵树状数组就可以维护：
然后我们就是要减去这两块：
我们考虑如何减去，观察这些点的性质，首先均满足 \(x'+y'\in [x+y,x+y+l]\)，然后其还满足 \(x'<x\) 或 \(y'<y\)。于是我们可以考虑开两棵二维树状数组，一棵维护下标 \((x+y,x)\)，另一棵维护下标 \((x+y,y)\)，然后在这两棵树状数组上矩阵加即可。
时间复杂度 \(\mathcal{O}(q\log^2n)\)，空间 \(\mathcal{O}(n^2)\)。
cpp
#define _CRT_SECURE_NO_WARNINGS
#include <map>
#include <set>
#include <stack>
#include <ctime>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cctype>
#include <vector>
#include <bitset>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <fstream>
#include <iostream>
#include <algorithm>
using namespace std;
inline char gc() {
static const int L = 233333;
static char sxd[L], *sss = sxd, *ttt = sxd;
if (sss == ttt) {
ttt = (sss = sxd) + fread(sxd, 1, L, stdin);
if (sss == ttt) {
return EOF;
}
}
return *sss++;
}
#ifndef _AT_HOME
#define dd c = gc()
#else
#define dd c = getchar()
#endif
inline char readalpha() {
char dd;
for (; !isalpha(c); dd);
return c;
}
inline char readchar() {
char dd;
for (; c == ' '; dd);
return c;
}
template <class T>
inline bool read(T& x) {
bool flg = false;
char dd;
x = 0;
for (; !isdigit(c); dd) {
if (c == '-') {
flg = true;
} else if(c == EOF) {
return false;
}
}
for (; isdigit(c); dd) {
x = (x * 10) + (c ^ 48);
}
if (flg) {
x = -x;
}
return true;
}
#undef dd
template <class T>
inline void write(T x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x < 10) {
putchar(x | 48);
return;
}
write(x / 10);
putchar((x % 10) | 48);
}
template <class T>
inline void writesp(T x) {
write(x);
putchar(' ');
}
template <class T>
inline void writeln(T x) {
write(x);
puts("");
}
#define lowbit(x) (x & -x)
namespace dfcmd {
const int maxn = 5005;
const int maxq = 100005;
int n, q;
struct Tree_Line {
int no[maxn << 1];
inline void init() {
memset(no, 0, sizeof(no));
}
inline void _update(int x, int y) {
for (; x <= n << 1; x += lowbit(x)) {
no[x] += y;
}
}
inline void update(int l, int r) {
_update(l, 1);
_update(r + 1, -1);
}
inline int query(int x) {
int ans = 0;
for (; x; x -= lowbit(x)) {
ans += no[x];
}
return ans;
}
} s;
struct Tree_2D {
int no[maxn << 1][maxn];
inline void init() {
memset(no, 0, sizeof(no));
}
inline void _update(int x, int y, int xx) {
for (; x <= n << 1; x += lowbit(x)) {
for (int ty = y; ty <= n; ty += lowbit(ty)) {
no[x][ty] += xx;
}
}
}
inline void update(int lx, int ly, int rx, int ry) {
if (lx <= rx && ly <= ry) {
_update(lx, ly, 1);
_update(rx + 1, ly, -1);
_update(lx, ry + 1, -1);
_update(rx + 1, ry + 1, 1);
}
}
inline int query(int x, int y) {
int ans = 0;
for (; x; x -= lowbit(x)) {
for (int ty = y; ty; ty -= lowbit(ty)) {
ans += no[x][ty];
}
}
return ans;
}
} xx, yy;
struct query {
int typ, dir, x, y, len;
} qq[maxq];
int ans[maxq];
inline void solve(int tp) {
xx.init(), yy.init(), s.init();
for (int i = 1; i <= q; ++i) {
if (qq[i].typ == 2) {
ans[i] += s.query(qq[i].x + qq[i].y) - xx.query(qq[i].x + qq[i].y, qq[i].x) - yy.query(qq[i].x + qq[i].y, qq[i].y);
} else if ((qq[i].dir & 1) == tp) {
if (qq[i].dir < 3) {
s.update(qq[i].x + qq[i].y, qq[i].x + qq[i].y + qq[i].len);
xx.update(qq[i].x + qq[i].y, 1, qq[i].x + qq[i].y + qq[i].len, qq[i].x - 1);
yy.update(qq[i].x + qq[i].y, 1, qq[i].x + qq[i].y + qq[i].len, qq[i].y - 1);
} else {
s.update(qq[i].x + qq[i].y - qq[i].len, qq[i].x + qq[i].y);
xx.update(qq[i].x + qq[i].y - qq[i].len, qq[i].x + 1, qq[i].x + qq[i].y, n);
yy.update(qq[i].x + qq[i].y - qq[i].len, qq[i].y + 1, qq[i].x + qq[i].y, n);
}
}
}
}
int Main() {
read(n), read(q);
for (int i = 1; i <= q; ++i) {
read(qq[i].typ);
if (qq[i].typ == 1) {
read(qq[i].dir), read(qq[i].x), read(qq[i].y), read(qq[i].len);
if (qq[i].dir == 3) {
qq[i].dir = 4;
} else if (qq[i].dir == 4) {
qq[i].dir = 3;
}
} else {
read(qq[i].x), read(qq[i].y);
}
}
solve(1);
for (int i = 1; i <= q; ++i) {
qq[i].y = n - qq[i].y + 1;
}
solve(0);
for (int i = 1; i <= q; ++i) {
if (qq[i].typ == 2) {
writeln(ans[i]);
}
}
return 0;
}
}
int main() {
return dfcmd::Main();
}