【题解】bzoj2391 Cirno的忧郁

Cirno 闲着无事的时候喜欢冰冻青蛙。

雾之湖生活着 $m$ 只青蛙,青蛙有大有小,所以每只青蛙的价值为一个不大于 $10000$ 的正整数。

Cirno 每次从雾之湖中固定的 $n$ 个结点中选出一些点构成一个简单多边形,Cirno 运用自己的能力能将此多边形内所有青蛙冰冻。Cirno 很想知道每次冻住的青蛙的价值总和。因为智商有限,Cirno 将这个问题交给完美算术教室里的你。

因为爱护动物,所以每次冻结的青蛙会被放生。也就是说一只青蛙可以被多次统计。

对于 $100\%$ 的数据,$n,m\leq 10^3, q\leq 10^4,-10^4\leq x,y\leq 10^4,0<v\leq 10^4$ 。

不知道为什么校内测试,某 NOIP 模拟题考了三角剖分…但不知道为什么一眼就看出是三角剖分。

紧接着发现是 bzoj 原题,学了一波三角剖分+温习了一遍向量之后感觉这题有点猛男。

大概考虑三角剖分本来是用于求多边形面积,方法是选择一个原点,按照逆时针或者顺时针的方式,把多边形顶点向量叉一圈的结果。形式化地讲,给定一个多边形 $A_1A_2A_3\ldots A_n$ ,那么这个多边形的面积就是

证明的话可能容斥可证,但我不会…我只知道两个向量的叉积是以这两个向量为临边的平行四边形的面积。

wjyyy的图

wjyyy的图

然后这里放了神仙 wjyyy 的图,看上去比较直观。

然后考虑这题怎么做。发现 $n+m$ 不大,于是考虑求一个 $f_{i,j}$ 表示向量 $\bf V_i$ 与 $\bf V_{j}$ 之间,$\bf V_{i}\to \bf V_{j}$ 需要逆时针旋转时,$i,j$ 之间的价值和。那么对于每一个询问 $\{s_n\}$ ,答案就是 $\sum f_{s_i,s_{i+1}}$ 。

考虑如何预处理这个东西。首先对所有向量按照极角逆时针排序(相等则模长大者位次靠后),枚举 $i$ ,之后就需要喜闻乐见的平衡树了。大概是这样:

其中红色向量是题目所给的向量,蓝色向量是辅助线。因为一开始就已经是逆时针排序,所以只需要判断每个向量的中点是否落在向量 $\bf i,j,t_2$ 构成的三角形即可。观察落在三角形内部的向量 $\bf k$ 和落在外部的向量 $\bf p$ ,会发现有

考虑向量夹角最大为 $\pi$ ,$y=\cos x$ 在 $[0,\pi]$ 上单调递减,于是可以知道要拿 $\cos x$ 作为键值,该向量的 $val$ 作为点值插入平衡树。其中 $\cos x$ 拿向量内积求即可。

最终复杂度 $O(n^2\log n+ms)$ 。

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
using namespace std ;

typedef double db ;

typedef long long ll ;

const int N = 2010 ;

const db eps = 1e-9 ;

int L ;
int cnt ;
int ans ;
int n, m, q ;
int f[N][N] ;


struct pts{
int id ; int val ; db x, y ;
il db mo() { return sqrt(x * x + y * y) ; }
il friend pts operator - (ct pts &p, ct pts &q){
return (pts){0, 0, p.x - q.x, p.y - q.y} ;
}
il friend db operator * (ct pts &p, ct pts &q){
return p.x * q.y - p.y * q.x ;
}
il friend db operator + (ct pts &p, ct pts &q){
return p.x * q.x + p.y * q.y ;
}
}v[N], org, calc[N] ;

il db cosi(pts a, pts b){
return (a + b) / (a.mo() * b.mo()) ;
}
il bool comp(pts a, pts b){
db ang = (a - org) * (b - org) ;
// cout << ang << '\n' ;
if (ang != eps) return ang > eps ;
return (a - org).mo() < (b - org).mo() ;
}

namespace _splay{
struct __splay{
int son[2] ;
int tot ;
int val ;
int sum ;
int fa ;
int sz ;
db key ;
}s[N] ;
#define sz(x) s[x].sz
#define fa(x) s[x].fa
#define val(x) s[x].val
#define key(x) s[x].key
#define tot(x) s[x].tot
#define sum(x) s[x].sum
#define lc(x) s[x].son[0]
#define rc(x) s[x].son[1]

int size ;
int root ;
bool w(int x){
return (x == rc(fa(x))) ;
}
void clear(){
for (int i = 0 ; i <= size ; ++ i){
sz(i) = lc(i) = rc(i) = fa(i) = 0 ;
tot(i) = val(i) = key(i) = sum(i) = 0 ;
}
size = 0 ; root = 0 ;
}
void upd(int x){
sz(x) = tot(x) ;
sum(x) = val(x) ;
if (lc(x)){
sz(x) += sz(lc(x)) ;
sum(x) += sum(lc(x)) ;
}
if (rc(x)){
sz(x) += sz(rc(x)) ;
sum(x) += sum(rc(x)) ;
}
}
void rotate(int x){
int c = w(x) ;
int f1 = fa(x) ;
int f2 = fa(f1) ;
if (!f2) root = x ;
else s[f2].son[w(f1)] = x ;
fa(x) = f2 ; fa(f1) = x ;
fa(s[x].son[c ^ 1]) = f1 ;
s[f1].son[c] = s[x].son[c ^ 1] ;
s[x].son[c ^ 1] = f1 ; upd(f1), upd(x) ;
}
void splay(int x, int aim){
while (fa(x) != aim){
if (fa(fa(x)) != aim)
rotate(w(x) == w(fa(x)) ? fa(x) : x) ;
rotate(x) ;
}
}
void Ins(int &x, db ky, int v, int dad){
if (!x){
x = ++ size ;
fa(x) = dad ;
key(x) = ky ;
val(x) = sum(x) = v ;
return ;
}
if (ky < key(x))
Ins(lc(x), ky, v, x) ;
else Ins(rc(x), ky, v, x) ; upd(x) ;
}
}

using namespace _splay ;

int main(){
org.x = -100000 ;
org.y = -100000 ;
cin >> n >> m ;
db x, y, w ; int z, h, r ;
for (int i = 1 ; i <= n ; ++ i)
cin >> x >> y, v[++ cnt] = (pts){i, 0, x, y} ;
for (int i = n + 1 ; i <= n + m ; ++ i)
cin >> x >> y >> w, v[++ cnt] = (pts){i, w, x, y} ;
sort(v + 1, v + cnt + 1, comp) ; m = n ; n = cnt ; cin >> q ;
for (int i = 1 ; i <= n ; ++ i){
if (v[i].id > m) continue ;
clear() ; pts o = v[i] - org ;
for (int j = i + 1 ; j <= n ; ++ j){
pts z = v[j] - v[i] ; db ky = cosi(o, z) ;
// cout << root << '\n' ;
Ins(root, ky, v[j].val, 0) ; splay(size, 0) ;
if(v[j].id <= m){
f[v[i].id][v[j].id] = sum(lc(root)) ;
f[v[j].id][v[i].id] = - sum(lc(root)) ;
}
}
}
/*
for (int i = 1 ; i <= n ; ++ i)
for (int j = 1 ; j <= n ; ++ j)
cout << f[i][j] << " \n"[j == n] ; */
while (q --){
cin >> L ; cin >> h ; r = h ;
for (int i = 1 ; i < L ; ++ i)
cin >> z, ans += f[h][z], h = z ;
ans += f[h][r] ; printf ("%d\n", abs(ans)) ; ans = 0 ;
}
return 0 ;
}

重写了一遍 splay,发现是真的慢+维护的信息真的多…

并且发现递归式的 splay 插入是真的好写。