http://acmicpc.info/archives/1710
http://blog.renren.com/blog/271960376/918770698?bfrom=01020110200
https://gist.github.com/lychees/803f6e6a61c0f393660a
Problem D. Bathysphere
Brief description:
。。。x 轴上方给定一段折线。（一个分段线性可积函数）。
。。求 d 宽度的窗口内的最大面积。。。
Analysis:
Two Point 解方程
为了处理方便我们先准备一些辅助函数。。。
inline DB yy(int i, DB xx){ // 求横坐标为 xx 时的函数值。。
return y[i] + (xx-x[i])*slope[i];
}
inline DB s(int i, DB st, DB ed){ //求 st 到 ed 这段区间的面积。。
return (ed-st)*(yy(i,st)+yy(i,ed));
}
考虑 Two Point 的部分。。我们用 ll, rr 记录当前窗口的位置。。（rr-ll 总等于 d。。。再用 l， r 记录其左侧第一个结点的位置。。。
...
for (;r<n-1;l+=ll==x[l+1],r+=rr==x[r+1]){
int d = min(x[r+1]-rr, x[l+1]-ll); DB a = slope[r]-slope[l], b = (yy(r,rr)-yy(l,ll))*2; if (sgn(a)){
DB dd = -b/(2*a); if (sgn(.0, dd) < 0 && sgn(dd, DB(d)) < 0){
checkMax(res, pre-(b*b/a/4));
}
}
checkMax(res, pre += s(r,rr,rr+d)-s(l,ll,ll+d));
ll+=d,rr+=d;
}
...
。。就是每次我们取移动的步长 d…。。
。。然后解这个窗口内二次方程。。看极值点是否落在步长范围之内。。
。。更新完之后。。再移动两个端点。。。
我们直接在移动端点的同时再尝试更新一次答案。。（因为有可能出现方程退化情况。。
const int N = int(2e5) + 9;
int x[N], y[N], n; DB slope[N];
int D;
inline DB yy(int i, DB xx){
return y[i] + (xx-x[i])*slope[i];
}
inline DB s(int i, DB st, DB ed){
return (ed-st)*(yy(i,st)+yy(i,ed));
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif
Rush{
RD(n); RD(); REP(i, n) RD(x[i], y[i]); RD(D)*=2;
REP(i, n-1) slope[i] = (DB)(y[i+1]-y[i])/(x[i+1]-x[i]);
DB res = 0, pre = 0; int r; REP_N(r, n-1){
if (x[r+1] >= D) break;
pre += s(r,x[r],x[r+1]);
}
checkMax(res, pre += s(r, x[r], D));
int l=0,ll=0,rr=D;r+=rr==x[r+1];
for (;r<n-1;l+=ll==x[l+1],r+=rr==x[r+1]){
int d = min(x[r+1]-rr, x[l+1]-ll); DB a = slope[r]-slope[l], b = (yy(r,rr)-yy(l,ll))*2; if (sgn(a)){
DB dd = -b/(2*a); if (sgn(.0, dd) < 0 && sgn(dd, DB(d)) < 0){
checkMax(res, pre-(b*b/a/4));
}
}
checkMax(res, pre += s(r,rr,rr+d)-s(l,ll,ll+d));
ll+=d,rr+=d;
}
OT(res/D/2);
}
}
Problem J. Tri-war
Brief description:
。。给定 $$n$$ 个结点的一棵树。。每次询问三个点 $$u_0, u_1, u_2$$。。。
。。。点 $$v$$ 被 $$u_x$$ 支配 。。如果 $$\forall y \not = x, d(u_x, v) < d(u_y, v) $$。。
。。。问这三个点所在的支配集的大小。。。
Analysis:
倍增祖先 LCA 分类讨论
两个点的情况：
。先铺好模板。。显然就是。。。。。（。Codeforces Round #140 和 SPOJ 1486. The Ants in a Tree
。。考虑 2 个点的。。设函数 up(u, k) 表示 $$u$$ 结点向上 $$k$$ 个位置的结点。。。
。。那么通过 倍增祖先 我们就可以将中点找到。。。之后根据路径的奇偶性讨论一下即可。。。
最后要么是。。。
u0 --- m --- u1
（这种情况存在着一些 灰色结点。。（既不属于 $$u_0$$ 也不属于 $$u_1$$。。
要么是。。。
u0 --- m0 --- m1 --- u1
。。。复杂度 $$O(log(n))$$。。。（对于有边权的情况。。复杂度好像仍然是 $$O(log(n))$$ ？。。可以一边二分一边向上跳？）
。。。合理的使用 swap 以提高对讨论的抗性。。、、。。
（本题中 swap 的情况目测会茫茫多。。我们直接使用 ans[] 来记录答案。。）
void gao(int x, int y){
int z = lca(x,y), dx = dep[x]-dep[z], dy = dep[y]-dep[z], dd = dx+dy;
int d = dd/2; if (d>=dx) swap(x, y), swap(dx, dy); int m = up(x,d);
if (dd&1) ans[x] = sz[m], ans[y] = n-ans[x];
else ans[x] = sz[up(x,d-1)], ans[y] = d==dx?sz[up(y,d-1)]:n-sz[m];
}
三个点的情况：
。。。。现在讨论三个点的情况。。。
。。先按照 dep 对询问点排序。。
Case 1：链状
这种情况，$$u_0$$ 和 $$u_2$$ 都是它们各自对 $$u_1$$ 两个点时的答案。。。
。。。再把 $$u_1$$ 容斥出来。。。
void gao(int u0, int u1, int u2){
gao(u1, u2); int g = n-ans[u1]-ans[u2]; gao(u0, u1);
ans[u1] -= ans[u2]+g;
}
Case 2：叉状
我们求出三者的汇点 $$m$$。。并重新将询问的结点按照到 $$m$$ 的距离排序。。
m = entry(u0, u1, u2); SRT(I, cmp);
Case 2-1：$$m$$ 被其中一个结点支配
这种情况，$$u_1$$ 和 $$u_2$$ 都是它们各自对 $$u_0$$ 两个点时的答案。。。
。。。类似的。。再把 $$u_0$$ 容斥出来。。。
gao(u1, u0); int g1 = n-ans[u0]-ans[u1];
gao(u0, u2); int g2 = n-ans[u0]-ans[u2];
ans[u0] = n-ans[u1]-ans[u2]-g1-g2;
Case 2-2：$$m$$ 是灰色结点
这种情况还得分两种情况讨论。（恰好两个结点到 $$m$$ 距离相等，和三个结点到 $$m$$ 距离都相等。。）
。。但是处理起来恰好可以做到完全一样。。。。
最后注意 HDU 直接交会 dfs() 爆栈。。。
这里我使用了汇编调栈。。。。
const int N = int(1e5)+9, M = 2*N, LV = 18;
int hd[N], suc[M], to[M];
int ST[LV+1][M], sz[N], fa[N][LV], st[N], dep[N];
int n, tt;
inline bool elder(int a, int b){
return dep[a] < dep[b];
}
inline int lca(int a, int b){
int l = st[a], r = st[b]; if (l > r) swap(l, r); ++r; int lv = lg2(r-l);
return min(ST[lv][l], ST[lv][r-(1<<lv)], elder);
}
bool isa(int u1, int u2){
return lca(u1, u2) == u1;
}
int entry(int x, int y, int w){
int xy = lca(x, y); if (!isa(xy, w)) return xy; int xw = lca(x, w);
return xw != xy ? xw : lca(y, w);
}
inline int d(int x, int y){
return dep[x]+dep[y]-2*dep[lca(x,y)];
}
inline int up(int x, int t){
for (int i=0;i<LV&&t;++i,t>>=1)
if (t&1) x = fa[x][i];
return x;
}
#define aa to[i^1]
#define bb to[i]
#define v bb
void dfs(int u = 1){
ST[0][st[u] = ++tt] = u, sz[u] = 1;
REP_G(i, u) if (!st[v]){
dep[v] = dep[u] + 1, fa[v][0] = u; FOR(lv, 1, LV) fa[v][lv] = fa[fa[v][lv-1]][lv-1];
dfs(v), ST[0][++tt] = u, sz[u] += sz[v];
}
}
#undef v
int ans[N], m;
bool cmp(int a, int b){
return d(a, m) < d(b, m);
}
void gao(int x, int y){
int z = lca(x,y), dx = dep[x]-dep[z], dy = dep[y]-dep[z], dd = dx+dy;
int d = dd/2; if (d>=dx) swap(x, y), swap(dx, dy); int m = up(x,d);
if (dd&1) ans[x] = sz[m], ans[y] = n-ans[x];
else ans[x] = sz[up(x,d-1)], ans[y] = d==dx?sz[up(y,d-1)]:n-sz[m];
}
void gao(int u0, int u1, int u2){
gao(u1, u2); int g = n-ans[u1]-ans[u2]; gao(u0, u1);
ans[u1] -= ans[u2]+g;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif
int __size__ = 256 << 20; // 256MB
char *__p__ = (char*)malloc(__size__) + __size__;
__asm__("movl %0, %%esp\n" :: "r"(__p__));
Rush{
FOR_C(i, 2, RD(n)<<1){
RD(aa, bb);
suc[i] = hd[aa], hd[aa] = i, ++i;
suc[i] = hd[aa], hd[aa] = i;
}
dfs();
for ( int lv = 1 ; (1 << lv) <= tt ; lv ++ ){
for ( int i = 1 ; i + (1 << lv) <= tt + 1 ; i ++ )
ST[lv][i] = min(ST[lv-1][i], ST[lv-1][i + (1<<(lv-1))], elder);
}
Rush{
int u0, u1, u2; RD(u0, u1, u2);
VI I; I.PB(u0), I.PB(u1), I.PB(u2); SRT(I, elder);
#define u0 I[0]
#define u1 I[1]
#define u2 I[2]
if (isa(u0, u1) && isa(u1, u2)){
gao(u0, u1, u2); // Case 1
}
else{
m = entry(u0, u1, u2); SRT(I, cmp);
if (d(u0,m) < d(u1,m)){ // Case 2.1
gao(u1, u0); int g1 = n-ans[u0]-ans[u1];
gao(u0, u2); int g2 = n-ans[u0]-ans[u2];
ans[u0] = n-ans[u1]-ans[u2]-g1-g2;
}
else{ // Case 2.2
gao(u0, u2), gao(u0, u1);
}
}
#undef u0
#undef u1
#undef u2
printf("%d %d %d\n", ans[u0], ans[u1], ans[u2]);
}
fill(hd+1, hd+n+1, 0);
fill(st+1, st+n+1, 0);
tt = 0;
}
}
