树套树是我写到至今最DT的数据库结构了吧。。。
【BZOJ3196】【Tyvj 1730】二逼平衡树
线段树套TREAP，nlog3n
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 | program p3196; type tree=record l,r,w,f,size:longint; end; var t:array[0..4000000] of tree; x,root:array[0..500000] of longint; i,j,n,m,len,ans,l,r,mid,k1,k2,k3,k4,k5,k6:longint; ch:char; function min(k1,k2:longint):longint; begin if k1<k2 then exit(k1) else exit(k2); end; function max(k1,k2:longint):longint; begin if k1<k2 then exit(k2) else exit(k1); end; procedure zig(pf,f,k:longint); begin if t[pf].l=f then t[pf].l:=k else if t[pf].r=f then t[pf].r:=k; t[f].l:=t[k].r; t[k].r:=f; t[f].size:=t[t[f].l].size+t[t[f].r].size+1; t[k].size:=t[t[k].l].size+t[t[k].r].size+1; end; procedure zag(pf,f,k:longint); begin if t[pf].l=f then t[pf].l:=k else if t[pf].r=f then t[pf].r:=k; t[f].r:=t[k].l; t[k].l:=f; t[f].size:=t[t[f].l].size+t[t[f].r].size+1; t[k].size:=t[t[k].l].size+t[t[k].r].size+1; end; procedure insert(f,k1,k2:longint); begin inc(t[k1].size); if t[k1].w>t[k2].w then begin if t[k1].l=0 then t[k1].l:=k2 else insert(k1,t[k1].l,k2); if t[k1].f<t[k2].f then zig(f,k1,k2); end else begin if t[k1].r=0 then t[k1].r:=k2 else insert(k1,t[k1].r,k2); if t[k1].f<t[k2].f then zag(f,k1,k2); end; end; procedure buildtree(k1,k2,k3:longint); var now,i,j:longint; begin root[k1]:=len+1; now:=len-k2+1; len:=len+k3-k2+1; for i:=k2 to k3 do begin t[i+now].w:=x[i]; t[i+now].size:=1; t[i+now].f:=random(1000000); if i<>k2 then begin insert(0,root[k1],i+now); if (t[i+now].l=root[k1]) or (t[i+now].r=root[k1]) then root[k1]:=i+now; end; end; if k2<>k3 then begin buildtree(k1*2,k2,(k2+k3) shr 1); buildtree(k1*2+1,(k2+k3) shr 1+1,k3); end; end; function findallnum(k1,k2:longint):longint; begin if k1=0 then exit(0); if k2<t[k1].w then exit(findallnum(t[k1].l,k2)); exit(findallnum(t[k1].r,k2)+1+t[t[k1].l].size); end; function pd(k1,k2,k3,k4,k5,k6:longint):longint; var k:longint; begin if (k2>k5) or (k3<k4) then exit(0); if (k2>=k4) and (k3<=k5) then exit(findallnum(root[k1],k6)); exit(pd(k1*2,k2,(k2+k3) shr 1,k4,k5,k6)+pd(k1*2+1,(k2+k3) shr 1+1,k3,k4,k5,k6)); end; function findwhere(k,k1,k2,f:longint):longint; var k3,k4:longint; begin if t[k1].w=k2 then begin while true do begin if t[k1].l=0 then begin if f=0 then root[k]:=t[k1].r else begin if k1=t[f].l then t[f].l:=t[k1].r else t[f].r:=t[k1].r; end; t[k1].r:=0; exit(k1); end else if t[k1].r=0 then begin if f=0 then root[k]:=t[k1].l else begin if k1=t[f].l then t[f].l:=t[k1].l else t[f].r:=t[k1].l; end; t[k1].l:=0; exit(k1); end else begin k3:=f; if t[t[k1].l].f>t[t[k1].r].f then begin f:=t[k1].l; zig(k3,k1,t[k1].l); end else begin f:=t[k1].r; zag(k3,k1,t[k1].r); end; if k3=0 then root[k]:=f; dec(t[f].size); end; end; end; dec(t[k1].size); if t[k1].w>k2 then exit(findwhere(k,t[k1].l,k2,k1)) else exit(findwhere(k,t[k1].r,k2,k1)); end; procedure change(k1,k2,k3,k4,k6,k5:longint); var k:longint; begin if (k2>k4) or (k3<k4) then exit; if (k2=k3) then begin t[root[k1]].w:=k5; exit; end; k:=findwhere(k1,root[k1],k6,0); t[k].size:=1; t[k].w:=k5; insert(0,root[k1],k); if (t[k].l=root[k1]) or (t[k].r=root[k1]) then root[k1]:=k; change(k1*2,k2,(k2+k3) shr 1,k4,k6,k5); change(k1*2+1,(k2+k3) shr 1+1,k3,k4,k6,k5); end; function findnum(k1,k2,k3,k4,k5,k6:longint):longint; begin if (k2>k5) or (k3<k4) then exit(0); if (k2>=k4) and (k3<=k5) then exit(findallnum(root[k1],k6)); exit(findnum(k1*2,k2,(k2+k3) shr 1,k4,k5,k6)+findnum(k1*2+1,(k2+k3) shr 1+1,k3,k4,k5,k6)); end; function findlesss(k1,k2:longint):longint; begin if k1=0 then exit(-maxlongint); if k2<=t[k1].w then exit(findlesss(t[k1].l,k2)); exit(max(findlesss(t[k1].r,k2),t[k1].w)); end; function findmore(k1,k2:longint):longint; begin if k1=0 then exit(maxlongint); if k2>=t[k1].w then exit(findmore(t[k1].r,k2)); exit(min(findmore(t[k1].l,k2),t[k1].w)); end; function findmax(k1,k2,k3,k4,k5,k6:longint):longint; begin if (k2>k5) or (k3<k4) then exit(-maxlongint); if (k2>=k4) and (k3<=k5) then {begin writeln(k2,' ',k3,' ',k4,' ',k5,' ',k6,' ',findlesss(root[k1],k6));} exit(findlesss(root[k1],k6)); {end;} exit(max(findmax(k1*2,k2,(k2+k3) shr 1,k4,k5,k6),findmax(k1*2+1,(k2+k3) shr 1+1,k3,k4,k5,k6))); end; function findmin(k1,k2,k3,k4,k5,k6:longint):longint; begin if (k2>k5) or (k3<k4) then exit(maxlongint); if (k2>=k4) and (k3<=k5) then exit(findmore(root[k1],k6)); exit(min(findmin(k1*2,k2,(k2+k3) shr 1,k4,k5,k6),findmin(k1*2+1,(k2+k3) shr 1+1,k3,k4,k5,k6))); end; begin readln(n,m); for i:=1 to n do read(x[i]); readln; len:=0; buildtree(1,1,n); for i:=1 to m do begin read(k6); if k6=2 then begin readln(k1,k2,k3); l:=0; r:=1000000001; while l<r do begin mid:=(l+r) shr 1; k4:=pd(1,1,n,k1,k2,mid); if k4>=k3 then begin ans:=mid; r:=mid; end else l:=mid+1; end; writeln(ans); end else if k6=3 then begin readln(k1,k2); change(1,1,n,k1,x[k1],k2); x[k1]:=k2; end else if k6=1 then begin readln(k1,k2,k3); writeln(findnum(1,1,n,k1,k2,k3-1)+1); end else if k6=4 then begin readln(k1,k2,k3); writeln(findmax(1,1,n,k1,k2,k3)); end else if k6=5 then begin readln(k1,k2,k3); writeln(findmin(1,1,n,k1,k2,k3)); end; end; end. |
【BZOJ2141】排队
用树套树来维护逆序对个数。挺巧妙的。nlog2n
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 | program p2141; type tree=record father,l,r,w,size:longint; end; var t:array[0..2000000] of tree; w,root,x,y:array[0..3000000] of longint; i,j,n,m,len,k1,k2:longint; tot:int64; procedure zig(k:longint); var f:longint; begin f:=t[k].father; t[k].father:=t[f].father; if f=t[t[f].father].l then t[t[f].father].l:=k else if f=t[t[f].father].r then t[t[f].father].r:=k; t[f].l:=t[k].r; t[t[f].l].father:=f; t[k].r:=f; t[f].father:=k; t[f].size:=t[t[f].l].size+t[t[f].r].size+1; t[k].size:=t[t[k].l].size+t[t[k].r].size+1; end; procedure zag(k:longint); var f:longint; begin f:=t[k].father; t[k].father:=t[f].father; if f=t[t[f].father].l then t[t[f].father].l:=k else if f=t[t[f].father].r then t[t[f].father].r:=k; t[f].r:=t[k].l; t[t[f].r].father:=f; t[k].l:=f; t[f].father:=k; t[f].size:=t[t[f].l].size+t[t[f].r].size+1; t[k].size:=t[t[k].l].size+t[t[k].r].size+1; end; procedure up(k,k1:longint); var f1,f2:longint; begin while (k<>k1) do begin f1:=t[k].father; f2:=t[f1].father; if f1=k1 then begin if k=t[f1].l then zig(k) else zag(k); exit; end; if k=t[f1].l then begin if f1=t[f2].l then begin zig(f1); zig(k); end else begin zig(k); zag(k); end; end else if f1=t[f2].l then begin zag(k); zig(k); end else begin zag(f1); zag(k); end; if f2=k1 then exit; end; end; procedure insert(k1,k2:longint); begin inc(t[k1].size); if t[k2].w>t[k1].w then begin if t[k1].r=0 then begin t[k1].r:=k2; t[k2].father:=k1; end else insert(t[k1].r,k2); end else begin if t[k1].l=0 then begin t[k1].l:=k2; t[k2].father:=k1; end else insert(t[k1].l,k2); end; end; procedure buildtree(k1,k2,k3:longint); var now,i,j:longint; begin inc(len); root[k1]:=len; now:=len-k2; len:=len+k3-k2; for i:=k2 to k3 do begin t[now+i].w:=w[i]; t[now+i].size:=1; if i<>k2 then begin insert(root[k1],now+i); {if k1=1 then begin writeln(root[k1]); for j:=1 to n do writeln(t[j].l,' ',t[j].r,' ',t[j].size,' ',t[j].father,' ',t[j].w); readln; end;} up(now+i,root[k1]); root[k1]:=now+i; end; end; if k2<>k3 then begin buildtree(k1*2,k2,(k2+k3) shr 1); buildtree(k1*2+1,(k2+k3) shr 1+1,k3); end; end; procedure sort(first,en:longint); var i,j:longint; begin i:=first; j:=en; x[0]:=x[i]; while i<j do begin while (i<j) and ((w[x[j]]>w[x[0]]) or ((w[x[j]]=w[x[0]]) and (x[j]>=x[0]))) do dec(j); if i<j then x[i]:=x[j]; while (i<j) and ((w[x[i]]<w[x[0]]) or ((w[x[i]]=w[x[0]]) and (x[i]<x[0]))) do inc(i); if i<j then x[j]:=x[i]; end; x[i]:=x[0]; if i>first+1 then sort(first,i-1); if i<en-1 then sort(i+1,en); end; function lowbit(k:longint):longint; begin exit(k and (-k)); end; procedure addin(k:longint); var i:longint; begin i:=k; while i<=n do begin x[i]:=x[i]+1; i:=i+lowbit(i); end; end; function addup(k:longint):longint; var i,j:longint; begin j:=0; i:=k; while i>0 do begin j:=j+x[i]; i:=i-lowbit(i); end; exit(j); end; procedure swap(var k1,k2:longint); var i:longint; begin i:=k1; k1:=k2; k2:=i; end; function findallless(k1,k2:longint):longint; begin if k1=0 then exit(0); if t[k1].w>k2 then exit(findallless(t[k1].l,k2)); exit(findallless(t[k1].r,k2)+t[t[k1].l].size+1); end; function findallmore(k1,k2:longint):longint; begin if k1=0 then exit(0); if t[k1].w<k2 then exit(findallmore(t[k1].r,k2)); exit(findallmore(t[k1].l,k2)+t[t[k1].r].size+1); end; function findless(k1,k2,k3,k4,k5,k6:longint):longint; begin if (k2>k5) or (k3<k4) then exit(0); if (k2>=k4) and (k3<=k5) then exit(findallless(root[k1],k6)); exit(findless(k1*2,k2,(k2+k3) shr 1,k4,k5,k6)+findless(k1*2+1,(k2+k3) shr 1+1,k3,k4,k5,k6)); end; function findmore(k1,k2,k3,k4,k5,k6:longint):longint; begin if (k2>k5) or (k3<k4) then exit(0); if (k2>=k4) and (k3<=k5) then exit(findallmore(root[k1],k6)); exit(findmore(k1*2,k2,(k2+k3) shr 1,k4,k5,k6)+findmore(k1*2+1,(k2+k3) shr 1+1,k3,k4,k5,k6)); end; function findwhere(k1,k2:longint):longint; begin if t[k1].w=k2 then exit(k1); if t[k1].w<k2 then exit(findwhere(t[k1].r,k2)); exit(findwhere(t[k1].l,k2)); end; function findleft(k:longint):longint; begin while t[k].l<>0 do k:=t[k].l; exit(k); end; function findright(k:longint):longint; begin while t[k].r<>0 do k:=t[k].r; exit(k); end; procedure change(k1,k2,k3,k4,k5:longint); var k,i,j,k6,k7:longint; begin if (k2>k4) or (k3<k4) then exit; if (k2=k3) then begin t[root[k1]].w:=k5; exit; end; k:=findwhere(root[k1],w[k4]); up(k,root[k1]); root[k1]:=k; if t[k].l=0 then begin t[k].size:=1; t[t[k].r].father:=0; root[k1]:=t[k].r; t[k].r:=0; end else if t[k].r=0 then begin t[k].size:=1; t[t[k].l].father:=0; root[k1]:=t[k].l; t[k].l:=0; end else begin k6:=findright(t[k].l); k7:=findleft(t[k].r); up(k6,k); up(k7,t[k6].r); root[k1]:=k6; t[k7].l:=0; dec(t[k7].size); dec(t[k6].size); t[k].father:=0; end; t[k].w:=k5; insert(root[k1],k); change(k1*2,k2,(k2+k3) shr 1,k4,k5); change(k1*2+1,(k2+k3) shr 1+1,k3,k4,k5); end; begin {assign(input,'data.in'); reset(input); assign(output,'dat1a.out'); rewrite(output);} readln(n); for i:=1 to n do read(w[i]); len:=0; fillchar(t,sizeof(t),0); fillchar(root,sizeof(root),0); buildtree(1,1,n); for i:=1 to n do x[i]:=i; sort(1,n); for i:=1 to n do y[x[i]]:=i; fillchar(x,sizeof(x),0); for i:=n downto 1 do begin tot:=tot+addup(y[i]-1); addin(y[i]); end; writeln(tot); readln(m); {while true do begin read(i); writeln(findmore(1,1,n,1,n,i)); writeln(findless(1,1,n,1,n,i)); end;} for i:=1 to m do begin {writeln(root[1]);}{ for j:=1 to n do writeln(t[j].l,' ',t[j].r,' ',t[j].size,' ',t[j].father,' ',t[j].w);} readln(k1,k2); if w[k1]=w[k2] then begin writeln(tot); continue; end; if k1>k2 then swap(k1,k2); { writeln(findmore(1,1,n,1,n,w[k1]+1),' ',findless(1,1,n,1,n,w[k1]-1),' ',findless(1,1,n,1,n,w[k2]-1),' ',findmore(1,1,n,1,n,w[k2]+1)); } if k1+1<>k2 then tot:=tot+findmore(1,1,n,k1+1,k2-1,w[k1]+1)-findless(1,1,n,k1+1,k2-1,w[k1]-1)+findless(1,1,n,k1+1,k2-1,w[k2]-1)-findmore(1,1,n,k1+1,k2-1,w[k2]+1); if w[k1]<w[k2] then inc(tot) else dec(tot); change(1,1,n,k1,w[k2]); {for j:=1 to n do writeln(t[j].l,' ',t[j].r,' ',t[j].size,' ',t[j].father,' ',t[j].w);} change(1,1,n,k2,w[k1]); swap(w[k1],w[k2]); writeln(tot); end; end. |
【BZOJ2120】数颜色
用颜色种类个数的SPLAY来维护同种颜色的下一只画笔的位置。用树套树来求解。nlog2n。据说树状数组套主席树也可以做，但我太弱了不会。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 | program p2120; type tree=record l,r,father,w,size:longint; end; var root,first:array[0..800000] of longint; ro:array[0..2000000] of longint; t:array[0..4000000] of tree; w,x:array[0..20000] of longint; i,j,n,m,k1,k2,len:longint; ch:char; procedure zig(k:longint); var f:longint; begin f:=t[k].father; t[k].father:=t[f].father; if f=t[t[f].father].l then t[t[f].father].l:=k else if f=t[t[f].father].r then t[t[f].father].r:=k; t[f].father:=k; t[f].l:=t[k].r; t[t[f].l].father:=f; t[k].r:=f; t[f].size:=t[t[f].l].size+t[t[f].r].size+1; t[k].size:=t[t[k].l].size+t[t[k].r].size+1; end; procedure zag(k:longint); var f:longint; begin f:=t[k].father; t[k].father:=t[f].father; if f=t[t[f].father].l then t[t[f].father].l:=k else if f=t[t[f].father].r then t[t[f].father].r:=k; t[f].father:=k; t[f].r:=t[k].l; t[t[f].r].father:=f; t[k].l:=f; t[f].size:=t[t[f].l].size+t[t[f].r].size+1; t[k].size:=t[t[k].l].size+t[t[k].r].size+1; end; procedure up(k1,k2:longint); var f1,f2:longint; begin while (k1<>k2) and (t[k1].father<>k2) do begin f1:=t[k1].father; f2:=t[f1].father; if f2=k2 then begin if k1=t[f1].l then zig(k1) else zag(k1); exit; end; if k1=t[f1].l then begin if f1=t[f2].l then begin zig(f1); zig(k1); end else begin zig(k1); zag(k1); end; end else if f1=t[f2].l then begin zag(k1); zig(k1); end else begin zag(f1); zag(k1); end; end; end; procedure insert(k1,k2:longint); begin if k1=0 then exit; inc(t[k1].size); if t[k1].w<t[k2].w then begin if t[k1].r=0 then begin t[k1].r:=k2; t[k2].father:=k1; end else insert(t[k1].r,k2); end else if t[k1].l=0 then begin t[k1].l:=k2; t[k2].father:=k1; end else insert(t[k1].l,k2); end; function min(k1,k2:longint):longint; begin if k1<k2 then exit(k1) else exit(k2); end; function findless(k1,k2:longint):longint; begin if k1=0 then exit(maxlongint); if t[k1].w<=k2 then exit(findless(t[k1].r,k2)); exit(min(findless(t[k1].l,k2),t[k1].w)); end; procedure buildtree(k1,k2,k3:longint); var i,j,now:longint; begin now:=len-k2; root[k1]:=len; len:=len+k3-k2+1; first[k1]:=now; for i:=k2 to k3 do begin t[now+i].w:=x[i]; t[now+i].size:=1; if i<>k2 then begin insert(root[k1],now+i); up(now+i,0); root[k1]:=now+i; end; end; if k2<>k3 then begin buildtree(k1*2,k2,(k2+k3) shr 1); buildtree(k1*2+1,(k2+k3) shr 1+1,k3); end; end; procedure getchar(var ch:char); begin repeat read(ch); until(ch>='A') and (ch<='Z'); end; function findbig(k1,k2:longint):longint; begin if k1=0 then exit(0); if t[k1].w>k2 then exit(findbig(t[k1].l,k2)+1+t[t[k1].r].size); exit(findbig(t[k1].r,k2)); end; function findanswer(k1,k2,k3,k4,k5:longint):longint; begin if (k2>k5) or (k3<k4) then exit(0); if (k2>=k4) and (k3<=k5) then exit(findbig(root[k1],k5)); exit(findanswer(k1*2,k2,(k2+k3) shr 1,k4,k5)+findanswer(k1*2+1,(k2+k3) shr 1+1,k3,k4,k5)); end; function findmorewhere(k1,k2:longint):longint; var k:longint; begin if k1=0 then exit(0); if t[k1].w>=t[k2].w then exit(findmorewhere(t[k1].l,k2)); k:=findmorewhere(t[k1].r,k2); if k=0 then exit(k1) else exit(k); end; function findleft(k:longint):longint; begin while t[k].l<>0 do k:=t[k].l; exit(k); end; function findright(k:longint):longint; begin while t[k].r<>0 do k:=t[k].r; exit(k); end; procedure delete(k1,k2:longint); var l,r:longint; begin up(k2,0); root[k1]:=k2; if t[k2].l=0 then begin t[t[k2].r].father:=0; t[k2].size:=1; root[k1]:=t[k2].r; t[k2].r:=0; end else if t[k2].r=0 then begin t[t[k2].l].father:=0; t[k2].size:=1; root[k1]:=t[k2].l; t[k2].l:=0; end else begin l:=findright(t[k2].l); r:=findleft(t[k2].r); up(l,0); up(r,l); root[k1]:=l; dec(t[l].size); dec(t[r].size); t[r].l:=0; t[k2].father:=0; end; end; procedure changetreew(k1,k2,k3:longint); var k:longint; begin k:=first[k1]+k2; delete(k1,k); t[k].w:=k3; insert(root[k1],k); up(k,0); root[k1]:=k; end; procedure changew(k1,k2,k3,k4,k5:longint); begin if (k2>k4) or (k3<k4) then exit; changetreew(k1,k4,k5); if k2=k3 then exit; changew(k1*2,k2,(k2+k3) shr 1,k4,k5); changew(k1*2+1,(k2+k3) shr 1+1,k3,k4,k5); end; procedure changex(k,color:longint); var l,r:longint; begin up(k,0); ro[w[k]]:=k; if t[k].l=0 then begin t[t[k].r].father:=0; t[k].size:=1; ro[w[k]]:=t[k].r; t[k].r:=0; end else if t[k].r=0 then begin t[t[k].l].father:=0; t[k].size:=1; ro[w[k]]:=t[k].l; l:=findright(t[k].l); x[l]:=n+1; changew(1,1,n,l,n+1); t[k].l:=0; end else begin l:=findright(t[k].l); r:=findleft(t[k].r); up(l,0); up(r,l); ro[w[k]]:=l; dec(t[l].size); dec(t[r].size); t[r].l:=0; t[k].father:=0; x[l]:=r; changew(1,1,n,l,r); end; insert(ro[color],k); up(k,0); ro[color]:=k; if t[k].l<>0 then begin l:=findright(t[k].l); changew(1,1,n,k,x[l]); changew(1,1,n,l,k); x[k]:=x[l]; x[l]:=k; end else if t[k].r<>0 then begin r:=findleft(t[k].r); changew(1,1,n,k,r); x[k]:=r; end else begin x[k]:=n+1; changew(1,1,n,k,n+1); end; end; begin readln(n,m); fillchar(root,sizeof(root),0); fillchar(ro,sizeof(ro),0); fillchar(t,sizeof(t),0); for i:=1 to n do begin read(w[i]); t[i].w:=i; t[i].size:=1; insert(ro[w[i]],i); up(i,0); ro[w[i]]:=i; end; for i:=1 to n do begin up(i,0); if t[i].r=0 then x[i]:=n+1 else x[i]:=findleft(t[i].r); end; len:=n+1; buildtree(1,1,n); for i:=1 to m do begin {for j:=1 to n do writeln(x[j],' ',w[j]); for j:=1 to 6 do writeln(ro[j]); for j:=1 to n do writeln(j,' ',t[j].l,' ',t[j].r,' ',t[j].size,' ',t[j].w,' ',ro[w[j]]); writeln; for j:=1 to n*2 do writeln(first[j],' ',root[j]); for j:=1+n to n*2 do writeln(j,' ',t[j].l,' ',t[j].r,' ',t[j].size,' ',t[j].w); }getchar(ch); if ch='Q' then begin readln(k1,k2); writeln(findanswer(1,1,n,k1,k2)); end else begin readln(k1,k2); if w[k1]=k2 then continue; changex(k1,k2); w[k1]:=k2; end; end; end. |
2019年2月17日 20:53
The definition of the programmer is taught for the students. All the issues of the program and best dissertation writing are inducted for the security of the norms and flaws of the people.