某岛

… : "…アッカリ~ン . .. . " .. .
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