div.2

二维平面上有一个正方形，它的边与坐标轴平行。现在给出两个点，问是否有一个正方形的顶点是这两个点。如果有的话，输出另外两个点的坐标。

按边长关系讨论一下就好啦。

1 #include 
      
        2 #include 
       
         3  4 int X[4],Y[4]; 5  6 int main() { 7     for (int i = 0; i < 2; ++ i) { 8         scanf("%d%d",&X[i],&Y[i]); 9     }10     int dx = X[0]-X[1];11     int dy = Y[0]-Y[1];12     if (dx!=0 && dy!=0 && std::abs(dx)!=std::abs(dy)) {13         puts("-1");14         return 0;15     }16     if (dx==0) {17         X[2] = X[0] + dy;18         Y[2] = Y[0];19         X[3] = X[1] + dy;20         Y[3] = Y[1];21     } else if (dy==0) {22         X[2] = X[0];23         Y[2] = Y[0] + dx;24         X[3] = X[1];25         Y[3] = Y[1] + dx;26     } else {27         X[2] = X[0];28         Y[2] = Y[1];29         X[3] = X[1];30         Y[3] = Y[0];31     }32     printf("%d %d %d %d\n",X[2],Y[2],X[3],Y[3]);33     return 0;34 }
       
      

 

div.1

有一行n(<= 2e5)个点，执行5e5次操作。操作有三种：(1,x,y)把x点和y点连起来；(2,x,y)把(x,x+1,x+2...y-1,y)连起来；(3,x,y)询问x点和y点是否连通。

看起来就非常的并查集啊有木有。

需要两个并查集，1个维护连通性，另1个参考日常#1div1的那个并查集，维护仅在操作2下每个点的最右连通点是谁。

终于有人在比赛时间过了div.1的题，感动啊有木有。

1 #include 
      
        2  3 const int N = 200000 + 5; 4 int n,m; 5 int dsu[2][N]; 6  7 int find(int *dsu,int x) { 8     return dsu[x] == x ? x : dsu[x] = find(dsu,dsu[x]); 9 }10 11 int main() {12     scanf("%d%d",&n,&m);13     for (int i = 0; i <= n; ++ i) {14         dsu[0][i] = dsu[1][i] = i;15     }16     while (m--) {17         int op,a,b;18         scanf("%d%d%d",&op,&a,&b); a --; b --;19         if (op == 1) {20             int x = find(dsu[0],a);21             int y = find(dsu[0],b);22             dsu[0][x] = y;23         } else if (op == 2) {24             for (int i = find(dsu[1],a); i < b; dsu[1][i] = i + 1,i = find(dsu[1],i)) {25                 int x = find(dsu[0],i);26                 int y = find(dsu[0],i + 1);27                 dsu[0][x] = y;28             }29         } else {30             puts(find(dsu[0],a) == find(dsu[0],b) ? "YES" : "NO");31         }32     }33 }