算是一个我不太熟悉的技巧吧……感觉大家都会，就我一个考场上没想出来.
单独考虑某一种商店类型到居住点的距离，它关于坐标的函数一定是一条折线，而且每一段的斜率都只可能是1或-1. 因为最后相当于要把一堆折线取max，所以每一条折线可以看作是一堆射线，即斜率为1的段只考虑右端点，斜率为-1的段只考虑左端点. 这样一来，查询就是给定某个横坐标求这个横坐标上各条射线的最高点，修改就是加入若干条射线，删除若干条射线.
考虑用一个数据结构维护这些射线，我的第一反应是lych线段树，但是它不支持删除. 注意到斜率只有两种，而相同斜率的射线方向都是一样的，我们可以把射线按斜率分开，分别按端点横坐标排序，同时维护截距. 那么每次查询其实就是查前缀/后缀的最大截距，插入和删除就是简单的单点修改，用一个平衡树来维护就可以了.
复杂度是一个$\log$的，但是常数应该比较大，截止到写这篇题解的时候，我的代码是loj上AC代码里面最慢的.
代码：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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
using namespace std;
const ele INF=2e9;
struct evt{
ele ty,x,t,a;
inline bool operator<(evt b)const{
return a<b.a;
}
};
struct ask{
ele l,y,id;
inline bool operator<(ask b)const{
return y<b.y;
}
};
struct node{
ele i,b,mx,p;
node *l,*r;
node(){
p=rand(); l=r=NULL;
}
inline ele cmp(ele i,ele b){
if (i!=this->i) return i<this->i?0:1;
if (b!=this->b) return b<this->b?0:1;
return -1;
}
};
template<class T>struct mempool{
T *s,*t;
mempool():s(NULL),t(NULL){}
inline T* alloc(){
return s==t && (t=(s=new T[K])+K),s++;
}
};
ele n,k,Q,tot,cnt[maxn],res[maxn];
evt e[maxn];
ask q[maxn];
multiset<ele> S[maxn];
mempool<node> np;
node *r1,*r2;
inline void maintain(node *x){
x->mx=x->b;
if (x->l) x->mx=max(x->mx,x->l->mx);
if (x->r) x->mx=max(x->mx,x->r->mx);
}
node* merge(node *a,node *b){
if (!a) return b;
if (!b) return a;
if (a->p>b->p){
a->r=merge(a->r,b);
maintain(a);
return a;
}
else{
b->l=merge(a,b->l);
maintain(b);
return b;
}
}
void split(node *x,ele k,ele b1,node*&a,node*&b){
if (!x){ a=b=NULL; return; }
if (!x->cmp(k,b1)){
split(x->l,k,b1,a,b);
x->l=b; maintain(x);
b=x;
}
else{
split(x->r,k,b1,a,b);
x->r=a; maintain(x);
a=x;
}
}
inline node* ins(node *x,ele i,ele b){
node *p=np.alloc();
p->i=i; p->b=b; maintain(p);
node *u,*v;
split(x,i,b,u,v);
x=merge(u,p); x=merge(x,v);
return x;
}
inline node* del(node *x,ele i,ele b){
node *u,*v,*w;
split(x,i,b,v,w);
split(v,i,b-1,u,v);
if (v) v=merge(v->l,v->r);
else v=NULL;
x=merge(u,v); x=merge(x,w);
return x;
}
inline void ins(ele x,ele y){
ele L=(y-x)/2;
r1=ins(r1,x+L,-x); r2=ins(r2,y-L,y);
}
inline void del(ele x,ele y){
ele L=(y-x)/2;
r1=del(r1,x+L,-x); r2=del(r2,y-L,y);
}
int main(){
scanf("%lld%lld%lld",&n,&k,&Q);
for (int i=0; i<n; ++i){
ele x,t,a,b;
scanf("%lld%lld%lld%lld",&x,&t,&a,&b); --t;
e[i<<1]=(evt){1,x,t,a};
e[i<<1|1]=(evt){-1,x,t,b+1};
}
sort(e,e+n*2);
for (int i=0; i<Q; ++i){
ele l,y;
scanf("%lld%lld",&l,&y);
q[i]=(ask){l,y,i};
}
sort(q,q+Q);
tot=0; memset(cnt,0,sizeof(cnt));
r1=r2=NULL;
for (int i=0; i<k; ++i) S[i].insert(-INF),S[i].insert(INF),ins(-INF,INF);
ele j=0;
for (int i=0; i<Q; ++i){
for (; j<n*2 && e[j].a<=q[i].y; ++j)
if (~e[j].ty){
if (!cnt[e[j].t]) ++tot; ++cnt[e[j].t];
S[e[j].t].insert(e[j].x);
auto it=S[e[j].t].find(e[j].x),it1=it,it2=it;
--it1; ++it2;
del(*it1,*it2); ins(*it1,*it); ins(*it,*it2);
}
else{
--cnt[e[j].t]; if (!cnt[e[j].t]) --tot;
auto it=S[e[j].t].find(e[j].x),it1=it,it2=it;
--it1; ++it2;
del(*it1,*it); del(*it,*it2); ins(*it1,*it2);
S[e[j].t].erase(it);
}
if (tot!=k) res[q[i].id]=-1;
else{
ele ans=0;
node *u,*v;
split(r1,q[i].l-1,INF,u,v);
ans=max(ans,v->mx+q[i].l);
r1=merge(u,v);
split(r2,q[i].l,INF,u,v);
ans=max(ans,u->mx-q[i].l);
r2=merge(u,v);
res[q[i].id]=ans;
}
}
for (int i=0; i<Q; ++i) printf("%lld\n",res[i]);
return 0;
}