ACM-ICPC Regional Asia Changchun 2013 Onsite

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。。。再用 lr 記錄其左側第一個結點的位置。。。

...
        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:

。。給定 個結點的一棵樹。。每次詢問三個點 。。。
。。。點 支配 。。如果 。。 。。。問這三個點所在的支配集的大小。。。

Analysis:

倍增祖先 LCA 分類討論

兩個點的情況:

。先鋪好模板。。顯然就是。。。。。(。Codeforces Round #140SPOJ 1486. The Ants in a Tree

。。考慮 2 個點的。。設函數 up(u, k) 表示 結點向上 個位置的結點。。。
。。那麼通過 倍增祖先 我們就可以將中點找到。。。之後根據路徑的奇偶性討論一下即可。。。

最後要麼是。。。

u0  --- m --- u1 

(這種情況存在著一些 灰色結點。。(既不屬於 也不屬於 。。
要麼是。。。

u0 --- m0 --- m1 --- u1

。。。複雜度 。。。(對於有邊權的情況。。複雜度好像仍然是 ?。。可以一邊二分一邊向上跳?)

。。。合理的使用 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:鏈狀

這種情況, 都是它們各自對 兩個點時的答案。。。
。。。再把 容斥出來。。。

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 = entry(u0, u1, u2); SRT(I, cmp);
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;
Case 2-2: 是灰色結點

這種情況還得分兩種情況討論。(恰好兩個結點到 距離相等,和三個結點到 距離都相等。。)
。。但是處理起來恰好可以做到完全一樣。。。。

最後注意 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;
    }
}