Codechef 14.6 TWOCOMP 树链求交+网络流
Codechef 14.2 COT5 Treap+线段树

Codechef 14.3 GERALD07 LCT+可持久化线段树

shinbokuow posted @ Nov 20, 2015 04:15:25 PM in Something with tags LCT 可持久化线段树 , 553 阅读

 

题目大意:

给定一张$n$个点$m$条边的无向图,图中可能存在重边和自环,现在有$q$个询问,每次询问只保留标号在$[l,r]$区间内的边时,图中连通块的个数。
数据范围$n,m,q\leq{2\times{10^5}}$。
算法讨论:
一开始有$n$个连通块,对于一个区间中的边,那些两个端点之前没有连通的边,加入后会使得连通块的数目减少1。
所以我们只需知道哪些边是在加入这条边之前两个端点不连通的。
我们按照标号加入每条边,维护关于标号的最大生成树,并在加入这条边的时候,记录删掉了哪条边。
考虑区间$[l,r]$中的一条边$x$,若其弹掉了边$y$,则证明必须加入$y$这条边以及若干条之后的边,$x$的两个端点才能连通。因此,若$y<l$,则此时$x$的两个端点不连通,对答案产生$-1$的贡献;否则$y\leq{l}$,说明$[l,r]$中只使用$x$之前的某些边已经能让$x$的两个端点连通,对答案没有贡献。
使用Link-Cut Tree维护每个点弹掉了哪条边,对于每次询问其实就是询问区间$[l,r]$中弹掉边的标号$<l$的边的数目,可以用可持久化线段树维护。
时间复杂度$O((n+m+q)\log n)$。
时空复杂度:
时间复杂度$O((n+m+q)\log n)$,空间复杂度$O(n+m\log m+q)$。

代码:

#include <cstdio>
#include <cctype>
#include <cstring>
#include <climits>
#include <iostream>
#include <algorithm>
using namespace std;
 
inline int getc() {
    static const int L = 1 << 15;
    static char buf[L], *S = buf, *T = buf;
    if (S == T) { T = (S = buf) + fread(buf, 1, L, stdin); if (S == T) return EOF; }
    return *S++;
}
inline int getint() {
    int c;
    while(!isdigit(c = getc()));
    int tmp = c - '0';
    while(isdigit(c = getc()))
        tmp = (tmp << 1) + (tmp << 3) + c - '0';
    return tmp;
}
char buf[2000000], *o = buf;
void output(int x) {
    static int stack[100];
    int top = 0;
    for(; x; x /= 10)
        stack[++top] = 48 + x % 10;
    for(int i = top; i >= 1; --i)
        *o++ = stack[i];
    *o++ = '\n';
}
 
#define INF 0x3f3f3f3f
 
#define N 200010
#define M 200010
 
#define l ch[0]
#define r ch[1]
struct Node {
    Node *ch[2], *pa;
    int lab, Min;
    bool rev;
    Node():Min(INF),rev(0){}
     
    bool d() { return this == pa->r; }
    bool isRoot() { return this != pa->l && this != pa->r; }
    inline void sc(Node* p, bool d) { ch[d] = p, p->pa = this; }
    void RevIt() { rev ^= 1, swap(l, r); }
     
    void up();
    void down();
}Tnull, *null = &Tnull, mem[N + M], *C = mem, *Edge[M], *Point[N];
Node* Newnode(int _lab) {
    C->l = C->r = C->pa = null;
    C->lab = C->Min = _lab;
    C->rev = 0;
    return C++;
}
void Node::up() {
    Min = lab;
    if (l != null) Min = min(Min, l->Min);
    if (r != null) Min = min(Min, r->Min);
}
void Node::down() {
    if (rev) {
        if (l != null) l->RevIt();
        if (r != null) r->RevIt();
        rev = 0;
    }
}
 
void PushPath(Node *q) {
    static Node* stack[N + M];
    int top = 0;
    while(!q->isRoot())
        stack[++top] = q, q = q->pa;
    stack[++top] = q;
    for(int i = top; i >= 1; --i)
        stack[i]->down();
}
void Rot(Node *q) {
    Node *f = q->pa;
    bool d = q->d();
    q->pa = f->pa;
    if (!f->isRoot())
        f->pa->ch[f->d()] = q;
    f->sc(q->ch[!d], d);
    f->up();
    q->sc(f, !d);
}
void Splay(Node *q) {
    PushPath(q);
    while(!q->isRoot()) {
        if (q->pa->isRoot())
            Rot(q);
        else
            Rot(q->d() == q->pa->d() ? q->pa : q), Rot(q);
    }
    q->up();
}
void Access(Node *q) {
    Node *p = null;
    while(q != null) {
        Splay(q);
        q->r = p;
        q->up();
        p = q, q = q->pa;
    }
}
void Makeroot(Node *q) {
    Access(q);
    Splay(q);
    q->RevIt();
}
void Link(Node *p, Node *q) {
    Makeroot(p);
    p->pa = q;
}
void Cut(Node *p, Node* q) {
    Makeroot(p);
    Access(q);
    Splay(q);
    q->l = p->pa = null;
    q->up();
}
Node* FindRoot(Node *q) {
    while(q->pa != null)
        q = q->pa;
    return q;
}
int GetMin(Node *p, Node *q) {
    Makeroot(p);
    Access(q);
    Splay(q);
    return q->Min;
}
 
#define l(x) S[x].l
#define r(x) S[x].r
#define size(x) S[x].size
struct Seg {
    int l, r, size;
}S[4000010];
int id;
int root[M];
int NewVersion(int Last, int dl, int dr, int ins) {
    int q = ++id;
    S[q] = S[Last];
    ++size(q);
    if (dl == dr)
        return q;
 
    int mid = (dl + dr) >> 1;
    if (ins <= mid)
        l(q) = NewVersion(l(Last), dl, mid, ins);
    else
        r(q) = NewVersion(r(Last), mid + 1, dr, ins);
    return q;
}
int CalcLess(int Left, int Right, int dl, int dr, int ins) {
    int res = 0, mid;
    while(1) {
        if (dl == dr) {
            res += ((dl < ins) ? 1 : 0);
            break;
        }
        mid = (dl + dr) >> 1;
        if (mid >= ins)
            dr = mid, Left = l(Left), Right = l(Right);
        else
            dl = mid + 1, res += size(l(Right)) - size(l(Left)), Left = r(Left), Right = r(Right);
    }
    return res;
}
 
int w[N];
void init() {
    C = mem;
    id = 0;
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("tt.in", "r", stdin);
#endif
    
    int T = getint(), n, m, q;
    while (T--) {
        init();
        n = getint(), m = getint(), q = getint();    
        register int i;
        for(i = 1; i <= n; ++i)
            Point[i] = Newnode(INF);
        int a, b;
        memset(w, 0, sizeof w);
        for(i = 1; i <= m; ++i) {
            a = getint(), b = getint();
            if (a == b) {
                w[i] = i;
                continue;
            }
            Edge[i] = Newnode(i);
            if (FindRoot(Point[a]) == FindRoot(Point[b])) {
                int del = GetMin(Point[a], Point[b]);
                w[i] = del;
                Cut(Point[a], Edge[del]);
                Cut(Point[b], Edge[del]);
            }
            Link(Point[a], Edge[i]);
            Link(Point[b], Edge[i]);
        }
         
        for(i = 1; i <= m; ++i)
            root[i] = NewVersion(root[i - 1], 1, m + 1, w[i] + 1);
         
        int lastans = 0;
        while(q--) {
            a = getint(), b = getint();
            output(lastans = n - CalcLess(root[a - 1], root[b], 1, m + 1, a + 1));
        }
    }
    return fwrite(buf, 1, o - buf, stdout), 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter