JZOJ 4419.Hole

这题空间卡得比动态逆序对还恐怖……

发现这个东西不好简单地用数据结构维护,于是我们可以看一张图:

我们发现框起来的部分是所有满足 i+j[x+y,x+y+d]i + j \in [x + y,x + y + d] 的点对 (i,j)(i,j)
又发现,减去两块绿色的平行四边形剩下的蓝色三角形正是询问的结果。
于是思考一下,又发现这两块区域分别对应着 i<x,j<yi < x,j < y 的点对。
而且,由于第一个限制,这两个条件不可能同时满足。

于是考虑树套树,第一层维护 x+yx + y 的和,第二层开两棵分别维护 x,yx,y
卡一卡空间就好了。

代码:

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
100
101
102
103
#include <cstdio>
#define ls(p) tree[p].lson
#define rs(p) tree[p].rson
using namespace std;

const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
#define gc() (BB == BE ? (BE = (BB = BUFF) + fread(BUFF,1,BUFF_SIZE,stdin),BB == BE ? EOF : *BB++) : *BB++)
template<class T>
inline void read(T &x)
{
x = 0;
char ch = 0,w = 0;
while(ch < '0' || ch > '9')
w |= ch == '-',ch = gc();
while(ch >= '0' && ch <= '9')
x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc();
w && (x = -x);
}

const int N = 88888;
const int A = 33333333;
int n;
struct segnode
{
int cnt;
int lson,rson;
} seg[N * 448 + 10];
struct node
{
int x,y;
int lson,rson;
} tree[N * 38 + 10];
int rt;
void insert(int x,int &p,int tl,int tr)
{
static int tot = 0;
if(!p)
p = ++tot;
++seg[p].cnt;
if(tl == tr)
return ;
int mid = tl + tr >> 1;
if(x <= mid)
insert(x,seg[p].lson,tl,mid);
else
insert(x,seg[p].rson,mid + 1,tr);
}
int query(int l,int r,int p,int tl,int tr)
{
if(!p)
return 0;
if(l <= tl && tr <= r)
return seg[p].cnt;
int mid = tl + tr >> 1;
int ret = 0;
if(l <= mid)
ret += query(l,r,seg[p].lson,tl,mid);
if(r > mid)
ret += query(l,r,seg[p].rson,mid + 1,tr);
return ret;
}
void insert(int x,int y,int &p,int tl,int tr)
{
static int tot = 0;
if(!p)
p = ++tot;
insert(x,tree[p].x,0,A),insert(y,tree[p].y,0,A);
if(tl == tr)
return ;
int mid = tl + tr >> 1;
if(x + y <= mid)
insert(x,y,ls(p),tl,mid);
else
insert(x,y,rs(p),mid + 1,tr);
}
int query(int x,int y,int d,int p,int tl,int tr)
{
if(!p)
return 0;
if(x + y <= tl && tr <= x + y + d)
return seg[tree[p].x].cnt - query(0,x - 1,tree[p].x,0,A) - query(0,y - 1,tree[p].y,0,A);
int mid = tl + tr >> 1;
int ret = 0;
if(x + y <= mid)
ret += query(x,y,d,ls(p),tl,mid);
if(x + y + d > mid)
ret += query(x,y,d,rs(p),mid + 1,tr);
return ret;
}
int main()
{
read(n);
int x,y,d;
while(n--)
{
read(x),read(y),read(d);
if(!d)
insert(x,y,rt,0,A * 2);
else
printf("%d\n",query(x,y,d,rt,0,A * 2));
}
}