P5350 序列 可持久化fhq

2022-09-22 21:31:37 字數 2115 閱讀 9509

戳這裡

我們發現 \(1,2,3,6\) 這些操作就是 \(fhq\) 的基操,模板題做過就會

所以我們只需要考慮 \(4,5\) 操作

對於 \(5\) 操作就直接裂成 \(5\) 段,然後交換第 \(2\) 和 \(4\) 段,再合上就好了

對於 \(4\) 操作,我們發現因為 \(fhq\) 不支援插入一段區間,只能一個元素一個元素並上去,那麼複雜度就會變成 \(o(qn)\) ,所以我們需要記一下歷史版本,然後直接複製歷史版本的元素資訊到對應的位置上,這樣就相當於加上了一段區間

然後你就會得到 \(mle\) 的好成績,做了 可持久化\(fhq\)/可持久化文藝平衡樹 就會發現,這道題的空間小的離譜,只有 \(128m\) 也就是說我們不可能把所有的歷史版本都存下來,那麼只能在空間達到一定程度後重構 \(fhq\) 把所有 \(4\) 操作帶來的影響加上去,來維持空間複雜度,具體來說就是遍歷整個 \(fhq\) 把所有標記都清除後重建一個 \(fhq\)

tip:

對於可持久化 \(fhq\) ,需要在任何改變平衡樹形態和元素資訊的地方記錄一下歷史版本,比如 \(pushdown,merge,split\) 的時候

這應該是我寫過的最長的資料結構題,足足 \(7k\) **

#includeusing namespace std;

namespace zzc

while (isdigit(ch))

return x*f; }

const int maxn = 3e6+5;

const int mod = 1e9+7;

int n,m,num;

int tmp[maxn];

namespace fhq_treap

t[maxn];

inline int new_node(int x=0)

inline int copy(int x)

inline void pushup(int x)

inline void push_tag(int x,int k)

inline void push_add(int x,int k)

inline void push_rev(int x)

inline void pushdown(int x)

if(t[x].add)

if(t[x].rev)

}int merge(int x,int y)

split(rt,r2,d,e);

split(d,l2-1,c,d);

split(c,r1,b,c);

split(b,l1-1,a,b);

if(flag) b=copy(d);

else d=copy(b);

rt=merge(a,merge(b,merge(c,merge(d,e))));

}inline void _swap(int l1,int r1,int l2,int r2)

split(rt,r2,d,e);

split(d,l2-1,c,d);

split(c,r1,b,c);

split(b,l1-1,a,b);

rt=merge(a,merge(d,merge(c,merge(b,e))));

}inline void reverse(int l,int r)

void dfs(int const &x)

int build(int l,int r)

inline void rebuild()

void watch()

puts("");

} }

using namespace fhq_treap;

void work()

case 2:

case 3:

case 4:

case 5:

case 6:

}if(cnt>2000000) rebuild();

//printf("%d : ",i);watch();

}num=0;dfs(rt);

for(int i=1;i<=n;i++) printf("%d ",tmp[i]); }}

int main()

Luogu P5350 序列

這道題目太毒瘤啦,經過了無數遍的tle wa,和re tat ,我終於瞭解了珂朵莉樹的強 r 大 e 我會詳細的介紹關於tle,wa和re的原因。 首先我們看到區間賦值操作和保證資料隨機,我們的第一直覺肯定是珂朵莉樹啦,雖然在刻意構造的資料下她的時間複雜度是錯誤的,但是在隨機資料下她的表現十分優秀,...

LG P5350 序列

操作 1 2 3 就是原題。。不講了。。 把odt的set中的那一段點存入一個vector 然後把兩邊的左右端點換一下 在插入就好了。。 只不過在操作時要時刻注意odt的先右後左原則。。 開 o 2 才能過。。喔太菜了。。 includeusing namespace std const int m...

Luogu P3919 可持久化陣列

陣列是一種單點修改,單點查詢的基礎資料結構。 如果要對陣列改進,使之可持久化,那麼顯然我們需要利用其它的資料結構來改進它。 對於單點修改和單點查詢兩種操作,很容易發現可持久化線段樹也是支援這種操作的。 所以,我們利用可持久化線段樹來維護一個可持久化陣列 include define mid l r ...