題目描述

在森林中見過會動的樹，在沙漠中見過會動的仙人掌過后，魔法少女LJJ已經覺得自己見過世界上的所有稀奇古怪的事情了
LJJ感嘆道“這里真是個迷人的綠色世界,空氣清新、淡雅,到處散發著醉人的奶漿味；小猴在枝頭悠來蕩去,好不自在；各式各樣的鮮花爭相開放,各種樹枝的枝頭掛滿沉甸甸的野果；鳥兒的歌聲婉轉動聽,小河里飄著落下的花瓣真是人間仙境”
SHY覺得LJJ還是太naive，一天，SHY帶著自己心愛的圖找到LJJ，對LJJ說：“既然你已經見識過動態樹，動態仙人掌了，那么今天就來見識一下動態圖吧”
LJJ：“要支持什么操作？”
SHY：“
1.新建一個節點，權值為x。
2.連接兩個節點。
3.將一個節點a所屬于的聯通快內權值小于x的所有節點權值變成x。
4.將一個節點a所屬于的聯通快內權值大于x的所有節點權值變成x。
5.詢問一個節點a所屬于的聯通塊內的第k小的權值是多少。
6.詢問一個節點a所屬聯通快內所有節點權值之積與另一個節點b所屬聯通快內所有節點權值之積的大小。
7.詢問a所在聯通快內節點的數量
8.若兩個節點a，b直接相連，將這條邊斷開。
9.若節點a存在，將這個點刪去。
”
LJJ：“我可以離線嗎？”
SHY：“可以，每次操作是不加密的，”
LJJ：“我可以暴力嗎？”
SHY：“自重”
LJJ很郁悶，你能幫幫他嗎

（事實上，仔細讀題可以發現，出題人在數據范圍中約定了$c\le 7$，因此第8、9種操作是不存在的！這里也將樣例作了修改）

輸入

第一行有一個正整數m，表示操作個數。
接下來m行，每行先給出1個正整數c。
若c=1，之后一個正整數x，表示新建一個權值為x的節點，并且節點編號為n+1（當前有n個節點）。
若c=2，之后兩個正整數a，b，表示在a，b之間連接一條邊。
若c=3，之后兩個正整數a，x，表示a聯通快內原本權值小于x的節點全部變成x。
若c=4，之后兩個正整數a，x，表示a聯通快內原本權值大于x的節點全部變成x。
若c=5，之后兩個正整數a，k，表示詢問a所屬于的聯通塊內的第k小的權值是多少。
若c=6，之后兩個正整數a，b，表示詢問a所屬聯通快內所有節點權值之積與b所屬聯通快內所有節點權值之積的大小，
若a所屬聯通快內所有節點權值之積大于b所屬聯通快內所有節點權值之積，輸出1，否則為0。
若c=7，之后一個正整數a，表示詢問a所在聯通塊大小
若c=8，之后兩個正整數a，b，表示斷開a，b所連接的邊。
若c=9，之后一個正整數a，表示斷開a點的所有連邊
具體輸出格式見樣例

輸出

對于每個詢問，輸出答案

樣例輸入

11
1 2
1 3
1 4
1 5
1 6
2 1 2
2 2 3
2 3 4
2 4 5
3 2 5
5 3 4

樣例輸出

5

---

題解

并查集+權值線段樹合并（本題是道語文題= =）

對于操作1、2、3、4、5、7，稍有做題經驗的人很容易想到使用并查集維護連通塊，對每個連通塊開一棵權值線段樹。

連邊操作直接權值線段樹合并，各種查詢直接裸上線段樹的區間查詢。

對于3、4操作，可以先統計出有多少個數小于/大于x，然后刪除所有小于/大于x的數，并在x位置加上這些數。

而對于6操作出現了乘積不是很好處理，我們把它取對數，因為$\log(nm)=\log n+\log m$，所以轉化為每個數的對數的和，直接維護區間權值和即可。本題中使用double不會被卡精度。

時間復雜度$O(m\log n)$。

然而比$O(m\log n+n\log^2n)$的平衡樹啟發式合并還慢什么鬼。。

#include <cmath> #include <cstdio> #include <algorithm> #define N 400010 #define lson l , mid , ls[x] #define rson mid + 1 , r , rs[x] using namespace std; const int m = 1000000000; int ls[N * 19] , rs[N * 19] , si[N * 19] , tot , root[N] , f[N] , n; double sum[N * 19]; bool tag[N * 19]; void pushdown(int x) {if(tag[x]){si[ls[x]] = si[rs[x]] = 0 , sum[ls[x]] = sum[rs[x]] = 0;tag[ls[x]] = tag[rs[x]] = 1 , tag[x] = 0;} } int find(int x) {return x == f[x] ? x : f[x] = find(f[x]); } void add(int p , int a , double v , int l , int r , int &x) {if(!x) x = ++tot;si[x] += a , sum[x] += a * v;if(l == r) return;pushdown(x);int mid = (l + r) >> 1;if(p <= mid) add(p , a , v , lson);else add(p , a , v , rson); } void del(int b , int e , int l , int r , int x) {if(!x) return;if(b <= l && r <= e){si[x] = 0 , sum[x] = 0 , tag[x] = 1;return;}pushdown(x);int mid = (l + r) >> 1;if(b <= mid) del(b , e , lson);if(e > mid) del(b , e , rson);si[x] = si[ls[x]] + si[rs[x]] , sum[x] = sum[ls[x]] + sum[rs[x]]; } int querysi(int b , int e , int l , int r , int x) {if(!x) return 0;if(b <= l && r <= e) return si[x];pushdown(x);int mid = (l + r) >> 1 , ans = 0;if(b <= mid) ans += querysi(b , e , lson);if(e > mid) ans += querysi(b , e , rson);return ans; } int find(int k , int l , int r , int x) {if(l == r) return l;pushdown(x);int mid = (l + r) >> 1;if(k <= si[ls[x]]) return find(k , lson);else return find(k - si[ls[x]] , rson); } int merge(int x , int y) {if(!x) return y;if(!y) return x;si[x] += si[y] , sum[x] += sum[y];pushdown(x) , pushdown(y);ls[x] = merge(ls[x] , ls[y]) , rs[x] = merge(rs[x] , rs[y]);return x; } int main() {int q , c , x , y , t;scanf("%d" , &q);while(q -- ){scanf("%d%d" , &c , &x);switch(c){case 1: add(x , 1 , log(x) , 1 , m , root[++n]) , f[n] = n; break;case 2:{scanf("%d" , &y) , x = find(x) , y = find(y);if(x != y) f[y] = x , root[x] = merge(root[x] , root[y]);break;}case 3:{x = find(x) , scanf("%d" , &y) , t = querysi(1 , y , 1 , m , root[x]);del(1 , y , 1 , m , root[x]) , add(y , t , log(y) , 1 , m , root[x]);break;}case 4:{x = find(x) , scanf("%d" , &y) , t = querysi(y , m , 1 , m , root[x]);del(y , m , 1 , m , root[x]) , add(y , t , log(y) , 1 , m , root[x]);break;}case 5: x = find(x) , scanf("%d" , &y) , printf("%d\n" , find(y , 1 , m , root[x])); break; case 6: x = find(x) , scanf("%d" , &y) , y = find(y) , printf("%d\n" , sum[root[x]] > sum[root[y]]); break;default: x = find(x) , printf("%d\n" , si[root[x]]);}}return 0; }

?

?

轉載于:https://www.cnblogs.com/GXZlegend/p/7423642.html

總結

以上是生活随笔為你收集整理的【bzoj4399】魔法少女LJJ 并查集+权值线段树合并的全部內容，希望文章能夠幫你解決所遇到的問題。

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