bzoj2049 线段树 + 可撤销并查集-白红宇

bzoj2049 线段树 + 可撤销并查集

阅读量：4700 次

发布时间：2019-06-09

本文共 3931 字，大约阅读时间需要 13 分钟。

https://www.lydsy.com/JudgeOnline/problem.php?id=2049

线段树真神奇

题意：给出一波操作，拆边加边以及询问两点是否联通。

听说常规方法是在线LCT，留坑。

如果说这个删边的操作是删除上一条边，那这自然是可撤销并查集的模板题，直接在线维护就可以了。

但是问题在于删除边的顺序是不可能固定的，要知道并查集是不可以随意撤销的。

万万没想到还有更加高妙的手法。

首先可以证明一条边的存在一定是一段或者多段连续的区间。

建立一条时间节点长度的线段树，结点维护一个边集合，每个位置表示的是当前这个时间下存在了哪几条边。

将上述的边区间全部加入，和常规的线段树不一样，这个不需要lazy标记也不需要Pushdown到下属区间，为了节省时间和空间，对于1 - N区间的边来说，我们仅仅把1号结点加上这条边。

然后用dfs的方法，进入结点时加上这些边，离开的时候删除这些边，在线段树的叶子节点上，并查集维护的就是当前时间的状态，离线的query直接询问即可。

时间复杂度，加边的整个过程mlogm,询问的过程节点数mlogm * 并查集find操作logm = mlog²m

#include #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    using namespace std;#define For(i, x, y) for(int i=x;i<=y;i++) #define _For(i, x, y) for(int i=x;i>=y;i--)#define Mem(f, x) memset(f,x,sizeof(f)) #define Sca(x) scanf("%d", &x)#define Sca2(x,y) scanf("%d%d",&x,&y)#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)#define Scl(x) scanf("%lld",&x); #define Pri(x) printf("%d\n", x)#define Prl(x) printf("%lld\n",x); #define CLR(u) for(int i=0;i<=N;i++)u[i].clear();#define LL long long#define ULL unsigned long long #define mp make_pair#define PII pair
                    
                     #define PIL pair
                     
                      #define PLL pair
                      
                       #define pb push_back#define fi first#define se second typedef vector
                       
                         VI;int read(){ int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){ if (c == '-') f = -1;c = getchar();}while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}const double eps = 1e-9;const int maxn = 1e5 + 10;const int maxm = 2e6 + 10;const int INF = 0x3f3f3f3f;const int mod = 1e9 + 7; int N,M,K;struct Query{ int t,u,v; Query(){} Query(int t,int u,int v):t(t),u(u),v(v){}}q[maxm];struct Line{ int op,u,v; Line(){} Line(int op,int u,int v):op(op),u(u),v(v){}}line[maxm];map
                        
                         Q;int Stack[maxm],top;int size[maxn],fa[maxn];void init(){ for(int i = 0; i <= N ; i ++){ fa[i] = -1; size[i] = 0; } top = 0;}//segment_treestruct Tree{ int l,r; int head;}tree[maxm << 2];struct Edge{ PII data; int next;}edge[maxm << 2];int tot,cnt,cnt2;void add(int u,PII v){ edge[tot].next = tree[u].head; edge[tot].data = v; tree[u].head = tot++;}void Build(int t,int l,int r){ tree[t].l = l; tree[t].r = r; tree[t].head = -1; if(l == r) return; int m = (l + r) >> 1; Build(t << 1,l,m); Build(t << 1 | 1,m + 1,r);}void update(int t,int l,int r,PII v){ if(l <= tree[t].l && tree[t].r <= r){ add(t,v); return; } int m = (tree[t].l + tree[t].r) >> 1; if(r <= m) update(t << 1,l,r,v); else if(l > m) update(t << 1 | 1,l,r,v); else{ update(t << 1,l,m,v); update(t << 1 | 1,m + 1,r,v); }}int find(int x){ while(fa[x] != -1) x = fa[x]; return x;}void Union(int x,int y){ x = find(x); y = find(y); if(x == y) return; if(size[x] > size[y]) swap(x,y); Stack[top++] = x; fa[x] = y; size[y] += size[x] + 1;}void rewind(int t){ while(top > t){ int x = Stack[--top]; size[fa[x]] -= size[x] + 1; fa[x] = -1; }}void dfs(int t){ int now = top; for(int i = tree[t].head; ~i; i = edge[i].next){ PII v = edge[i].data; Union(v.fi,v.se); } if(tree[t].l == tree[t].r){ while(tot <= cnt2 && q[tot].t == tree[t].l){ if(find(q[tot].u) == find(q[tot].v)){ puts("Yes"); }else{ puts("No"); } tot++; } rewind(now); return; } dfs(t << 1); dfs(t << 1 | 1); rewind(now);}int main(){ Sca2(N,M); init(); cnt = 0,cnt2 = 0; for(int i = 1; i <= M ; i ++){ char op[10]; int u,v; scanf("%s%d%d",op,&u,&v); if(u > v) swap(u,v); if(op[0] == 'Q') q[++cnt2] = Query(cnt,u,v); else if(op[0] == 'C') line[++cnt] = Line(0,u,v); else line[++cnt] = Line(1,u,v); } tot = 0; Build(1,0,cnt); for(int i = 1; i <= cnt; i ++){ int &x = Q[mp(line[i].u,line[i].v)]; if(line[i].op == 0) x = i; else{ update(1,x,i - 1,mp(line[i].u,line[i].v)); x = 0; } } for(map
                         
                          ::iterator it = Q.begin(); it != Q.end(); it++){ pair
                          
                            u = *it; if(u.se) update(1,u.se,cnt,u.fi); } tot = 1; dfs(1); return 0;}

转载于:https://www.cnblogs.com/Hugh-Locke/p/10367480.html

你可能感兴趣的文章