LA_4730 Kingdom 并查集+树状数组

给定N个点的坐标，代表N各城市，有M种操作，共分两种，一种是连线，把两个点连起来（一旦构成连通图，这个连通图即为一个州），还有种询问操作，为y=c，（c为小数部分恒为.5的实数），问y=c这条线经过了多少个大周，这些州总共有多少个城市

很明显要用到并查集，比较好的做法是把并查集落实到线段树上，并查集维护的是每个集合的最大y和最小y，以及rank表示集合数目。但是线段树要用到离散化、

然后参照一个用树状数组的博客，其实思路差不多，都是把每次的变更落实到树上

不过这个树状数组跟之前写的不一样，这个是改段查点型的，之前的是改点查段型的，其实只要改一下辅助数组的定义即可，在这个树状数组里面，把辅助数组d当做从1到当前所有的变更，每次更新时从当前往递减方向，所以，为了得到某个点值，必须把当前点以及当前之前的变更都加起来。

所以这个

add(int loc,int v)

{

while (loc>0){d[loc]+=v;loc-=lowbit(loc);}

}

query(int loc)

{

int ret=0;

while (loc<n) {ret+=d[loc];loc+=lowbit(loc);}

return ret;

}

因为给定的数是.5的实数，故意把坐标往后压一位即可，把每一个小格子往后压成一个点即可

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 int n,m;

 int f[],rank[],y1[],y2[];

 void init()

 {

     for (int i=;i<=n;i++){

         f[i]=i;

         rank[i]=;

     }

 }

 int findset(int x)

 {

     if (x!=f[x]){

         f[x]=findset(f[x]);

     }

     return f[x];

 }

 int lowbit(int x)

 {

     return x&(-x);

 }

 struct bit

 {

     int d[];

     int limit;

     void clear()

     {

         memset(d,,sizeof d);

     }

     void add(int L,int R,int v){

         while (R>=){

             d[R]+=v;

             R-=lowbit(R);

         }

         while (L>=){

             d[L]+=-v;

             L-=lowbit(L); //L这里不能算点，因为每个格子都往后压，每个点x，就代表x-1到x这个区间，所以在这里可以抵消L的格子的影响

         }

     }

     int query(int x)

     {

         int ret=;

         while (x<=limit){

             ret+=d[x];

             x+=lowbit(x);

         }

         return ret;

     }

 }city,state;

 void unit(int r1,int r2)

 {

     f[r1]=r2;

     rank[r2]+=rank[r1];

 }

 int main()

 {

     int t;

     scanf("%d",&t);

     int a,b;

     double c;

     char ch[];

     while (t--)

     {

         city.clear();

         state.clear();

         scanf("%d",&n);

         init();

         int maxn=;

         for (int i=;i<n;i++){

             scanf("%d%d",&a,&b);

             y1[i]=b;y2[i]=b;

             maxn=max(maxn,b);

         }

         city.limit=state.limit=maxn;

         scanf("%d",&m);

         for (int i=;i<=m;i++){

             scanf("%s",ch);

             if (ch[]=='r'){

                 scanf("%d%d",&a,&b);

                 int r1=findset(a);

                 int r2=findset(b);

                 if (r1==r2) continue;

                 if (rank[r1]== && rank[r2]==){

                     unit(r1,r2);

                     y1[r2]=min(y1[r2],y1[r1]);

                     y2[r2]=max(y2[r2],y2[r1]);

                     city.add(y1[r2],y2[r2],);

                     state.add(y1[r2],y2[r2],rank[r2]);

                 }

                 else

                 if (rank[r1]== || rank[r2]==){

                     if (rank[r1]==) swap(r1,r2);

                     city.add(y1[r1],y2[r1],-);

                     state.add(y1[r1],y2[r1],-rank[r1]);

                     unit(r1,r2);

                     y1[r2]=min(y1[r1],y1[r2]);

                     y2[r2]=max(y2[r1],y2[r2]);

                     city.add(y1[r2],y2[r2],);

                     state.add(y1[r2],y2[r2],rank[r2]);

                 }

                 else

                 {

                     city.add(y1[r1],y2[r1],-);

                     state.add(y1[r1],y2[r1],-rank[r1]);

                     city.add(y1[r2],y2[r2],-);

                     state.add(y1[r2],y2[r2],-rank[r2]);

                     unit(r1,r2);

                     y1[r2]=min(y1[r1],y1[r2]);

                     y2[r2]=max(y2[r1],y2[r2]);

                     city.add(y1[r2],y2[r2],);

                     state.add(y1[r2],y2[r2],rank[r2]);

                 }

             }

             else {

                 scanf("%lf",&c);

                 int tmp=c;

                 tmp++;

                 printf("%d %d\n",city.query(tmp),state.query(tmp));

             }

         }

     }

     return ;

 }

巴特西

LA_4730 Kingdom 并查集+树状数组

最新文章

热门文章