Top Tree

Self-Adjusting Top Tree

Tóm tắt

Self-Adjusting Top Tree, là 2005 năm Tarjan cùng Werneck ở bọn họ luận văn Self-Adjusting Top Trees trung đưa ra một loại căn cứ vào Top Tree lý luận giữ gìn hoàn toàn động thái rừng rậm số liệu kết cấu, tên gọi tắt vì SATT.

Self-Adjusting Top Tree có thể thực hiện trong rừng rậm nhậm một thân cây liên sửa chữa / tuần tra, tử thụ sửa chữa / tuần tra cùng với phi bộ phận tìm tòi chờ thao tác.

Splay Tree là SATT cơ sở, nhưng là SATT dùng Splay Tree cùng bình thường Splay ở chi tiết chỗ không quá giống nhau ( tiến hành rồi một ít mở rộng ).

Vấn đề dẫn vào

Giữ gìn một cái rừng rậm, duy trì như sau thao tác:

Xóa bỏ, tăng thêm một cái biên, bảo đảm thao tác trước sau vẫn là một cái rừng rậm.
Sửa chữa mỗ cây thượng mỗ điều đơn giản đường nhỏ quyền giá trị.
Sửa chữa lấy nào đó điểm làm gốc tử thụ quyền giá trị.
Tuần tra mỗ cây thượng mỗ điều đơn giản đường nhỏ quyền giá trị cùng.
Tuần tra lấy nào đó điểm làm gốc tử thụ quyền giá trị cùng.

Thụ co rút lại

Đối với tùy ý một thân cây, chúng ta đều có thể vận dụngThụ co rút lạiLý luận tới đem nó co rút lại vì một cái biên.

Cụ thể mà, thụ co rút lại có hai cái cơ bản thao tác:CompressCùngRake,Compress thao tác chỉ định một cái số độ vìĐiểm,Cùng điểmLiền nhau kia hai cái điểm nhớ vì,,Chúng ta liền một cái tân biên;Đem điểm,Biên,BiênTin tức phóng tớiTrung chứa đựng, cũng xóa đi chúng nó. Như đồ sở kỳ.

Rake thao tác chỉ định một cái độ vìĐiểm,Hơn nữa cùng điểmLiền nhau điểmSố độ cần lớn hơn,Thiết điểmMột cái khác lân điểm vì,Chúng ta đem điểm,BiênTin tức để vào biênTrung chứa đựng, cũng xóa đi chúng nó. Như đồ sở kỳ.

Không khó chứng minh, bất luận cái gì một thân cây đều có thể chỉ dùng Compress thao tác cùng Rake thao tác tới đem nó co rút lại vì một cái biên, như đồ sở kỳ.

Thốc

Vì biểu đạt phương tiện, chúng ta ghi tạc tiến hành bất luận cái gì thao tác phía trước nguyên thụ vì.Ở đốiTiến hành nào đó thụ co rút lại thao tác ( có thể không làm bất luận cái gì thao tác ) lúc sau thụ nhớ vì.

Chúng ta nghiên cứu nào đóTrung mỗ một cái biên sở bao hàm tin tức tình huống.

Này biên trừ bỏ có chứa nó bản thân tin tức ( đương nhiên, nếu này biên ởTrung không tồn tại, này biên liền không có bản thân tin tức ) ở ngoài, còn khả năng bao hàm cái khác thông qua Compress/Rake thao tác xác nhập đến nó mặt trên điểm, biên tin tức. Chúng ta không ngại trước từ dưới đồ trung thụ co rút lại trong quá trình lựa chọn sử dụng một cái biên, nhìn xem nó sở bao hàm tin tức ởTrung đại biểu này đó điểm, biên.

Như đồ, lựa chọn sử dụng biên cùng đối ứng đồ đã dùng tơ hồng vòng ra.

Có thể thấy được, này biên sở bao hàm tin tức ởTrung đại biểu điểm, biên là liên thông. Chúng ta có thể mở rộng, đối với nhậm mộtTrung nhậm một cái biên chứa đựng tin tức ởTrung tổng thể hiện vì một cái liên thông tử đồ. Chúng ta đem như vậy liên thông tử đồ xưng làThốc ( Cluster ).

Nhưng mà, thốc làKhông hoàn chỉnh tử đồ,Nó bao hàm nào đó biên điểm cuối không bị thốc nó chính mình bao hàm. Vì thế chúng ta đem này đó điểm cuối gọi thốcĐiểm cuối ( Endpoint ),Đem nó bao hàm những cái đó liên thông tử đồ điểm gọiNội điểm ( Internal Node ),Liên thông tử đồ biên gọiNội biên ( Internal Edge ).

Đối với tùy ý một cái thốc, đều có dưới tính chất:

Thốc chỉ tồn trữ cùng giữ gìn nội điểm cùng nội biên tin tức.
Thốc có hai cái điểm cuối. Này hai cái điểm cuối tức vìTrung đại biểu cái kia thốc biên tương liên kia hai cái điểm. Hai cái điểm cuối chi gian đường nhỏ chúng ta xưng làThốc đường nhỏ ( Cluster Path );Nhớ một cái thốc hai cái điểm cuối phân biệt vì,,Chúng ta phía dưới dùngTới tỏ vẻ cái này thốc.
Nội điểm chỉ cùng điểm cuối hoặc nội điểm tương liên.

Đặc biệt mà, đối vớiTrung mỗi điều biên, đều từng người độc lập vì một cái thốc ( chỉ bao hàm biên chính mình tin tức ), loại này thốc chúng ta xưng làCơ thốc ( Base Cluster ).Đối với từCo rút lại đến chỉ có một cái biên cuối cùng,Cái kia biên đại biểu thốc bao hàm trừ bỏ hai cái điểm cuối ở ngoài chỉnh câyTin tức, cái này thốc chúng ta xưng làCăn thốc ( Root Cluster ).

Như đồ, câu trên nhắc tới cơ thốc đã dùng tơ hồng tiêu ra.

Từ thốc thị giác tới xem Compress/Rake thao tác, chúng ta phát hiện này hai cái thao tác sẽ đem hai cái thốc “Hợp hai làm một”, dư lại một cái tân thốc, cho nên thụ co rút lại quá trình cũng là sở hữu cơ thốc xác nhập vì một cái thốc quá trình.

Cho nên chúng ta cũng có thể được đến hạ đồ, là đối một loạt thụ co rút lại thao tác một khác tỏ vẻ.

Top Tree

Chúng ta hiện tại tưởng tỏ vẻ mỗ một thân cây tiến hành thụ co rút lại toàn quá trình.

Chúng ta có thể dùng tới văn hai loại phương pháp tới tỏ vẻ này một quá trình, nhưng như vậy thập phần phiền toái, nếu thụ co rút lại tiến hành rồiBước, chúng ta liền phải dùngCây tới tỏ vẻ toàn bộ thụ co rút lại.

Suy xét một cái đối mỗ cây tiến hành mỗ một cây co rút lại càng giản tiện tỏ vẻ, chúng ta dẫn vàoTop Tree.

Như đồ, này đây câu trên co rút lại phương pháp cùng nguyên thụ làm cơ sở một cây Top Tree.

Top Tree có dưới tính chất;

Một cây Top Tree đối ứng một cây nguyên thụ cùng một loại đối này tiến hành thụ co rút lại phương pháp, Top Tree mỗi cái tiết điểm đều tỏ vẻ ở nào đóTrung mỗ một cái biên, cũng chính là thụ co rút lại trong quá trình hình thành mỗ một cái thốc. Đồ trung hình nhưĐiểm tỏ vẻcompress(x)Này một thao tác hình thành thốc.
Top Tree trung một cái tiết điểm có hai cái nhi tử ( đều phân biệt đại biểu một cái thốc ), cái này tiết điểm đại biểu thốc là này hai cái thốc thông qua Compress hoặc Rake thao tác xác nhập được đến tân thốc.
Top Tree lá cây tiết điểm là cơ thốc, này căn tiết điểm là căn thốc. Bởi vậy chúng ta ấn một cây Top Tree Topology tự phân tầng, nó mỗi một tầng liền đại biểu một cây.

Dùng tam độ hóa Self-Adjusting Top Tree thực hiện tin tức giữ gìn

Nguyên lý

Top Tree đối thụ co rút lại quá trình cực đại đơn giản hoá, sử chúng ta nhìn đến thông qua giữ gìn thụ co rút lại quá trình tới giữ gìn trên cây tin tức khả năng tính, SATT tức là thông qua này một nguyên lý tới giữ gìn trên cây tin tức.

Chú ý tới thụ co rút lại quá trình cũng là trên cây tin tức không ngừng gia nhập quá trình, chúng ta chấp hành một lầncompress(x),Điểm tin tức từ giờ phút này khởi liền bắt đầu ở nào đó thốc trung xuất hiện, ảnh hưởng chúng ta thống kê kết quả.

Nếu chúng ta hiện tại dùng Top Tree tới giữ gìn mỗ cây,Trên cây mỗi cái điểm, biên đều có quyền giá trị, chúng ta muốn giữ gìn chính làQuyền giá trị cùng.

Hiện tại chúng ta ở giữ gìn khi phải đốiTrung nào đó điểmQuyền giá trị tiến hành sửa chữa, thực rõ ràng, chúng ta liền yêu cầu sửa đổi Top Tree trung sở hữu thốc tin tức bao hàmTiết điểm tin tức, làm như vậy đơn thứ thời gian phức tạp độ sẽ làCấp bậc.

Nhưng mà, nếu chúng ta tuyển điểm nó ở Top Tree trung thốc tin tức bao hàmTiết điểm cái số rất ít, nói cách khác sử nó tin tức tận khả năng vãn mà gia nhập thốc trung, chúng ta đơn thứ thao tác thời gian phức tạp độ sẽ có một cái rất lớn tăng lên. Như đồ.

SATT chính là thông qua sửa chữaNào đó điểm / mỗ con đường kínhỞ thụ co rút lại trong quá trình tin tức bị gia nhập thốc trung trước sau trình tự ( lấy hạ thấp này ở bị sửa chữa khi đơn thứ thời gian phức tạp độ ) tới giữ gìn trên cây tin tức.

Thực tế kết cấu

Chúng ta trước đem một cây nguyên thụPhân tầng định căn, sau đó chúng ta suy xét đối nào đó thụ co rút lại trình tự Top Tree căn thốc, nó có hai cái điểm cuối, chúng ta lệnh này trong đó một cái điểm cuối chính là nguyên thụ căn, một cái khác điểm cuối nhậm tuyển.

Như đồ, cấp căn thốc tuyển ra một tổ điểm cuối, nơi này đánh dấu thốc khi đem điểm cuối cũng cuốn vào đi.

Từ thụ co rút lại cơ bản thao tác cũng biết, thốc đường nhỏ thượng điểm, biênTin tức cuối cùng là thông qua Compress thao tác mới gia nhập,Mà phi thốc đường nhỏ điểm $(a,b,i,f,g,e,ig,\cdots)$ Là thông qua Rake thao tác mới gia nhập.

Chúng ta đem thốc đường nhỏ đơn độc lấy ra tới, đây là một cái hình thái đặc thù ( vì liên ) thụ, chúng ta vì này cây kiến ra một cây top tree ( này đại biểu thụ co rút lại trình tự tùy ý ).

Chúng ta đem này một kết cấu xưng làCompress Tree,Bởi vì tại đây cây Top Tree trung nhậm một cái điểm hai cái nhi tử chi gian là thông qua Compress thao tác tới xác nhập thành chúng nó phụ thân.

Compress Tree tiết điểm xưng làCompress Node.Chỉ suy xét trước mặt này thốc đường nhỏ, một cái phi lá cây Compress Node liền đại biểu một lần compress quá trình, tỏ vẻ đem tả nhi tử cùng hữu nhi tử tin tức xác nhập lên, lại đem cái nàycompress(x)Bản thân tồn trữ điểmTin tức gia nhập. Này cây Compress Tree liền giữ gìnThốc đường nhỏ tin tức.

Mặt khác, ở Compress Tree trung, chúng ta trên thực tế còn đối sử dụng Top Tree làm một ít hạn chế. Chú ý tới Compress Tree giữ gìn chính là một cáiĐiểm giữa chiều sâu hai hai bất đồng liên, chúng ta quy định ở Compress Tree trung cơ thốc trung tự biến lịch trình tự cùng đối ứngTrung biên chiều sâu là nhất trí, thả trung tự biến lịch càng nhỏ chiều sâu càng thiển. Đồng dạng, đối với mỗi cái điểmĐối ứngcompress(x)Quan hệ cũng là như thế.

Hiện tại tới giữ gìn những cái đó phi thốc đường nhỏ tin tức, chúng ta giả thiết này đó phi thốc đường nhỏ thượng điểm, biên đã hình thành từng cái cực đại thốc, mà này đó cực đại thốc là từ này đó dùng lam cuộn dây ra càng tiểu thốc chi gian cho nhau Rake hình thành, đối từ một ít càng tiểu thốc xác nhập hình thành một cái cực đại thốc quá trình, chúng ta dùng một cái tam xoa thụ tới tỏ vẻ, cùng loại mà, chúng ta xưng này một kết cấu vìRake Tree,Đối ứng mà Rake Tree điểm chính làRake Node.Mỗi cái Rake Node đều đại biểu một cái thốc, là từ này tả nhi tử cùng hữu nhi tử Rake đến trong đó nhi tử đại biểu càng tiểu thốc thượng hình thành. Cụ thể có thể thấy được hạ đồ, cũng biết Rake Tree trung mỗi cái điểm đều đại biểuTrung có tương đồng điểm cuối càng tiểu thốc.

Như đồ, lam cuộn dây ra chính là từng cái cực đại thốc, hoàng cuộn dây ra chính là từng cái càng tiểu thốc.

Đối với những cái đó càng tiểu thốc, chúng ta đối chúng nó tiến hành tương đồng xử lý, cho chúng nó lựa chọn thốc đường nhỏ, kiến ra Compress Tree,…… Như thế đệ quy đi xuống, liền kiến ra rất nhiều tỏ vẻ thụ co rút lại quá trình Compress Tree, Rake Tree.

Thượng đồ vì nguyên thụ Rake-Compress Tree ( bởi vì mỗi cái Rake Node đều hợp với một cây Compress Tree, cho nên biểu hiện vì một cây Rake Tree hợp với rất nhiều Compress Tree hình thái ) cùng đại biểu căn thốc đường nhỏ Compress Tree.

Suy xét đem này đó thụ lấy nào đó phương thức ghép nối ở bên nhau, sử chúng nó hình thành một cái có tự chỉnh thể. Nhớ một cái Rake Tree đại biểu nhỏ nhất thốc tập hợp công cộng điểm cuối là điểm.Chúng ta cấp này đó Rake Node trung nhi tử ( một cái Compress Tree tập hợp ) đều gia nhập phiMột chỗ khác điểm, nhưng vẫn bảo trì trong đó tự biến lịch cùng Top Tree cơ bản tính chất, như đồ.

Này một bước tương đương với là làm Rake thao tác gia nhập nào đóĐiểm giữa thao tác trực tiếp phát sinh ở Compress Tree trung, này không chỉ có sử chúng ta có thể chính xác giữ gìn Rake Node tin tức ( chỉ cần đem ba cái nhi tử tin tức xác nhập có thể ), còn sử chúng ta Compress Tree kết cấu càng hoàn chỉnh. Bước tiếp theo, chúng ta đem Compress Tree sửa vì tam xoa thụ, nếu nào đó Rake Tree công cộng điểm cuối là điểm,Chúng ta liền đem Rake Tree treo ởcompress(x)Trung nhi tử chỗ, như đồ.

Lúc này trải qua tam xoa hóacompress(x)Điểm, nó ý nghĩa liền biến thành trước đem trong đó nhi tử Rake đến thốc đường nhỏ thượng, lại thống kê tả hữu nhi tử cùng điểmTin tức.

Cuối cùng, chúng ta lại xử lý một chút căn thốc đường nhỏ kia cây Compress Tree: Cùng với nó sở hữu Compress Tree nhất trí mà, ấn trung tự biến lịch gia nhập nó hai cái điểm cuối, khiến cho nó căn chứa đựng chỉnh câyTin tức.

Vì thế chúng ta liền thực hiện dùng tam độ hóa Self-Adjusting Top Tree thực hiện một thân cây tin tức giữ gìn.

Tổng kết một chút, SATT có dưới tính chất:

SATT từ Compress Tree cùng Rake Tree tạo thành, Compress Tree là một cây đặc thù Top Tree; Rake Tree là một cái tam xoa thụ, chúng nó đều đối ứng một thân cây tiến hành thụ co rút lại quá trình.
Compress Tree điểm nhiều nhất có ba cái nhi tử. Compress Tree có thể làm cùng loại với Splay thụ xoay tròn thao tác ( chỉ cần bảo đảm trong đó tự biến lịch bất biến có thể, xoay tròn một cái điểm khi bảo trì trong đó nhi tử bất động ).
Rake Tree điểm nhất định có một cái trung nhi tử. Rake Tree có thể làm cùng loại với Splay thụ xoay tròn thao tác ( chỉ cần bảo đảm trong đó tự biến lịch bất biến có thể, xoay tròn một cái điểm khi bảo trì trong đó nhi tử bất động ).
SATT Topology tự phản ánh nguyên thụThụ co rút lại trình tự.

Chúng ta ở câu trên trung nhắc tới “Sửa chữa nào đó điểm / mỗ con đường kính ở thụ co rút lại trong quá trình tin tức bị gia nhập thốc trung trước sau trình tự” SATT hay không có thể thực hiện đâu, đáp án là khẳng định.

Ở SATT trung, có một cáiaccess(x)Thao tác, nó tác dụng là sử mỗ điểmTrở thành căn thốc phi ngọn điểm, đồng thời ở SATT trung sửcompress(x)Trở thành SATT căn.

Chúng ta có thể thông quaaccess(x)Thao tác lấy đều quán $O(\log n)$ Phức tạp độ sử SATT trung đại biểucompress(x)Điểm toàn đến chỉnh cây SATT rễ cây, căn cứ SATT cái thứ tư tính chất, chúng ta thay đổicompress(x)Thao tác trình tự, khiến cho nó nhất vãn chấp hành,Điểm tin tức cũng đã bị nhất vãn gia nhập; như vậy khi chúng ta muốn sửa chữaĐiểm tin tức khi, cũng chỉ yêu cầu đổi mớicompress(x).

Số hiệu thực hiện

Push loại hàm số

Đầu tiên suy xét thượng truyền tin tức, tứcPushup(x)Hàm số. Ở suy xét đối SATT nào đó tiết điểm giữ gìn tin tức khi, đầu tiên phân cái này điểm ở Compress Tree vẫn là ở Rake Tree tiến hành thảo luận, nguyên nhân có thể thấy được câu trên, không hề lắm lời, phía dưới lấy giữ gìn nào đó điểm tử thụ lớn nhỏ vì lệ

// ls(x) x tả nhi tử
// rs(x) x hữu nhi tử
// ms(x) x trung nhi tử
// type==0 là Compress Node
// type==1 là Rake Node
voidpushup(intx,inttype){
if(type==0)
size[x]=size[rs(x)]+size[ms(x)]+1;
else
size[x]=size[rs(x)]+size[ms(x)]+size[ls(x)];
return;
}

Tuần tra điểmTử thụ lớn nhỏ, liền đem này Access đến SATT căn, đáp án là trong đó nhi tử size;Bởi vì căn cứ câu trên, ở Access lúc sau, trong đó nhi tử mới là nó thật tử thụ.

Sau đó suy xét hạ truyền tin tức, tứcPushdown(x)Hàm số. Chúng ta nếu phải đối nguyên thụ trung nào đó tử thụ làm chỉnh thể sửa chữa, một cái thực tự nhiên ý tưởng là: Đem cái này tiết điểm trực tiếp Access đến SATT căn tiết điểm, cho nó trung nhi tử đánh thượng một cái đánh dấu là được. Cùng lý, tuần tra tử thụ liền trực tiếp Access sau tuần tra trung nhi tử.

Chúng ta nếu phải đối nguyên thụ trung mỗ con đường kính làm chỉnh thể sửa chữa, chúng ta liền expose đường nhỏ hai cái điểm cuối, trong đóexpose(x, y)Là sai sử điểmTrở thànhCăn tiết điểm, sử điểmTrở thành căn thốc một cái khác điểm cuối. Đối ứng ở SATT thượng, lúc này căn thốc Compress Tree chính làĐếnĐường nhỏ. Vì thế trực tiếp cấp căn thốc Compress Tree đánh thượng một cái đánh dấu là được. Cùng lý tuần tra liên expose sau tuần tra căn tiết điểm là được.

Vì thế chúng ta liền biết vấn đề dẫn vào vấn đề như thế nào làm.

voidpushdown(intx,inttype){
if(type==0){
// xử lý liên
chain[ls(x)]+=chain[x]chain[rs(x)]+=chain[x];
val[ls(x)]+=chain[x];
val[rs(x)]+=chain[x];
// xử lý tử thụ
subtree[ls(x)]+=subtree[x];
subtree[rs(x)]+=subtree[x];
subtree[ms(x)]+=subtree[x];
val[ls(x)]+=subtree[x];
val[rs(x)]+=subtree[x];
val[ms(x)]+=subtree[x];
subtree[x]=0;
}else{
subtree[ls(x)]+=subtree[x];
subtree[rs(x)]+=subtree[x];
subtree[ms(x)]+=subtree[x];
val[ls(x)]+=subtree[x];
val[rs(x)]+=subtree[x];
val[ms(x)]+=subtree[x];
subtree[x]=0;
}
return;
}

// hạ truyền đánh dấu
voidpushall(intx,inttype){
if(!isroot(x))pushall(father[x],type);
pushdown(x,type);
return;
}

Splay loại hàm số

Chúng ta biết SATT trung Rake Tree cùng Compress Tree đều là có thể xoay tròn, nói cách khác chúng nó có thể dùng Splay tới giữ gìn. Bởi vậy chúng ta có thể viết ra dưới số hiệu:

// là một cái tiết điểm trung nhi tử hoặc vô phụ thân
// ls một cái SATT tiết điểm tả nhi tử
// rs một cái SATT tiết điểm hữu nhi tử
// ms một cái SATT tiết điểm trung nhi tử
// type==1 ở Rake Tree trung
// type==0 ở Compress Tree trung
boolisroot(intx){returnrs(father[x])!=x&&ls(father[x])!=x;}

booldirection(intx){returnrs(father[x])==x;}

voidrotate(intx,inttype){
inty=father[x],z=father[y],d=direction(x),w=son[x][d^1];
if(z)son[z][ms(z)==y?2:direction(y)]=x;
son[x][d^1]=y;
son[y][d]=w;
if(w)father[w]=y;
father[y]=x;
father[x]=z;
pushup(y,type);
pushup(x,type);
return;
}

voidsplay(intx,inttype,intgoal=0){
pushall(x,ty);// hạ truyền đánh dấu
for(inty;y=father[x],(!isroot(x))&&y!=goal;rotate(x,ty)){
if(father[y]!=goal&&(!isroot(y))){
rotate(direction(x)^diretion(y)?x:y,type);
}
}
return;
}

Đáng chú ý chính là, hàm sốdirectionCùngisrootCùng bình thường Splay bất đồng. Bởi vì vô luận cái này điểm như thế nào chuyển, cái này điểm trung nhi tử là sẽ không thay đổi.

Access loại hàm số

access(x)Ý nghĩa là: Đem điểmXoay tròn đến toàn bộ SATT căn chỗ, sử điểmTrở thành căn thốc hai cái điểm cuối chi nhất ( một chỗ khác điểm tức vìCăn tiết điểm ), đồng thời không thể thay đổi nguyên thụ kết cấu cùng nguyên thụ căn.

Vì thực hiệnaccess(x),Chúng ta trước đem này xoay tròn đến này nơi Compress Tree rễ cây, lại đem điểmHữu nhi tử xóa, sử điểmTrở thành này nơi Compress Tree đối ứng thốc điểm cuối.

if(rs(x)){
inty=new_node();
setfather(ms(x),y,0);
setfather(rs(x),y,2);
rs(x)=0;
setfather(y,x,2);
pushup(y,1);
pushup(x,0);
}

Nếu lúc này điểmĐã tới rồi hệ rễ, tắc rời khỏi; nếu không có, tắc chấp hành dưới bước đi, lấy làm nó vượt qua nó mặt trên Rake Tree:

Đem này phụ thân tiết điểm ( nhất định là một cái Rake Node ), splay đến này Rake Tree rễ cây;
ĐemGia tiết điểm ( nhất định là một cái Compress Node ) splay đến này Compress Tree hệ rễ.
NếuGia tiết điểm có một cái hữu nhi tử, tắc đem điểm x cùng gia tiết điểm hữu nhi tử trao đổi, đổi mới tin tức, sau đó rời khỏi.
Nếu gia tiết điểm không có hữu nhi tử, tắc trước làm điểmTrở thành gia tiết điểm hữu nhi tử, lúc này điểmNguyên lai phụ tiết điểm không có trung nhi tử, căn cứ câu trên Rake Node tính chất, nó không thể tồn tại. Vì thế thuyên chuyểnDeleteHàm số, đem này xóa bỏ, sau đó rời khỏi.

1, 2 hai cái bước đi hợp xưng vìLocal Splay.3, 4 hai cái bước đi hợp xưng vìSplice.Nhưng chúng ta phương tiện khởi kiến, đem chúng nó đều viết ởSplice(x)Hàm số.

Câu trên nhắc tớiDelete(x)Hàm số là cái dạng này:

Kiểm tra sắp sửa xóa bỏ điểmCó hay không tả nhi tử, nếu có, tắc đem tả nhi tử tử thụ sau tiếp tục xoay tròn đến giờPhía dưới ( trở thành tân tả nhi tử ), sau đó đem hữu nhi tử ( nếu có ) biến thành tả nhi tử hữu nhi tử, lúc này điểmTả nhi tử liền thay thế điểm.Này tương đương với Splay xác nhập thao tác.
Nếu không có tả nhi tử, tắc trực tiếp làm này hữu nhi tử thay thế điểm.

Không khó phát hiện,Splice(x)Thay đổi nguyên thụ một ít thốc điểm cuối lựa chọn sử dụng. Một lần splice sau khi xong, chúng ta đem điểmPhụ thân tiết điểm làm như tân điểm,Tiến hành tiếp theo splice.

Cuối cùng chúng ta sẽ phát hiện, chúng ta ban đầu muốn thao tác điểmNhất định ở căn thốc Compress Tree nhất hữu đoan. Chúng ta chỉ cần cuối cùng làm một lầnGlobal Splay,Đem này toàn đến SATT hệ rễ là được.

// ls một cái SATT tiết điểm tả nhi tử
// rs một cái SATT tiết điểm hữu nhi tử
// ms một cái SATT tiết điểm trung nhi tử
// son[x][0] ls
// son[x][1] rs
// son[x][2] ms
// type==1 ở Rake Tree trung
// type==0 ở Compress Tree trung
intnew_node(){
if(top){
top--;
returnStack[top+1];
}
return++tot;
}

voidsetfather(intx,intfa,inttype){
if(x)father[x]=fa;
son[fa][type]=x;
}

voidDelete(intx){
setfather(ms(x),father[x],1);
if(ls(x)){
intp=ls(x);
pushdown(p,1);
while(rs(p))p=rs(p),pushdown(p,1);
splay(p,1,x);
setfather(rs(x),p,1);
setfather(p,father[x],2);
pushup(p,1);
pushup(father[x],0);
}else
setfather(rs(x),father[x],2);
Clear(x);
}

voidsplice(intx){
// local splay
splay(x,1);
inty=father[x];
splay(y,0);
pushdown(x,1);
// splice
if(rs(y)){
swap(father[ms(x)],father[rs(y)]);
swap(ms(x),rs(y));
}else
Delete(x);
pushup(x,1);
pushup(y,0);
}

voidaccess(intx){
splay(x,0);
if(rs(x)){
inty=new_node();
setfather(ms(x),y,0);
setfather(rs(x),y,2);
rs(x)=0;
setfather(y,x,2);
pushup(y,1);
pushup(x,0);
}
while(father[x]){
splice(father[x]);
x=father[x];
pushup(x,0);
}
splay(x,0)// global splay
}

Nếu muốn cho một cái điểm trở thành nguyên thụ căn, như vậy chúng ta liền đem điểmAccess đến SATT căn tiết điểm, cũng biết lúc này điểmĐã là cuối cùng trạng thái thốc một cái điểm cuối. Từ Compress Tree trung tự biến lịch tính chất cũng biết, đem điểmNơi Compress Tree tả hữu điên đảo ( sở hữu điểm tả hữu nhi tử trao đổi ), liền sử điểmTrở thành nguyên thụ căn. Ở cụ thể thực hiện trung, chúng ta thông qua cấp điểmĐánh thượng một cái quay cuồng đánh dấu, lúc sau hạ truyền đến tiến hành này một quá trình.

voidmakeroot(intx){
access(x);
push_rev(x);
}

Vì thếexpose(x, y)Liền miêu tả sinh động:

voidexpose(intx,inty){
makeroot(x);
access(y);
}

Link & Cut

Hiện tại chúng ta muốn đem nguyên thụ trung hai cái không liên thông điểm chi gian liền một cái biên, chúng ta trước làm trong đó một cái điểmTrở thành nguyên thụ căn, lại đem một cái khác điểmXoay tròn đến căn chỗ, cũng biết lúc này hẳn là sử điểmTrở thành điểmHữu nhi tử. Sau đó ở điểmHữu nhi tử thượng treo lên này một cái biên ( ở chỉ cần giữ gìn điểm SATT trung, này một bước nhưng tỉnh ).

voidLink(intx,inty,intz){
// z đại biểu liên tiếp x, y biên
access(x);
makeroot(y);
setfather(y,x,1);
setfather(z,y,0);
pushup(x,0);
pushup(y,0);
}

CutCùngLinkNguyên lý không sai biệt lắm

voidcut(intx,inty){
expose(x,y);
clear(rs(x));// xóa rớt xy này một cơ thốc
father[x]=ls(y)=rs(x);
pushup(y,0);
}

Hoàn chỉnh số hiệu

Luogu P3690【 khuôn mẫu 】 động thái thụ

#include&LTiostream>
#define ls(x) T[x][0]
#define rs(x) T[x][1]
#define ms(x) T[x][2]
usingnamespacestd;

constexprintMAXN=300005;

intT[MAXN][3],s[MAXN][2],tot,v[MAXN],r[MAXN],top,st[MAXN],f[MAXN];

intnnd(){
if(top){
top--;
returnst[top+1];
}
return++tot;
}

boolisr(intx){returnrs(f[x])!=x&&ls(f[x])!=x;}

booldir(intx){returnrs(f[x])==x;}

voidpsu(intx,intty){
if(ty){
s[x][1]=s[ls(x)][1]^s[rs(x)][1]^s[ms(x)][1];
return;
}
s[x][0]=s[ls(x)][0]^v[x]^s[rs(x)][0];
s[x][1]=s[ls(x)][1]^s[ms(x)][1]^s[rs(x)][1]^v[x];
}

voidpsr(intx){
if(!x)return;
r[x]^=1;
swap(ls(x),rs(x));
}

voidpsd(intx,intty){
if(ty)return;
if(r[x]){
psr(ls(x));
psr(rs(x));
r[x]=0;
}
}

voidupd(intx,intty){
if(!isr(x))upd(f[x],ty);
psd(x,ty);
}

voidstf(intx,intfa,intty){
if(x)f[x]=fa;
T[fa][ty]=x;
}

voidrtt(intx,intty){
inty=f[x],z=f[y],d=dir(x),w=T[x][d^1];
if(z)T[z][ms(z)==y?2:dir(y)]=x;
T[x][d^1]=y;
T[y][d]=w;
if(w)f[w]=y;
f[y]=x;
f[x]=z;
psu(y,ty);
psu(x,ty);
}

voidspy(intx,intty,intgl=0){
upd(x,ty);
for(inty;y=f[x],(!isr(x))&&y!=gl;rtt(x,ty)){
if(f[y]!=gl&&(!isr(y)))rtt(dir(x)^dir(y)?x:y,ty);
}
}

voidcle(intx){
ls(x)=ms(x)=rs(x)=s[x][0]=s[x][1]=r[x]=v[x]=0;
st[++top]=x;
}

voiddel(intx){
stf(ms(x),f[x],1);
if(ls(x)){
intp=ls(x);
psd(p,1);
while(rs(p))p=rs(p),psd(p,1);
spy(p,1,x);
stf(rs(x),p,1);
stf(p,f[x],2);
psu(p,1);
psu(f[x],0);
}else
stf(rs(x),f[x],2);
cle(x);
}

voidspl(intx){
spy(x,1);
inty=f[x];
spy(y,0);
psd(x,1);
if(rs(y)){
swap(f[ms(x)],f[rs(y)]);
swap(ms(x),rs(y));
psu(x,1);
}else
del(x);
psu(rs(y),0);
psu(y,0);
}

voidacs(intx){
spy(x,0);
intys=x;
if(rs(x)){
inty=nnd();
stf(ms(x),y,0);
stf(rs(x),y,2);
rs(x)=0;
stf(y,x,2);
psu(y,1);
psu(x,0);
}
while(f[x]){
spl(f[x]);
x=f[x];
}
spy(ys,0);
}

intfdr(intx){
acs(x);
psd(x,0);
while(ls(x))x=ls(x),psd(x,0);
spy(x,0);
returnx;
}

voidmkr(intx){
acs(x);
psr(x);
}

voidepo(intx,inty){
mkr(x);
acs(y);
}

voidlnk(intx,inty){
if(fdr(x)==fdr(y))return;
acs(x);
mkr(y);
stf(y,x,1);
psu(x,0);
psu(y,0);
}

voidcu(intx,inty){
epo(x,y);
if(ls(y)!=x||rs(x))return;
f[x]=ls(y)=0;
psu(y,0);
}

intmain(){
cin.tie(nullptr)->sync_with_stdio(false);
intn,m;
cin>>n>>m;
tot=n;
for(inti=1;in;i++){
cin>>v[i];
psu(i,0);
}
for(inti=1;im;i++){
intop,U,V;
cin>>op>>U>>V;
if(op==0){
epo(U,V);
couts[V][0]'\n';
}
if(op==1)lnk(U,V);
if(op==2)cu(U,V);
if(op==3){
acs(U);
v[U]=V;
psu(U,0);
}
}
return0;
}

SATT thời gian phức tạp độ chứng minh

Thiết lập tại một cây SATT ( điểm số vì) trung, này trước mặt trạng tháiThế năng hàm số vì

\varphi(x)= \sum_{i=1}^{n} r(i)

Trong đó $r(i) = \lceil \log_2 \text{siz}(i) \rceil$ . $\text{siz}(i)$ Vì lấyLàm gốc tử thụ lớn nhỏ.

Tắc SATT splay đều quán phức tạp độ hiển nhiên vẫn là $3n\log n + 1$ ,Cho dù SATT là một cái tam xoa thụ.

Bởi vậy đối với SATT, chúng ta chỉ cần chứng đến Access hàm số phức tạp độ chính xác, là có thể chứng đến SATT thời gian phức tạp độ.

Chúng ta từng bước phân tích Accese đều quán phức tạp độ.

Chúng ta trước muốn đem điểmToàn đến này nơi Compress Tree căn, tắc này một bước đều quán phức tạp độ

a \leq 3\log n +1

Tiếp theo chúng ta muốn sử điểmVô hữu nhi tử, tắc này một bước đều quán phức tạp độ

a = 1 + r'(\gamma)- 0 \leq \log n +1

Như đồ, vì xóa điểmHữu nhi tử quá trình.

Sau đó là Local Splay, Splice luân phiên tiến hành quá trình, trải qua bao nhiêu thứ Splice, điểmBị toàn đến SATT căn. Chúng ta đối trong đó một tổ Local Splay, Splice tiến hành phân tích:

Như đồ, thể hiện đối điểmLàm một lần Splice quá trình, không bao gồm cuối cùng ngược chiều kim đồng hồ điểmBộ phận.

Vì biểu đạt phương tiện, thiếtVì điểmỞ trạng tháiKhiGiá trị.

Từ đồ, dễ biết từ trạng thái 1 đến trạng thái 2 thao tác ( đem điểmPhụ thân toàn đến này Rake Tree hệ rễ Local Splay thao tác ) đều quán phức tạp độ

a \leq 3(r_2(\gamma)- r_1(\gamma))+1

Từ đồ, dễ biết từ trạng thái 2 đến trạng thái 3 thao tác ( đem điểmGia tiết điểm toàn đến này Compress Tree hệ rễ Local Splay thao tác ) đều quán phức tạp độ

a \leq 3(r_3(B)- r_2(B))+1

Trọng điểm phân tích từ trạng thái 3 đến trạng thái 4 thao tác ( Splice )

a = r_4(\gamma) -r_3(\gamma) +1

Không khó phát hiện $r_4(\gamma) \leq r_3(B)$

Cố lúc này đây thao tác đều quán phức tạp độ vì

\begin{aligned} a &\leq r_3(B)- r_3(\gamma)+1\\ &\leq 3(r_3(B)- r_3(\gamma))+1\\ \end{aligned}

Tổng hợp kể trên quá trình, một lần Splice phức tạp độ vì

a\leq 3r_3(B)+3r_3(B)+3r_2(\gamma)-3r_3(\gamma)-3r_2(B)-3r_1(\gamma)+3

Ghi nhớ một lần Splice điểm( tức trạng thái 4 trung điểm)Giá trị vì,Cũng chú ý tới $r_3(\gamma),r_1(\gamma) \ge r_1(X)$ , $r_3(B),r_2(\gamma) \leq r'(X)$ Thả,Cho nên

a\leq 9(r'(X)-r(X))+3

Trừ bỏ mặt trên cái này phức tạp độ bên ngoài, ở Splice trung khả năng còn sẽ có nguyên nhândelete(x)Sinh ra thêm vào đều quán phức tạp độ, nhớ này một bộ phận vì $a' \leq 3\log n +1$ .

Trước mặc kệBộ phận, mỗi lần SpliceTương đương tiếp theo,Thả lần đầu tiên SpliceTương đương chúng ta ngay từ đầu xoay tròn điểmĐến này Compress Tree rễ cây khi,Tắc đối với bất kểdelete(x)Một lầnaccess(x)Phức tạp độ, chúng ta có:

a \leq 9(r'(x)-r(x))+ 3k + 1

Trong đóVì Splice số lần.

Nhìn dáng vẻSẽ mang một cáiDẫn tới đều quán phức tạp độ vô pháp phân tích, nhưng chúng ta có biện pháp tới đối phó nó, chú ý tới zig-zig/zig-zag xoay tròn có thể như vậy đều quán

\begin{aligned} a &\leq 3(r'(X)-r(X)) + q\\ &\leq 3(q-1)(r'(X)-r(X)) \end{aligned}

Nếu chúng ta có thể tìm được cũng đủ nhiều zig-zig, zig-zag thao tác, chúng ta liền có thể đem nàyBình quán đến này đó thao tác đi lên, do đó tiêu rớt cái này.

Chúng ta phát hiện Globel Splay bên trong liền có nhiều như vậy zig-zig, zag-zig tới cấp chúng ta sử dụng, bởi vì Globel Splay bên trong điểm cái số nhất định lớn hơn,Mà từ điểmĐến Globel Splay hệ rễ đường nhỏ điểm số nhất định không ít với,Nói cách khác một lầnaccess(x)Trung nhất định sẽ ít nhất có $\dfrac k2$ Cái zig-zag thao tác, tính thượng Globel Splay đều quán phức tạp độ $a \leq 3\log n +1$ ,Một lầnaccess(x)Không nhớdelete(x)Đều quán phức tạp độ vì

\begin{aligned} a&\leq 9(r'(X)-r(X)) + 3k + 1 + 18(r''(X)-r'(X)) -S+1 +3 \log n +1,S \ge 3k\\ a&\leq 18(r''(X)-r(X)) +2 +3\log n+1\\ a&\leq 21(r''(X)-r(X)) +3 \end{aligned}

Hiện tại tính thượng,Liệt ra tiến hànhThứaccess(x)Thao tác tổng tư thế.

\sum_{i=1}^m a_i' + \sum_{i=1}^m a_i = \sum_{i=1}^m c_i + \varphi(x_n) -\varphi(x_0)

Chúng ta yêu cầu chính là thực tế phức tạp độ

\begin{aligned} \sum_{i=1}^m c_i &= \sum_{i=1}^m a_i +\sum_{i=1}^m a_i' - \varphi(x_n) +\varphi(x_0)\\ &\le \sum_{i=1}^m a_i' + 21m\log n +n\log n +3m \end{aligned}

Chú ý tớidelete(x)Thao tác bản chất là xóa rớt một cái Rake Node, nhưng chúng ta ởThứ thao tác trung nhiều nhất chỉ biết tăng thêmCái Rake Node, từ Rake Node định nghĩa, chúng ta mới bắt đầu khi nhiều nhất cóCái Rake Node, nói cách khác chúng ta tổng cộng chỉ biết làmThứdelete(x)Thao tác, từ $a' \leq 3\log n +1$ Cũng biết

\sum_{i=1}^m c_i \leq 3(m+n)\log n + 21m\log n +n\log n +4m +n

Cho nên chúng ta liền chứng minh rồi Access phức tạp độ, mà mặt khác hàm số hoặc là căn cứ vào Access hoặc là đơn thứ thời gian phức tạp độ vì hằng số, cho nên chúng ta liền chứng minh rồi SATT phức tạp độ.

Thuận tiện nhắc tới, nếu giống LCT giống nhau tỉnh lược Global Splay quá trình, sửa vì ở mỗi lần Splice khi trực tiếp sắp sửa Access điểm xoay tròn một chút, làm như vậy thời gian phức tạp độ cũng là đúng ( thật trắc tỉnh lược Global Splay phiên bản muốn mau rất nhiều, có thể cùng LCT ở Luogu P3690 chạy trốn chẳng phân biệt trên dưới ).

Ví dụ mẫu

Ví dụ mẫu 1

CEOI 2019 Dynamic Diameter

Cấp định một câyCái tiết điểm thụ, mỗi điều biên có biên quyền, cóThứ đổi mới, mỗi lần sửa chữa một cái biên biên quyền, cũng dò hỏi thụ đường kính. Cưỡng chế tại tuyến.

Giữ gìn động thái đường kính, kiến ra SATT sau, chúng ta chỉ cần ởPushup(x)Bên trong giữ gìn mỗi cái điểm đáp án, cuối cùng tuần tra căn tiết điểm đáp án ( tức chỉnh cây đường kính ) là được.

voidpushup(intx,intop){
if(op==0){
// là Compress Node
len[x]=len[ls(x)]+len[rs(x)];
diam[x]=maxs[ls(x)][1]+maxs[rs(x)][0];
diam[x]=
max(diam[x],max(maxs[ls(x)][1],maxs[rs(x)][0])+maxs[ms(x)][0]);
diam[x]=max(diam[x],max(max(diam[ls(x)],diam[rs(x)]),diam[ms(x)]));
maxs[x][0]=
max(maxs[ls(x)][0],len[ls(x)]+max(maxs[ms(x)][0],maxs[rs(x)][0]));
maxs[x][1]=
max(maxs[rs(x)][1],len[rs(x)]+max(maxs[ms(x)][0],maxs[ls(x)][1]));
}else{
// là Rake Node
diam[x]=maxs[ls(x)][0]+maxs[rs(x)][0];
diam[x]=
max(diam[x],maxs[ms(x)][0]+max(maxs[ls(x)][0],maxs[rs(x)][0]));
diam[x]=max(max(diam[x],diam[ms(x)]),max(diam[ls(x)],diam[rs(x)]));
maxs[x][0]=max(maxs[ms(x)][0],max(maxs[ls(x)][0],maxs[rs(x)][0]));
}
return;
}

Trong đóLà trước mặt điểm đáp án ( cái này điểm đại biểu thốc đường kính ).Tỏ vẻ trước mặt Compress Node nơi thốc đường nhỏ chiều dài, $maxs_{0/1}$ Tỏ vẻ Compress Node đến thốc nội điểm cùng điểm cuối không chọn thốc đường nhỏ nhi tử / không chọn phụ thân lớn nhất khoảng cách ( nếu là Rake Node tắc chỉ tồn trữ lựa chọn sử dụng trước mặt thốc đầu trên điểm đến thốc nội điểm cùng điểm cuối lớn nhất khoảng cách). Mỗi lần tuần tra SATT căn tiết điểm diam có thể, chính xác tính hiển nhiên.

Chú ý đốiPushrev(x)Làm một ít cải biến.

voidpushrev(intx){
if(!x)return;
r[x]^=1;
swap(ls(x),rs(x));
swap(maxs[x][0],maxs[x][1]);
}

Ví dụ mẫu 2

“CSP-S 2019” thụ trọng tâm

Cấp định một thân cây, cầu ra đơn độc xóa đi thụ mỗi điều biên sau, phân liệt ra hai cái tử thụ trọng tâm đánh số cùng chi cùng.

Nếu chúng ta năng động thái $O(\log n)$ Giữ gìn thụ trọng tâm, chúng ta liền làm ra cái này đề.

SATT duy trì động thái $O(\log n)$ Giữ gìn thụ trọng tâm, làm được này yêu cầuPhi bộ phận tìm tòi ( Non-local Search ).

Đối với một loại trên cây tính chất, nếu một cái điểm / một cái biên ở chỉnh cây trung có loại này tính chất, thả ở sở hữu bao hàm nó tử thụ trung đều bao hàm này loại tính chất, chúng ta liền xưng cái này tính chất làBộ phận ( Local ),Nếu không xưng nó làPhi bộ phận ( Non-local ).Bộ phận tin tức giống nhau có thể thông quapushup(x)Tới giữ gìn

Tỷ như, quyền giá trị nhỏ nhất giá trị là bộ phận, bởi vì một cái điểm / một cái biên nếu ở chỉnh cây trung quyền giá trị nhỏ nhất, như vậy ở sở hữu bao hàm nó tử thụ trung nó cũng là quyền giá trị nhỏ nhất, mà quyền giá trị đệ nhị tiểu hiển nhiên chính là phi bộ phận.

Chúng ta câu trên giữ gìnCũng là bộ phận tin tức.

Trở lại chính đề, trọng tâm hiển nhiên là một cái phi bộ phận tin tức, vô pháp thông qua đơn giảnpushup(x)Tới giữ gìn. Chúng ta suy xét ở SATT thượng tìm tòi:

Chúng ta tìm tòi từ SATT căn tiết điểm, tức căn thốc bắt đầu. Chú ý tới trọng tâm có thực tốt tính chất: Nếu có một cái biên một bên điểm cái số lớn hơn hoặc bằng một khác sườn điểm cái số, như vậy biên này một bên nhất định ít nhất có một cái trọng tâm ( trọng tâm khả năng có hai cái ).

NhớTỏ vẻ mỗ một cái thốc điểm cái số,Vì một cây Rake Tree sở hữu Rake Node trung nhi tửCực đại.

voidpushup(intx,intop){
if(op==0){
// là Compress Node
sum[x]=sum[ls(x)]+sum[rs(x)]+sum[ms(x)]+1;
}else{
// là Rake Node
maxs[x]=max(maxs[ls(x)],max(maxs[rs(x)],sum[ms(x)]));
sum[x]=sum[ls(x)]+sum[rs(x)]+sum[ms(x)];
}
}

Như đồ, vì tại tiến hành Non-local Search khi SATT cùng đối ứng nguyên thụ.

Chúng ta làm như sau tương đối:

Tương đối thốcGiá trị cùng thốc,ThốcCùng điểmCũng ( chúng ta tạm xưng là thốc $\alpha$ )Giá trị. NếuGiá trị lớn hơn hoặc bằng người sau, thuyết minh ít nhất có một cái trọng tâm ởTử thụ trung, chúng ta đệ quy đếnTìm tòi. ( nếu nơi này lấy chờ, điểmCũng là một cái trọng tâm, yêu cầu ký lục )
Tương đối thốcGiá trị cùng thốc,ThốcCùng điểmCũng ( chúng ta tạm xưng là thốc $\beta$ )Giá trị. NếuGiá trị lớn hơn hoặc bằng người sau, thuyết minh ít nhất có một cái trọng tâm ởTử thụ trung, chúng ta đệ quy đếnTìm tòi. ( nếu nơi này lấy chờ, điểmCũng là một cái trọng tâm, yêu cầu ký lục )
Tương đối điểmTrung nhi tử Rake tree bên trongLớn nhất càng tiểu thốcGiá trị cùng thốc,Thốc,ĐiểmVà nó càng tiểu thốc cũng ( chúng ta tạm xưng là thốc)Giá trị, nếu cái kia càng tiểu thốcGiá trị lớn hơn hoặc bằng người sau, thuyết minh ít nhất có một cái trọng tâm ở cái kia càng tiểu thốc tử thụ trung, chúng ta đệ quy đến nó tìm tòi. Nếu nơi này lấy chờ, điểmCũng là một cái trọng tâm, yêu cầu ký lục.
Nếu trở lên tương đối đều không đệ quy, tắc điểmNhất định là một cái trọng tâm, ký lục cũng rời khỏi.

Bước đầu tiên tìm tòi hiển nhiên chính xác, lúc sau hẳn là như thế nào lục soát đâu?

Nếu chúng ta đệ quy đến,Tắc hiện tạiChứa đựng tin tức cũng không hoàn chỉnh, bởi vìBên trong chỉ tồn trữ nó chính mình cái này thốc tin tức, mà chúng ta yêu cầu chính là chỉnh cây trọng tâm. Phương pháp giải quyết là, đem phía trước thốc tin tức ký lục xuống dưới, ở điểmThượng tương đối tính toán khi đem thượng một cái thốc tin tức cùng điểmChính mình tin tức xác nhập xử lý. Cụ thể thực hiện như sau:

voidnon_local_search(intx,intlv,intrv,intop){
// lv cùng rv đều là tìm tòi thượng một cái thốc tin tức
if(!x)return;
psd(x,0);
if(op==0){
if(maxs[ms(x)]>=
sum[ms(x)]-maxs[ms(x)]+sum[rs(x)]+sum[ls(x)]+lv+1+rv){
if(maxs[ms(x)]==
sum[ms(x)]-maxs[ms(x)]+sum[rs(x)]+sum[ls(x)]+lv+1+rv){
if(ans1)
ans2=x;
else
ans1=x;
}
non_local_search(
ms(x),
sum[ms(x)]-maxs[ms(x)]+sum[rs(x)]+sum[ls(x)]+1+lv+rv,0,
1);
return;
}
if(ss[rs(x)]+rv>=ss[ms(x)]+ss[ls(x)]+lv+1){
if(ss[rs(x)]+rv==ss[ms(x)]+ss[ls(x)]+lv+1){
if(ans1)
ans2=x;
else
ans1=x;
}
non_local_search(rs(x),sum[ms(x)]+1+sum[ls(x)]+lv,rv,0);
return;
}
if(sum[ls(x)]+lv>=sum[ms(x)]+sum[rs(x)]+1+rv){
if(sum[ls(x)]+lv==sum[ms(x)]+sum[rs(x)]+1+rv){
if(ans1)
ans2=x;
else
ans1=x;
}
non_local_search(ls(x),lv,rv+sum[ms(x)]+1+sum[rs(x)],0);
return;
}
}else{
if(maxs[ls(x)]==maxs[x]){
non_local_search(ls(x),lv,rv,1);
return;
}
if(maxs[rs(x)]==maxs[x]){
non_local_search(rs(x),lv,rv,1);
return;
}
non_local_search(ms(x),lv,rv,0);
return;
}
if(ans1)
ans2=x;
else
ans1=x;
}

Thí dụ mẫu số hiệu

#include&LTalgorithm>
#include&LTiostream>
#define ls(x) T[x][0]
#define rs(x) T[x][1]
#define ms(x) T[x][2]
usingnamespacestd;

constexprintMAXN=600005;

intT[MAXN][3],tot,r[MAXN],top,st[MAXN],f[MAXN],maxs[MAXN],ss[MAXN];

intnnd(){
if(top){
top--;
returnst[top+1];
}
return++tot;
}

boolisr(intx){returnrs(f[x])!=x&&ls(f[x])!=x;}

booldir(intx){returnrs(f[x])==x;}

voidpsr(intx){
if(!x)return;
r[x]^=1;
swap(ls(x),rs(x));
}

voidpsd(intx,intty){
if(ty)return;
if(r[x]){
psr(ls(x));
psr(rs(x));
r[x]=0;
}
}

voidpsu(intx,intop){
psd(x,op);/* không biết nào không psd*/
if(op==0){
ss[x]=ss[ls(x)]+ss[rs(x)]+ss[ms(x)]+1;
}else{
maxs[x]=max(maxs[ls(x)],max(maxs[rs(x)],ss[ms(x)]));
ss[x]=ss[ls(x)]+ss[rs(x)]+ss[ms(x)];
}
}

voidupd(intx,intty){
if(!isr(x))upd(f[x],ty);
psd(x,ty);
}

voidstf(intx,intfa,intty){
if(x)f[x]=fa;
T[fa][ty]=x;
}

voidrtt(intx,intty){
inty=f[x],z=f[y],d=dir(x),w=T[x][d^1];
if(z)T[z][ms(z)==y?2:dir(y)]=x;
T[x][d^1]=y;
T[y][d]=w;
if(w)f[w]=y;
f[y]=x;
f[x]=z;
psu(y,ty);
psu(x,ty);
}

voidspy(intx,intty,intgl=0){
upd(x,ty);
for(inty;y=f[x],(!isr(x))&&y!=gl;rtt(x,ty)){
if(f[y]!=gl&&(!isr(y)))rtt(dir(x)^dir(y)?x:y,ty);
}
}

voidcle(intx){
ls(x)=ms(x)=rs(x)=ss[x]=r[x]=maxs[x]=f[x]=0;
st[++top]=x;
}

voiddel(intx){
stf(ms(x),f[x],1);
if(ls(x)){
intp=ls(x);
psd(p,1);
while(rs(p))p=rs(p),psd(p,1);
spy(p,1,x);
stf(rs(x),p,1);
stf(p,f[x],2);
psu(p,1);
psu(f[x],0);
}else
stf(rs(x),f[x],2);
cle(x);
}

voidspl(intx){
spy(x,1);
inty=f[x];
spy(y,0);
psd(x,1);
if(rs(y)){
swap(f[ms(x)],f[rs(y)]);
swap(ms(x),rs(y));
}else
del(x);
psu(x,1);
psu(y,0);
rtt(rs(y),0);
}

voidacs(intx){
spy(x,0);
if(rs(x)){
inty=nnd();
stf(ms(x),y,0);
stf(rs(x),y,2);
rs(x)=0;
stf(y,x,2);
psu(y,1);
psu(x,0);
}
while(f[x])spl(f[x]);
}

voidmkr(intx){
acs(x);
psr(x);
}

voidepo(intx,inty){
mkr(x);
acs(y);
}

voidlnk(intx,inty){
acs(x);
mkr(y);
stf(y,x,1);
psu(x,0);
}

voidcu(intx,inty){
epo(x,y);
f[x]=ls(y)=0;
psu(y,0);
}

intans1,ans2;

voidnon_local_search(intx,intlv,intrv,intop){
if(!x)return;
psd(x,0);
if(op==0){
if(maxs[ms(x)]>=
ss[ms(x)]-maxs[ms(x)]+ss[rs(x)]+ss[ls(x)]+lv+1+rv){
if(maxs[ms(x)]==
ss[ms(x)]-maxs[ms(x)]+ss[rs(x)]+ss[ls(x)]+lv+1+rv){
if(ans1)
ans2=x;
else
ans1=x;
}
non_local_search(
ms(x),ss[ms(x)]-maxs[ms(x)]+ss[rs(x)]+ss[ls(x)]+1+lv+rv,
0,1);
return;
}
if(ss[rs(x)]+rv>=ss[ms(x)]+ss[ls(x)]+lv+1){
if(ss[rs(x)]+rv==ss[ms(x)]+ss[ls(x)]+lv+1){
if(ans1)
ans2=x;
else
ans1=x;
}
non_local_search(rs(x),ss[ms(x)]+1+ss[ls(x)]+lv,rv,0);
return;
}
if(ss[ls(x)]+lv>=ss[ms(x)]+ss[rs(x)]+1+rv){
if(ss[ls(x)]+lv==ss[ms(x)]+ss[rs(x)]+1+rv){
if(ans1)
ans2=x;
else
ans1=x;
}
non_local_search(ls(x),lv,rv+ss[ms(x)]+1+ss[rs(x)],0);
return;
}
}else{
if(maxs[ls(x)]==maxs[x]){
non_local_search(ls(x),lv,rv,1);
return;
}
if(maxs[rs(x)]==maxs[x]){
non_local_search(rs(x),lv,rv,1);
return;
}
non_local_search(ms(x),lv,rv,0);
return;
}
if(ans1)
ans2=x;
else
ans1=x;
return;
}

intqu[MAXN],qv[MAXN];

intmain(){
cin.tie(nullptr)->sync_with_stdio(false);
intTT;
cin>>TT;
while(TT--){
intn;
cin>>n;
tot=n;
longlongANS=0;
for(inti=1;in;i++)ss[i]=1;
for(inti=1;in;i++){
cin>>qu[i]>>qv[i];
lnk(qu[i],qv[i]);
}
for(inti=1;in;i++){
cu(qu[i],qv[i]);
ans1=0;
ans2=0;
non_local_search(qu[i],0,0,0);
ANS+=ans1+ans2;
if(ans1)acs(ans1);
if(ans2)acs(ans2);
ans1=0;
ans2=0;
non_local_search(qv[i],0,0,0);
ANS+=ans1+ans2;
if(ans1)acs(ans1);
if(ans2)acs(ans2);
lnk(qu[i],qv[i]);
}
coutANS'\n';
for(inti=1;itot;i++)
T[i][0]=T[i][1]=T[i][2]=ss[i]=r[i]=maxs[i]=f[i]=0;
tot=top=0;
}
return0;
}

Reference

Robert E. Tarjan and Renato F. Werneck. 2005. Self-adjusting top trees. In Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms (SODA '05). Society for Industrial and Applied Mathematics, USA, 813–822. DOI 10.5555/1070432.1070547
negiizhao blog

Bổn giao diện gần nhất đổi mới:2024/10/9 22:38:42,Đổi mới lịch sử
Phát hiện sai lầm? Tưởng cùng nhau hoàn thiện?Ở GitHub thượng biên tập này trang!
Bổn giao diện cống hiến giả:F7487,AtomAlpaca,Enter-tainer,FFjet,HeRaNO,hsfzLZH1,Ir1d,liuzimingc,Tiphereth-A,Xeonacid
Bổn giao diện toàn bộ nội dung ởCC BY-SA 4.0CùngSATAHiệp nghị chi điều khoản hạ cung cấp, phụ gia điều khoản cũng khả năng ứng dụng