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 —
