CodeForces 575I Robots protection
你需要在平面直角坐标系上进行 q 次操作。每次操作有两种，要么放置一个两条直角边平行于坐标轴的等腰直角三角形，要么查询某一个点被多少个三角形覆盖。保证所有点的坐标都是整数且 ∈[1,n]。n≤5×103,q≤105。
考虑到四种方向是对称的，我们只考虑其中一种情况，比如说直角顶点在左下角的情况，令三个顶点为 (x,y),(x+l,y),(x,y+l)。
首先我们发现需要加的所有点 (x′,y′)，都满足 x+y≤x′+y′≤x+y+l，这个东西用一棵树状数组就可以维护：
然后我们就是要减去这两块：
我们考虑如何减去，观察这些点的性质，首先均满足 x′+y′∈[x+y,x+y+l]，然后其还满足 x′<x 或 y′<y。于是我们可以考虑开两棵二维树状数组，一棵维护下标 (x+y,x)，另一棵维护下标 (x+y,y)，然后在这两棵树状数组上矩阵加即可。
时间复杂度 O(qlog2n)，空间 O(n2)。
代码在这儿 。
