BZOJ 3514 Codechef MARCH14 GERALD07加強版 LCT+主席樹

題目大意：N個點M條邊的無向圖，詢問保留圖中編号在[l,r]的邊的時候圖中的聯通塊個數。

思路：看到了wulala的題解，這裡就直接粘過來了。

蔥娘說這是一個很巧妙的題。。

有一個比較獵奇的做法：首先把邊依次加到圖中，若目前這條邊與圖中的邊形成了環，那麼把這個環中最早加進來的邊彈出去

并将每條邊把哪條邊彈了出去記錄下來：ntr[i] = j，特别地，要是沒有彈出邊，ntr[i] = 0;

這個顯然是可以用LCT來弄的對吧。

然後對于每個詢問，我們的答案就是對l~r中ntr小于l的邊求和，并用n減去這個值

正确性可以YY一下：

如果一條邊的ntr >= l,那麼顯然他可以與從l ~ r中的邊形成環，那麼它對答案沒有貢獻

反之如果一條邊的ntr < l那麼它與從l ~ r中的邊是不能形成環的，那麼他對答案的貢獻為-1

對于查詢從l ~ r中有多少邊的ntr小于l，我反正是用的函數式線段樹

看了題解才會做的人傷不起啊。。。

做法已經很詳細了，就直接貼代碼了。

CODE：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define INF 0x3f3f3f3f
#define MAX 200010
#define RANGE 7000010
using namespace std;
 
struct Edge{
    int x,y;
}edge[MAX];
 
struct SplayTree{
    SplayTree *son[2],*father;
    int val,_min;
    bool reverse;
     
    SplayTree(int _);
    bool Check() {
        return father->son[1] == this;
    }
    void Reverse() {
        reverse ^= 1;
        swap(son[0],son[1]);
    }
    void PushDown() {
        if(father->son[0] == this || father->son[1] == this)
            father->PushDown();
        if(reverse) {
            son[0]->Reverse();
            son[1]->Reverse();
            reverse = false;
        }
    }
    void PushUp() {
        _min = min(son[0]->_min,son[1]->_min);
        _min = min(_min,val);
    }
}none(INF),*nil = &none,*tree[MAX << 1];
SplayTree:: SplayTree(int _) {
    val = _min = _;
    son[0] = son[1] = father = nil;
    reverse = false;
}
 
int points,edges,asks;
int type,last_ans;
int ntr[MAX];
 
inline void Rotate(SplayTree *a,bool dir)
{
    SplayTree *f = a->father;
    f->PushDown(),a->PushDown();
    f->son[!dir] = a->son[dir];
    f->son[!dir]->father = f;
    a->son[dir] = f;
    if(f->father->son[0] == f || f->father->son[1] == f)
        f->father->son[f->Check()] = a;
    a->father = f->father;
    f->father = a;
    f->PushUp();
}
 
inline void Splay(SplayTree *a)
{
    a->PushDown();
    while(a->father->son[0] == a || a->father->son[1] == a) {
        SplayTree *f = a->father;
        if(f->father->son[0] != f && f->father->son[1] != f)
            Rotate(a,!a->Check());
        else if(!f->Check()) {
            if(!a->Check())  
                Rotate(a->father,true),Rotate(a,true);
            else    Rotate(a,false),Rotate(a,true);
        }
        else {
            if(a->Check())
                Rotate(a->father,false),Rotate(a,false);
            else    Rotate(a,true),Rotate(a,false);
        }
    }
    a->PushUp();
}
 
inline void Access(SplayTree *a)
{
    SplayTree *temp = nil;
    while(a != nil) {
        Splay(a);
        a->son[1] = temp;
        a->PushUp();
        temp = a;
        a = a->father;
    }
}
 
inline SplayTree *FindRoot(SplayTree *a)
{
    while(a->father != nil)
        a = a->father;
    return a;
}
 
inline void ToRoot(SplayTree *a)
{
    Access(a);
    Splay(a);
    a->Reverse();
}
 
inline void Link(SplayTree *x,SplayTree *y)
{
    ToRoot(y);
    y->father = x;
}
 
inline void Cut(SplayTree *x,SplayTree *y)
{
    ToRoot(x);
    Access(y);
    Splay(y);
    x->father = nil;
    y->son[0] = nil;
    y->PushUp();
}
 
inline void Insert(const Edge &e,int p)
{
    if(e.x == e.y) {
        ntr[p] = p;
        return ;
    }
    SplayTree *fx = FindRoot(tree[e.x]),*fy = FindRoot(tree[e.y]);
    if(fx == fy) {
        ToRoot(tree[e.x]);
        Access(tree[e.y]);
        Splay(tree[e.y]);
        int _min = tree[e.y]->_min;
        ntr[p] = _min;
        Cut(tree[edge[_min].x],tree[points + _min]);
        Cut(tree[edge[_min].y],tree[points + _min]);
    }
    tree[points + p] = new SplayTree(p);
    Link(tree[points + p],tree[e.x]);
    Link(tree[points + p],tree[e.y]);
}
 
struct SegTree{
    SegTree *son[2];
    int cnt;
     
    void *operator new(size_t,SegTree *_,SegTree *__,int ___);
}*seg_tree[MAX],mempool[RANGE],*C = mempool;
void *SegTree:: operator new(size_t,SegTree *_,SegTree *__,int ___) {
    C->son[0] = _;
    C->son[1] = __;
    C->cnt = ___;
    return C++;
}
 
SegTree *Modify(SegTree *last,int l,int r,int x)
{
    if(l == r)
        return new(NULL,NULL,last->cnt + 1)SegTree;
    int mid = (l + r) >> 1;
    if(x <= mid) return new(Modify(last->son[0],l,mid,x),last->son[1],last->cnt + 1)SegTree;
    return new(last->son[0],Modify(last->son[1],mid + 1,r,x),last->cnt + 1)SegTree;
}
 
int Ask(SegTree *contrast,SegTree *now,int l,int r,int x,int y)
{
    if(l == x && y == r)
        return now->cnt - contrast->cnt;
    int mid = (l + r) >> 1;
    if(y <= mid) return Ask(contrast->son[0],now->son[0],l,mid,x,y);
    if(x > mid)      return Ask(contrast->son[1],now->son[1],mid + 1,r,x,y);
    int left = Ask(contrast->son[0],now->son[0],l,mid,x,mid);
    int right = Ask(contrast->son[1],now->son[1],mid + 1,r,mid + 1,y);
    return left + right;
}
 
int main()
{
    cin >> points >> edges >> asks >> type;
    for(int i = 1; i <= points; ++i)
        tree[i] = new SplayTree(INF);
    for(int i = 1; i <= edges; ++i) {
        scanf("%d%d",&edge[i].x,&edge[i].y);
        Insert(edge[i],i);
    }
    seg_tree[0] = new(C,C,0)SegTree;
    for(int i = 1; i <= edges; ++i)
        seg_tree[i] = Modify(seg_tree[i - 1],0,edges,ntr[i]);
    for(int x,y,i = 1; i <= asks; ++i) {
        scanf("%d%d",&x,&y);
        if(type)    x ^= last_ans,y ^= last_ans;
        if(x > y)    swap(x,y);
        last_ans = points - Ask(seg_tree[x - 1],seg_tree[y],0,edges,0,x - 1);
        printf("%d\n",last_ans);
    }
    return 0;
}