POJ 3580 - SuperMemo 解題心得( 題目 )
解題概念:treap
解題方法:這題得使用特殊資料結構，像是segment tree不支持插入，而linkedlist先不考慮查詢，刪除速度也夠慢，所以這題必須使用treap，讓所有操作為O(logN)才行，我們使用無旋式treap。
INSERT:把treap切開，插入一個新的點再和回去
DELETE:把treap切開，切成3份，中間那份為移除的那個，把左右和回去
MIN:把treap切成三份，中間那份為查詢區間，進行MIN更新後取頂端。
ADD:把treap切成三份，在中間那份頂端打加值懶標
REVERSE:把treap切成三份，在中間那份頂端打反轉懶標
REVOLVE:把treap切成四份(觀察規律)，把二、三部分交換。
Java參考程式碼(更好意見可留言於下方，謝謝!):
//Author:En Chi Tsung(欉恩祁)
//Date:2022/03/02
import java.io.*;
import java.util.*;
public class Main {
public static int tem;
public static Treap a;
public static Treap[] x,y,z;
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws Exception{
String[] in=br.readLine().split(" ");
final int n=Integer.parseInt(in[0]);
a=null;
for(int i=0;i<n;i++) {
in=br.readLine().split(" ");
a=Merge(a,new Treap(Long.parseLong(in[0])));
}
in=br.readLine().split(" ");
final int m=Integer.parseInt(in[0]);
int l,r,t;
long v;
for(int i=0;i<m;i++) {
in=br.readLine().split(" ");
if(in[0].equals("ADD")) {
l=Integer.parseInt(in[1]);
r=Integer.parseInt(in[2]);
v=Long.parseLong(in[3]);
Add(l,r,v);
}
if(in[0].equals("REVERSE")) {
l=Integer.parseInt(in[1]);
r=Integer.parseInt(in[2]);
Reverse(l,r);
}
if(in[0].equals("REVOLVE")) {
l=Integer.parseInt(in[1]);
r=Integer.parseInt(in[2]);
v=Long.parseLong(in[3]);
Revolve(l,r,v);
}
if(in[0].equals("INSERT")) {
l=Integer.parseInt(in[1]);
v=Long.parseLong(in[2]);
Insert(l,v);
}
if(in[0].equals("DELETE")) {
t=Integer.parseInt(in[1]);
Delete(t);
}
if(in[0].equals("MIN")) {
l=Integer.parseInt(in[1]);
r=Integer.parseInt(in[2]);
Query(l,r);
}
}
bw.flush();
}
public static void Add(int l,int r,long v){
x=Split(a,r);
y=Split(x[0],l-1);
y[1].val+=v;
y[1].min+=v;
y[1].lt+=v;
a=Merge(Merge(y[0],y[1]),x[1]);
}
public static void Reverse(int l,int r){
x=Split(a,r);
y=Split(x[0],l-1);
if(y[1]!=null)y[1].rev^=1;
a=Merge(Merge(y[0],y[1]),x[1]);
}
public static void Revolve(int l,int r,long t) {
x=Split(a,r);
y=Split(x[0],l-1);
if(t<0) {
t+=((-t*(r-l+1)/(r-l+1))+1);
}
z=Split(y[1],(int)(r-l+1-t%(r-l+1)));
a=Merge(Merge(y[0],Merge(z[1],z[0])),x[1]);
}
public static void Insert(int l,long v) throws Exception{
x=Split(a,l);
a=Merge(Merge(x[0],new Treap(v)),x[1]);
}
public static void Delete(int l) throws Exception{
x=Split(a,l);
y=Split(x[0],l-1);
a=Merge(y[0],x[1]);
}
public static void Query(int l,int r) throws Exception{
x=Split(a,r);
y=Split(x[0],l-1);
bw.write(y[1].min+"\n");
a=Merge(Merge(y[0],y[1]),x[1]);
}
public static Treap Merge(Treap a,Treap b) {
if(a==null)return b;
if(b==null)return a;
a.Move();
b.Move();
if(a.pri<b.pri) {
a.tr[1]=Merge(a.tr[1],b);
if(a!=null)a.Reset();
return a;
}
else {
b.tr[0]=Merge(a,b.tr[0]);
if(b!=null)b.Reset();
return b;
}
}
public static Treap[] Split(Treap a,int L) {
if(a==null)return new Treap[] {null,null};
a.Move();
if(L<=((a.tr[0]==null)?0:a.tr[0].size)) {
Treap[] left=Split(a.tr[0],L);
a.tr[0]=left[1];
if(a!=null)a.Reset();
return new Treap[] {left[0],a};
}
else {
Treap[] right=Split(a.tr[1],L-((a.tr[0]==null)?0:a.tr[0].size)-1);
a.tr[1]=right[0];
if(a!=null)a.Reset();
return new Treap[] {a,right[1]};
}
}
}
class Treap{
long val,lt=0,min=(1<<30);
int pri,size=1,rev=0;
Treap[] tr=new Treap[2];
Treap(long v){
val=min=v;
pri=(int)(Math.random()*1000000000);
}
void Reset() {
if(this==null)return;
size=1;
min=val;
if(tr[0]!=null) {
min=Math.min(min,tr[0].min);
size+=tr[0].size;
}
if(tr[1]!=null) {
min=Math.min(min,tr[1].min);
size+=tr[1].size;
}
}
void Move() {
if(this==null)return;
if(lt!=0) {
if(tr[0]!=null) {
tr[0].lt+=lt;
tr[0].min+=lt;
tr[0].val+=lt;
}
if(tr[1]!=null) {
tr[1].lt+=lt;
tr[1].min+=lt;
tr[1].val+=lt;
}
lt=0;
}
if(rev!=0) {
rev=0;
if(tr[0]!=null) {
tr[0].rev^=1;
}
if(tr[1]!=null) {
tr[1].rev^=1;
}
Treap temp=tr[0];
tr[0]=tr[1];
tr[1]=temp;
}
}
}
文章標籤
全站熱搜
留言列表
