1984: 月下“毛景树”

1984: 月下“毛景树”

Time Limit: 20 Sec  Memory Limit: 64 MB

Submit: 1003  Solved: 324

[Submit][Status][Discuss]

Sample Input

4 1 2 8 1 3 7 3 4 9 Max 2 4 Cover 2 4 5 Add 1 4 10 Change 1 16 Max 2 4 Stop

Sample Output

9 16 【Data Range】 1<=N<=100,000，操作+询问数目不超过100,000。 保证在任意时刻，所有树枝上毛毛果的个数都不会超过10^9个。

Source

```  1 /**************************************************************
2     Problem: 1984
3     User: HansBug
4     Language: Pascal
5     Result: Accepted
6     Time:13800 ms
7     Memory:58596 kb
8 ****************************************************************/
9
10 {\$M 6552000,0,655360000}
11 type
12     point=^node;
13     node=record
14                g,f:longint;
15                next:point;w:int64;
16     end;
17 var
18    i,j,k,l,m,n,tot,root:longint;ch:char;
19    a:array[0..100005] of point;
20    e:array[0..1000005,0..3] of int64;
21    c:array[0..20,0..100005] of longint;
22    d:array[0..1000005] of int64;
23    f:array[0..100005] of int64;
24    top,tip,len,siz,son,g,num,anum:array[0..100005] of longint;
25 procedure swap(var x,y:longint);
26           var z:longint;
27           begin
28                z:=x;x:=y;y:=z;
29           end;
30 function max(x,y:longint):longint;
31          begin
32               if x>y then max:=x else max:=y;
33          end;
34 function min(x,y:longint):longint;
35          begin
36               if x<y then min:=x else min:=y;
37          end;
39           var p:point;
40           begin
41                new(p);p^.g:=y;p^.w:=z;p^.f:=t;
42                p^.next:=a[x];a[x]:=p;
43           end;
44 procedure dfs(y,x:longint);
45           var p:point;
46           begin
47                len[x]:=len[y]+1;
48                c[0,x]:=y;siz[x]:=1;
49                son[x]:=0;p:=a[x];
50                while p<>nil do
51                      begin
52                           if p^.g<>y then
53                              begin
54                                   dfs(x,p^.g);tip[p^.w]:=p^.g;f[p^.g]:=p^.f;
55                                   if (son[x]=0) or (siz[p^.g]>siz[son[x]]) then son[x]:=p^.g;
56                                   inc(siz[x],siz[p^.g]);
57                              end;
58                           p:=p^.next;
59                      end;
60           end;
61 procedure dfs2(y,x,z:longint);
62           var p:point;
63           begin
64                top[x]:=z;inc(tot);num[x]:=tot;anum[tot]:=x;
65                if son[x]<>0 then dfs2(x,son[x],z);p:=a[x];
66                while p<>nil do
67                      begin
68                           if (p^.g<>y) and (p^.g<>son[x]) then dfs2(x,p^.g,p^.g);
69                           p:=p^.next;
70                      end;
71           end;
72 procedure ext(z,x,y:longint);
73           begin
74                if e[z,1]<>0 then
75                   begin
76                        d[z]:=e[z,2];
77                        if x<>y then
78                           begin
79                                e[z*2,1]:=1;e[z*2,2]:=e[z,2];
80                                e[z*2+1,1]:=1;e[z*2+1,2]:=e[z,2];
81                           end;
82                        e[z,2]:=0;e[z,1]:=0;e[z,3]:=0;
83                   end
84                else if e[z,3]<>0 then
85                     begin
86                          inc(d[z],e[z,3]);
87                          if x<>y then
88                             begin
89                                  if e[z*2,1]<>0 then ext(z*2,x,(x+y) div 2);
90                                  if e[z*2+1,1]<>0 then ext(z*2+1,(x+y) div 2+1,y);
91                                  inc(e[z*2,3],e[z,3]);
92                                  inc(e[z*2+1,3],e[z,3]);
93                             end;
94                          e[z,3]:=0;e[z,2]:=0;e[z,1]:=0;
95                     end;
96           end;
97 procedure built(z,x,y:longint);
98          begin
99               if x=y then
100                  d[z]:=f[anum[x]]
101               else
102                   begin
103                        built(z*2,x,(x+y) div 2);
104                        built(z*2+1,(x+y) div 2+1,y);
105                        if d[z*2]>d[z*2+1] then d[z]:=d[z*2] else d[z]:=d[z*2+1];
106                   end;
107               e[z,1]:=0;e[z,2]:=0;e[z,3]:=0;
108          end;
110          var a1,a2:int64;
111          begin
112               if l>r then
113                  begin
114                       ext(z,x,y);
115                       exit(d[z]);
116                  end;
117               ext(z,x,y);if (x=l) and (y=r) then
118                             begin
119                                  inc(e[z,3],t);
120                                  exit(d[z]+e[z,3]);
121                             end;
122               a1:=addd(z*2,x,(x+y) div 2,l,min(r,(x+y) div 2),t);
123               a2:=addd(z*2+1,(x+y) div 2+1,y,max((x+y) div 2+1,l),r,t);
124               if a1>a2 then d[z]:=a1 else d[z]:=a2;
125               exit(d[z]);
126          end;
127 function cover(z,x,y,l,r:longint;t:int64):int64;
128          var a1,a2:int64;
129           begin
130
131                if l>r then
132                   begin
133                        ext(z,x,y);
134                        exit(d[z]);
135                   end;
136                if (x=l) and (y=r) then
137                   begin
138                        e[z,1]:=1;
139                        e[z,2]:=t;
140                        exit(t);
141                   end;
142                ext(z,x,y);
143                a1:=cover(z*2,x,(x+y) div 2,l,min(r,(x+y) div 2),t);
144                a2:=cover(z*2+1,(x+y) div 2+1,y,max((x+y) div 2+1,l),r,t);
145                if a1>a2 then d[z]:=a1 else d[z]:=a2;
146                exit(d[z]);
147           end;
148 function getmax(z,x,y,l,r:longint):int64;
149          begin
150               if l>r then exit(-maxlongint);
151               if e[z,1]<>0 then exit(e[z,2]);
152               ext(z,x,y);
153               if (x=l) and (y=r) then exit(d[z]);
154               exit(max(getmax(z*2,x,(x+y) div 2,l,min(r,(x+y) div 2)),getmax(z*2+1,(x+y) div 2+1,y,max((x+y) div 2+1,l),r)));
155          end;
156 function getup(x,y:longint):longint;
157          var i:longint;
158          begin
159               i:=0;
160               while y<>0 do
161                     begin
162                          if odd(y) then x:=c[i,x];
163                          inc(i);y:=y div 2;
164                     end;
165               exit(x);
166          end;
167 function getcom(x,y:longint):longint;
168          var i:longint;
169          begin
170               if len[x]<len[y] then swap(x,y);
171               x:=getup(x,len[x]-len[y]);
172               if x=y then exit(x);
173               for i:=trunc(round(ln(len[x])/ln(2))) downto 0 do
174                   if c[i,x]<>c[i,y] then
175                      begin
176                           x:=c[i,x];
177                           y:=c[i,y];
178                      end;
179               exit(c[0,x]);
180          end;
181 procedure treechange(x,y:longint;t:int64);
182           var i,z,z1:longint;
183           begin
184                z:=getcom(x,y);
185                if x<>z then
186                   begin
187                        z1:=getup(x,len[x]-len[z]-1);
188                        repeat
189                              if len[top[x]]<len[z1] then i:=z1 else i:=top[x];
190                              cover(1,1,n,num[i],num[x],t);
191                              if i=z1 then break;
192                              x:=c[0,i];
193                        until false;
194                   end;
195                if y<>z then
196                   begin
197                        z1:=getup(y,len[y]-len[z]-1);
198                        repeat
199                              if len[top[y]]<len[z1] then i:=z1 else i:=top[y];
200                              cover(1,1,n,num[i],num[y],t);
201                              if i=z1 then break;
202                              y:=c[0,i];
203                        until false;
204                   end;
205           end;
207           var z,i,z1:longint;
208           begin
209                z:=getcom(x,y);
210                if x<>z then
211                   begin
212                        z1:=getup(x,len[x]-len[z]-1);
213                        repeat
214                              if len[top[x]]<len[z1] then i:=z1 else i:=top[x];
216                              if i=z1 then break;
217                              x:=c[0,i];
218                        until false;
219                   end;
220                if y<>z then
221                   begin
222                        z1:=getup(y,len[y]-len[z]-1);
223                        repeat
224                              if len[top[y]]<len[z1] then i:=z1 else i:=top[y];
226                              if i=z1 then break;
227                              y:=c[0,i];
228                        until false;
229                   end;
230           end;
231 function treemax(x,y:longint):int64;
232          var i,z,z1:longint;a1:int64;
233           begin
234                z:=getcom(x,y);treemax:=0;
235                if x<>z then
236                   begin
237                        z1:=getup(x,len[x]-len[z]-1);
238                        repeat
239                              if len[top[x]]<len[z1] then i:=z1 else i:=top[x];
240                              a1:=getmax(1,1,n,num[i],num[x]);
241                              if a1>treemax then treemax:=a1;
242                              if i=z1 then break;
243                              x:=c[0,i];
244                        until false;
245                   end;
246                if y<>z then
247                   begin
248                        z1:=getup(y,len[y]-len[z]-1);
249                        repeat
250                              if len[top[y]]<len[z1] then i:=z1 else i:=top[y];
251                              a1:=getmax(1,1,n,num[i],num[y]);
252                              if a1>treemax then treemax:=a1;
253                              if i=z1 then break;
254                              y:=c[0,i];
255                        until false;
256                   end;
257           end;
258 begin
260      for i:=1 to n do a[i]:=nil;
261      for i:=1 to n-1 do
262          begin
265          end;
266      root:=random(n)+1;dfs(0,root);dfs2(0,root,root);
267      for i:=1 to trunc(round(ln(n)/ln(2))) do
268          for j:=1 to n do
269              c[i,j]:=c[i-1,c[i-1,j]];
270      built(1,1,n);
271      while not(eof) do
272            begin
274                 case upcase(ch) of
275                      'A':begin
277                               writeln(treemax(i,j));
278                      end;
279                      'O':begin
281                               treechange(i,j,k);
282                      end;
283                      'D':begin
286                      end;
287                      'H':begin
289                               treechange(c[0,tip[i]],tip[i],j);
290                      end;
291                      'T':halt;
292                 end;
293            end;
294 end.```

0 条评论

• 1303: [CQOI2009]中位数图

1303: [CQOI2009]中位数图 Time Limit: 1 Sec  Memory Limit: 162 MB Submit: 1383  Solve...

• 算法模板——线段树5（区间开根+区间求和）

实现功能——1：区间开根；2：区间求和（此模板以BZOJ3038为例） 作为一个非常规的线段树操作，其tag也比较特殊呵呵哒 1 var 2 i,j,...

• 3410: [Usaco2009 Dec]Selfish Grazing 自私的食草者

3410: [Usaco2009 Dec]Selfish Grazing 自私的食草者 Time Limit: 3 Sec  Memory Limit: 128...

• 3211: 花神游历各国

3211: 花神游历各国 Time Limit: 5 Sec  Memory Limit: 128 MB Submit: 1042  Solved: 381 ...

• 爬虫那么危险，干嘛不直接基因数据库下载文件呢？

问了具体后，才知道原来是ncbi上的信息，相当于在ncbi上在gene库中查找，然后爬取目标信息。如下：

• 队列(Queue)

看看队列在Android里面的使用 Handle消息队列 使用Handle的时候都要使用Looper.loop()

• Leetcode 165 Compare Version Numbers

Compare two version numbers version1 and version2. If version1 > version2 retu...