某島

… : "…アッカリ~ン . .. . " .. .
June 15, 2014

SRM 624

250. BuildingHeights

Brief description:

給定 n 個建築的高度,你所能執行的唯一操作是將一個建築的高度 +1.。。
。。。。 f(k) 表示得到至少 k 個相同高度的建築,至少需要進行多少次操作。
Xor_{i=1}^n

Analysis:

。。排序、。之後枚舉目標建築的高度。。 $$O(n^2)$$ 暴力即可。。
。因為需要使用部分和。。。果斷從 1 標號吧!

450. DrivingPlans

Brief description:

給定一個 n 個結點的邊權非負的無向圖,問 1->n 最短路徑的方案數,
無窮時輸出 -1

Analysis:

沒有負環,有無窮多組方案數當且僅當最短路徑上存在權值和為 0 的迴路,因為邊權非負這種情況也就只需要判斷單條邊。
直接 Dijkstra 就可以了,基本中的基本。。

const int N = 2009;

VII adj[N];
int d1[N], dn[N], dp[N] , n;

priority_queue<PII, VII, greater<PII> > Q;

void relax(int d[], int u, int v, int w){
    if (d[v] > d[u] + w){
        d[v] = d[u] + w;
        Q.push(MP(d[v], v));
    }
}

#define v it->fi
#define w it->se

int gao(){
    VII I; REP_1(i, n) I.PB(MP(d1[i], i)); SRT(I);
    fill(dp+1, dp+n+1, 0); dp[1] = 1;

    ECH(it, I){
        int u = it->se; ECH(it, adj[u]) if (d1[u] + w == d1[v]){
            INC(dp[v], dp[u]);
        }
    }

    return dp[n];
}


void Dijkstra(int s, int d[]){
    while (!Q.empty()) Q.pop(); fill(d+1, d+n+1, INF); d[s] = 0; Q.push(MP(0, s));

    while (!Q.empty()){
        int du = Q.top().fi, u = Q.top().se; Q.pop();
        if (du != d[u]) continue; ECH(it, adj[u]){
            relax(d, u, v, w);
        }
    }
}

class DrivingPlans {
    public:
    int count(int n, vector <int> A, vector <int> B, vector <int> C) {

    	::n = n; REP_1(i, n) adj[i].clear(); REP(i, A.size()){
    		adj[A[i]].PB(MP(B[i] , C[i]));
    		adj[B[i]].PB(MP(A[i] , C[i]));
    	}

    	Dijkstra(1, d1); Dijkstra(n, dn);

    	REP(i, A.size()) if (!C[i]){
            if (d1[A[i]] + dn[B[i]] == d1[n]) {
                return -1;
            }
    	}

    	return gao();
    }

};

1000. TreeColoring

Brief description:

動態維護一個樹,支持,將一個點染成藍色。詢問 u 點到所有藍色結點的距離和。
。染色只有白色->藍色。。。初始都是白色、、

Analysis:

如果是子樹和的話。。就可以直接離線樹狀數組搞。。但是這個題是所有四周的和。。。。
。。。。似乎可以點分治不過動態樹的做法更加直覺。。

。。。。終於調過了。。。幾個月沒弄。。。動態樹竟變得如此生疏。。
。。。本地測試的時候需要彙編調棧。。。(但是這段代碼似乎必須放在 main() 函數中。。否則直接 RE ???)
。。。而 TC 是沒有 main() 函數的。。不過交上去似乎沒錯。。看來 TC 棧足夠的深。

。(。。比賽時若能用 LCT 全場 A 掉這題。。那將多麼華麗!!。。。)

————————

其實就這三行。。唉。。

     inline void upd(){
        sz = l->sz+c0+r->sz+_sz, dd = l->dd+d0+r->dd;
        ls = l->ls+_ls+r->ls+(l->dd+d0)*(sz-l->sz);
        rs = l->rs+_ls+r->rs+r->dd*(sz-r->sz)+(LL)d0*l->sz;
    }

做法就是三叉動態樹。。。。

    static node *NIL; node *c[2], *p; int _sz; LL _ls;
    int c0, d0, sz; LL dd, ls, rs;

c0: 是否染色。
d0: 到父親的邊權。
sz: 子樹中包含染色結點的個數。
dd: 重鏈的長度。

ls: 左端點出發的距離和。
rs: 右端點出發的距離和。

_sz: 虛孩子的 sz 和。。。
_ls: 虛孩子的 ls 和。。

如果比賽時大腦實在進水。。。不妨先考慮一條鏈版本的問題。。。
(給定一條鏈,每次 toggle() 一個點,詢問所有染色點到某個點的距離和 )
(顯然我們可以使用 splay 去維護這個問題。。略加思索。。。。upd() 的雛形就有了。。)
(。之後把 _sz_ls 一併考慮進來就可以了。。虛孩子的作用和右孩子是一致的。。)

詢問的時候我們 access() 這個點。。那麼它現在就成為一條重鏈的末尾(右端點)。。
。。因此此時 rs 就是答案。。。


const int N = int(1e5) + 9, M = 2 * N;

namespace LCT{

struct node{

    static node *NIL; node *c[2], *p; int _sz; LL _ls;
    int c0, d0, sz; LL dd, ls, rs; //bool r0;

#define NIL node::NIL
#define l c[0]
#define r c[1]
#define lx x->l
#define rx x->r
#define px x->p
#define ly y->l
#define ry y->r
#define py y->p

    void reset(){
        l = r = p = NIL; _sz = _ls = 0;
        c0 = d0 = sz = dd = 0; ls = rs = 0; //r0 = 0;
    }

    inline node(){
        reset();
    }

    inline void rev(){
        //r0 ^= 1; swap(l, r); swap(ls, rs);
    }

    inline void upd(){
        sz = l->sz+c0+r->sz+_sz, dd = l->dd+d0+r->dd;
        ls = l->ls+_ls+r->ls+(l->dd+d0)*(sz-l->sz);
        rs = l->rs+_ls+r->rs+r->dd*(sz-r->sz)+(LL)d0*l->sz;
    }

    inline void rls(){
        /*if (r0){
            l->rev(), r->rev();
            r0 = 0;
        }*/
    }

    inline int sgn(){return p->l==this?0:p->r==this?1:-1;}
    inline void setc(int d,node*x){c[d]=x,px=this;}

    inline void rot(int d){
        node*y=p,*z=py;if(~y->sgn())z->setc(y->sgn(),this);else p=z;
        y->setc(d,c[!d]),setc(!d,y),y->upd();
    }
    inline void rot(){rot(sgn());}

    inline void fix(){if (~sgn()) p->fix(); rls();}
/*
    inline node* splay(){
        fix();while (~sgn()) rot(); upd();
        return this;
    }
*/

    inline node*splay(){
        fix();int a,b;while(~(a=sgn())){
            if(~(b=(p->sgn())))(a^b?this:p)->rot(a),rot(b);
            else rot(a);
        }
        upd();
        return this;
    }

    inline node* acs(){
        node *x = this, *y = NIL; do{
            x->splay();
            if (y != NIL) x->_sz -= y->sz, x->_ls -= y->ls;
            if (rx != NIL) x->_sz += rx->sz, x->_ls += rx->ls;
            rx = y, x->upd();
            y = x, x = px;
        } while (x != NIL);
        return splay();
    }

    inline node* rt(){node* x; for (x = acs(); x->rls(), lx != NIL; x = lx); return x->splay();}
    inline node* ert(){acs()->rev(); return this;}

    void cut(){
        acs(); l->p = l = NIL;
    }

    void tog(){
        acs(); c0 = 1;
    }

    LL query(){
        acs(); return rs;
    }

} *NIL, *T[N];



int hd[N], suc[M], to[M], ww[N], n;
#define aa to[i^1]
#define bb to[i]
#define w ww[i/2]
#define v bb

inline void dfs(int u){
    REP_G(i, u) if (T[v]->p == NIL){
        T[v]->p = T[u], T[v]->d0 = w, dfs(v);
    }
    T[u]->upd();
}

} using namespace LCT;

void init(){
    NIL = new node(); REP(i, N) T[i] = new node();
}

int curValue; int genNextRandom() {
    curValue = ((LL)curValue * 1999 + 17) % 1000003;
    return curValue;
}

int distancee[N], parent[N], queryType[N], queryNode[N];

class TreeColoring {
public:
	long long color(int n, int Q, int startSeed, int threshold, int maxDist) {

        curValue = startSeed;

        for (int i = 0; i < n-1; i++) {
            distancee[i] = genNextRandom() % maxDist;
            parent[i] = genNextRandom();
            if (parent[i] < threshold) {
                parent[i] = i;
            } else {
                parent[i] = parent[i] % (i + 1);
            }
        }

        for (int i = 0; i < Q; i++) {
            queryType[i] = genNextRandom() % 2 + 1;
            queryNode[i] = genNextRandom() % n + 1;
        }

        // gen input..

        if (!NIL) init(); else fill(hd+1, hd+n+1, 0);
        REP_1(i, n) T[i]->reset();

        int i = 2; FOR_1(ii, 2, n){
            aa = ii, bb = parent[ii-2]+1, w = distancee[ii-2];
            suc[i] = hd[aa], hd[aa] = i++;
            suc[i] = hd[aa], hd[aa] = i++;
        }

        T[1]->p = T[0]; dfs(1); T[1]->p = NIL;

        LL res = 0; REP(i, Q){
            switch(queryType[i]){
                case 2:
                    res ^= T[queryNode[i]]->query();
                break;
                default:
                    T[queryNode[i]]->tog();
            }
        }

		return res;
	}
};

— UPD —

External link:

https://gist.github.com/lychees/27fd8661bd8489244d93