題目來源：?CodeForces 基準時間限制：1?秒 空間限制：131072?KB 分值:?80?難度：5級算法題

有n個人在公司里面工作。員工從1到n編號。每一個人屬于一個部門。剛開始每一個人在自己的部門負責自己的項目，這樣的話公司里面就有n個部門。

然而，公司內部出現了危機，需要合并一些部門，以提高工作效率。team(person)?表示person這個人所在的部門。有以下兩種合并操作：

1.????合并?team(x)?和?team(y)。?x和?y?(1≤x,y≤n)是員工編號。如果team(x)?和?team(y)是同一個部門，那么就不操作。

2.????合并team(x),team(x+1),...,team(y)，x?和?y?(1≤x≤y≤n)是員工編號。

有一些查詢操作，查詢員工x?和?y?(1≤x,y≤n)是否屬于同一部門。

Input 單組測試數據。 第一行有兩個整數n?和?q?(1≤n≤200000,?1≤q≤500000)表示員工的數目和操作數目。 接下來q行，每行的格式是type?x?y。type∈{1，2，3}。如果type=1?或者?type=2，那么表示第一種或者第二種合并操作。如果type=3，表示查詢員工x和y是否屬于同一部門。 Output 對于第三種查詢，如果屬于同一部門輸出YES，否則輸出NO。 Input示例 樣例輸入1 8?6 3?2?5 1?2?5 3?2?5 2?4?7 2?1?2 3?1?7 Output示例 樣例輸出1 NO YES YES 并查集? pre數組記錄的是前面第一個與他是不是同個部門的點。 因為記錄的是前面一個 所以2操作要倒過來合并 找題的時候突然看到這題沒做完， 然后發現 原來離A掉這個題 只差一個讀入優化 屠龍寶刀點擊就送 #include <cstdio> #include <cctype> #define N 205000 int n,q,fa[N],pre[N]; int find_(int x) {return x==fa[x]?x:fa[x]=find_(fa[x]);} template<typename T> inline void read(T &x) {register char ch=getchar();for(x=0;!isdigit(ch);ch=getchar());for(;isdigit(ch);x=x*10+ch-'0',ch=getchar()); } int main() {read(n);read(q);for(int i=1;i<=n;++i) fa[i]=i,pre[i]=i-1;for(int opt,x,y;q--;){read(opt);read(x);read(y);if(opt==1) fa[find_(y)]=find_(x);else if(opt==2){int end,i=y;for(;i>=x&&(end=pre[i])>=x;i=end){fa[find_(end)]=fa[find_(i)];pre[i]=pre[end];}}else{if(find_(x)==find_(y)) puts("YES");else puts("NO");}}return 0; }

?

轉載于:https://www.cnblogs.com/ruojisun/p/7648036.html

總結

以上是生活随笔為你收集整理的51nod 1525 重组公司的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。