完成了我人生第二道 CDQ 分治题（上一道是我自己出的）……
告诉我，你和 JZOJ 4419 啥关系（
考虑如何判定一个点是否在一个等腰直角三角形内部。
这里以 \((x,y),(x+z,y),(x,y+z)\) 组成的三角形为例（即 \(type=1\) 的情况）。
显然点 \((x',y')\) 在这个三角形内部，当且仅当 \(x+y \le x'+y' \le x+y+z, x \le x', y \le y'\)。
首先假设所有询问都在修改后。
看起来是个三维偏序。然而，实际上，容易发现，若 \(x+y \le x'+y' \le x+y+z\)，则在剩下的两个条件中，必定至少满足一个。
这意味着什么？
这意味着，仅需用总数分别减去不满足其中一个条件的数量即可。
这样就变成二维偏序了。
当然，再套路地做两次二维偏序很麻烦……
所以实际上可以对 \(x+y\) 做扫描线，然后用两个树状数组分别维护 \(x\) 和 \(y\) 的贡献。
这样就可以一遍扫描线解决一个一维偏序（雾，但是没说错啊）和两个二维偏序了。
然后丢上 CDQ 分治即可。
复杂度 \(O(n \log^2 n)\)。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
using namespace std;
const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
template<class T>
inline void read(T &x)
{
x = 0;
char ch = 0,w = 0;
for(;ch < '0' || ch > '9';w |= ch == '-',ch = gc());
for(;ch >= '0' && ch <= '9';x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc());
w && (x = -x,1);
}
const int N = 3e5;
const int M = 3e5;
int num,n,m,all;
int tot[4],qry_tot,ans[M + 5];
struct note
{
int op,x,y,z;
inline bool operator<(const note &o) const
{
return x + y + z < o.x + o.y + o.z || (x + y + z == o.x + o.y + o.z && op < o.op);
}
} a[4][M + 5],e[(M << 1) + 5];
int c[2][N + 5];
inline void update(int op,int x,int k)
{
for(;x;x -= lowbit(x))
c[op][x] += k;
}
inline int query(int op,int x)
{
int ret = 0;
for(;x <= n;x += lowbit(x))
ret += c[op][x];
return ret;
}
void cdq(note *a,int l,int r)
{
if(l == r)
return ;
int mid = l + r >> 1,n = 0;
cdq(a,l,mid),cdq(a,mid + 1,r);
for(register int i = l;i <= mid;++i)
if(!a[i].op)
e[++n] = (note){0,a[i].x,a[i].y,0},e[++n] = (note){-1,a[i].x,a[i].y,a[i].z + 1};
for(register int i = mid + 1;i <= r;++i)
if(a[i].op)
e[++n] = (note){a[i].op,a[i].x,a[i].y,0};
sort(e + 1,e + n + 1);
for(register int i = 1;i <= n;++i)
{
if(!e[i].op)
update(0,all,1),update(0,e[i].x - 1,-1),update(1,e[i].y - 1,-1);
else if(~e[i].op)
ans[e[i].op] += query(0,e[i].x) + query(1,e[i].y);
else
update(0,all,-1),update(0,e[i].x - 1,1),update(1,e[i].y - 1,1);
}
}
int main()
{
freopen("frontier.in","r",stdin),freopen("frontier.out","w",stdout);
read(num),read(n),read(m),all = n;
int op,type,x,y,z;
for(register int i = 1;i <= m;++i)
{
read(op);
if(op == 1)
{
read(type),read(x),read(y),read(z);
if(type == 1)
a[0][++tot[0]] = (note){0,x,y,z};
else if(type == 2)
a[1][++tot[1]] = (note){0,x,n - y + 1,z};
else if(type == 3)
a[2][++tot[2]] = (note){0,n - x + 1,y,z};
else
a[3][++tot[3]] = (note){0,n - x + 1,n - y + 1,z};
}
else
read(x),read(y),++qry_tot,
a[0][++tot[0]] = (note){qry_tot,x,y,0},
a[1][++tot[1]] = (note){qry_tot,x,n - y + 1,0},
a[2][++tot[2]] = (note){qry_tot,n - x + 1,y,0},
a[3][++tot[3]] = (note){qry_tot,n - x + 1,n - y + 1,0};
}
for(register int i = 0;i < 4;++i)
if(tot[i])
cdq(a[i],1,tot[i]);
for(register int i = 1;i <= qry_tot;++i)
printf("%d\n",ans[i]);
}