3514: Codechef MARCH14 GERALD07加强版

Time Limit: 60 Sec  Memory Limit: 256 MB

Submit: 1288  Solved: 490

[][][]

Description

N个点M条边的无向图，询问保留图中编号在[l,r]的边的时候图中的联通块个数。

Input

第一行四个整数N、M、K、type，代表点数、边数、询问数以及询问是否加密。

接下来M行，代表图中的每条边。

接下来K行，每行两个整数L、R代表一组询问。对于type=0的测试点，读入的L和R即为询问的L、R；对于type=1的测试点，每组询问的L、R应为L xor lastans和R xor lastans。

Output

 K行每行一个整数代表该组询问的联通块个数。

Sample Input

3 5 4 0

1 3

1 2

2 1

3 2

2 2

2 3

1 5

5 5

1 2

Sample Output

2

1

3

1

HINT

对于100%的数据，1≤N、M、K≤200,000。

2016.2.26提高时限至60s

Source

Solution

这应该算是动态图问题吧？？ 问了一下ShallWe，用LCT维护动态图问题的一种离线做法是维护一颗 时间最大生成树 ，所以这个也是一样。

思路非常的巧妙，首先维护一颗 时间最大生成树 ，按时间顺序加边。

设当前加边为$<u,v>$，如果$u$和$v$属于同一个联通块，则加入$<u,v>$必然会形成环，那么切掉这个环上的边权(时间)最小的边，连上这个边，记这个被切掉的边为$pop_{i}$

然后这个题要求联通块的个数，然后发现，对于$pop$存在一个性质：

对于一条边$x$，在边$x$和使边$x$被切的边$y$之间连上的边，是不会与使边$x$被切得边$y$出现环的，即如果$r>y>l>x$则$y$必然会使联通块-1

所以问题就可以转化为求$[l,r]$中$pop<l$的$pop$的个数，这个可以用主席树去维护，所以答案就是$N-sum$。

Code

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define INF 0x3fffffff#define MAXN 400010inline int read(){    int x=0,f=1; char ch=getchar();    while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}    while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}    return x*f;}int N,M,K,T,last;struct EdgeNode{int u,v;}edge[MAXN];namespace LCT{    int fa[MAXN],son[MAXN][2],id[MAXN],tim[MAXN]; bool rev[MAXN];    inline void Init() {for (int i=1; i<=N; i++) id[i]=i,tim[i]=INF;}    inline bool is_root(int x) {return !fa[x] || son[fa[x]][0]!=x&&son[fa[x]][1]!=x;}    inline int Min(int x,int y) {return tim[x]
           
            >1; if (val<=mid) Insert(l,mid,lson[now],lson[par],val); else Insert(mid+1,r,rson[now],rson[par],val); } inline int Query(int l,int r,int L,int R,int val) { if (r<=val) return sum[R]-sum[L]; int mid=(l+r)>>1; if (val<=mid) return Query(l,mid,lson[L],lson[R],val); else return Query(l,mid,lson[L],lson[R],val)+Query(mid+1,r,rson[L],rson[R],val); }}using namespace PrTree;int pop[MAXN];int main(){ N=read(),M=read(),K=read(),T=read(); for (int i=1; i<=M; i++) edge[i].u=read(),edge[i].v=read(); LCT::Init(); for (int i=1; i<=M; i++) { int u=edge[i].u,v=edge[i].v; if (u==v) {pop[i]=i; continue;} if (LCT::Find(u)==LCT::Find(v)) { pop[i]=LCT::Query(u,v); LCT::Cut(u,pop[i]); LCT::Cut(v,pop[i]); pop[i]-=N; } id[i+N]=i+N,tim[i+N]=i; LCT::Link(u,i+N); LCT::Link(v,i+N); }// for (int i=1; i<=M; i++) printf("%d ",pop[i]); puts(""); for (int i=1; i<=M; i++) PrTree::Insert(0,M,root[i],root[i-1],pop[i]); while (K--) { int L=read(),R=read(); if (T) L^=last,R^=last; printf("%d\n",last=N-Query(0,M,root[L-1],root[R],L-1)); } return 0;}