HDOJ 4509 湫湫系列故事——减肥记II（2013腾讯编程马拉松）并查集合并区间-白红宇

HDOJ 4509 湫湫系列故事——减肥记II（2013腾讯编程马拉松）并查集合并区间

阅读量：5119 次

发布时间：2019-06-13

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

发现这种合并区间的题目还可以这么玩

给你n段时间然后问没被占用的时间是多少

题目所给的区间是右开的导致我wa

好多人5e5*1440的暴力跑出来的时间居然只是我的两倍不懂....

所以并查集并没有跑的很快奇怪....

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
            7 #include 
            
              8 using namespace std; 9 typedef long long ll;10 const int maxn = 5e5+100;11 int par[maxn];12 int l[maxn],r[maxn];13 bool vis[maxn];14 void init(int n_)15 {16 for(int i=0;i<=n_;i++)17 {18 par[i] = i;19 l[i] = r[i] = i;20 }21 memset(vis,false,sizeof(vis));22 }23 int find(int x)24 {25 if(x!=par[x])26 {27 return par[x] = find(par[x]);28 }29 return x;30 }31 void unite(int x,int y)32 {33 x = find(x);34 y = find(y);35 if(x==y) return ;36 par[x] = y;37 l[y] = min(l[y],l[x]);38 r[y] = max(r[y],r[x]);39 40 return ;41 }42 void make(int x,int y)43 {44 int pre = x;45 for(int i=x;i