gzwzm06
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  1 随笔 :: 52 文章 :: 17 评论 :: 0 Trackbacks
7th GDCPC Problem H(DFS序 + 线段树)
  1#include <cstdio>
  2
  3const int SIZE = 100001;
  4const int INF = 10000000;
  5
  6int N, arr_sc[SIZE], arr_order[SIZE], arr_index[SIZE], edge[SIZE][2], father[SIZE];
  7
  8struct NODE
  9{
 10    int m_v;
 11    struct NODE* next;
 12}tree[SIZE], mem[SIZE * 2];
 13
 14int index = 0, M = 0, tId = 1;
 15int gMax, gMin;
 16
 17struct ITEM
 18{
 19    int fst;
 20    int last;
 21}arr_pos[SIZE];
 22
 23struct STREE
 24{
 25    int m_start;
 26    int m_end;
 27
 28    int m_max;
 29    int m_min;
 30    int m_markMin;
 31    int m_markMax;
 32
 33    int m_leftChild;
 34    int m_rightChild;
 35}stree[SIZE * 2];
 36
 37void Insert(const int& x, const int& y)
 38{
 39    mem[index].m_v = y;
 40    mem[index].next = tree[x].next;
 41    tree[x].next = &mem[index];
 42    index++;
 43
 44    mem[index].m_v = x;
 45    mem[index].next = tree[y].next;
 46    tree[y].next = &mem[index];
 47    index++;
 48}
 49
 50void DFS( const int &root, const int& fat )
 51{
 52    NODE *ptr = tree[root].next;
 53    
 54    arr_pos[root].fst = M;
 55    arr_index[root] = M;
 56    arr_order[M++] = root;
 57    father[root] = fat;
 58
 59    while ( ptr )
 60    {
 61        if ( ptr->m_v != fat )
 62        {
 63            DFS( ptr->m_v, root );
 64        }
 65        ptr = ptr->next;
 66    }
 67
 68    arr_pos[root].last = M - 1;
 69}
 70
 71void Build(const int& id, const int& s, const int& e)
 72{
 73    stree[id].m_start = s;
 74    stree[id].m_end = e;
 75    stree[id].m_max = 0;
 76    stree[id].m_min = INF;
 77    stree[id].m_markMax = -1;
 78    stree[id].m_markMin = -1;
 79    if ( s == e )
 80    {
 81        return;
 82    }
 83
 84    int mid = (s + e) >> 1;
 85
 86    stree[id].m_leftChild = tId++;
 87    Build( stree[id].m_leftChild, s, mid );
 88
 89    stree[id].m_rightChild = tId++;
 90    Build( stree[id].m_rightChild, mid + 1, e );
 91}
 92
 93void InsertTree(const int& id, const int& p, const int& v)
 94{
 95    if ( stree[id].m_max < v )
 96    {
 97        stree[id].m_max = v;
 98        stree[id].m_markMax = arr_order[p];
 99    }
100    if ( stree[id].m_min > v )
101    {
102        stree[id].m_min = v;
103        stree[id].m_markMin = arr_order[p];
104    }
105
106    if ( stree[id].m_start == p && stree[id].m_end == p )
107    {
108        return;
109    }
110
111    int mid = (stree[id].m_start + stree[id].m_end) >> 1;
112
113    if ( mid >= p )
114        InsertTree( stree[id].m_leftChild, p, v );
115    else
116        InsertTree( stree[id].m_rightChild, p, v );
117}
118
119void Change( const int& id, const int& p, const int& v )
120{
121    if ( stree[id].m_markMax == arr_order[p] )
122    {
123        stree[id].m_max = 0;
124        stree[id].m_markMax = -1;
125    }
126    if ( stree[id].m_markMin == arr_order[p] )
127    {
128        stree[id].m_min = INF;
129        stree[id].m_markMin = -1;
130    }
131
132    if ( stree[id].m_leftChild == p && stree[id].m_rightChild == p )
133    {
134        stree[id].m_max = stree[id].m_min = v;
135        stree[id].m_markMax = stree[id].m_markMin = arr_order[p];
136        return;
137    }
138
139    int mid = (stree[id].m_start + stree[id].m_end) >> 1;
140
141    if ( mid >= p )
142    {
143        Change( stree[id].m_leftChild, p, v );
144    }
145    else {
146        Change( stree[id].m_rightChild, p, v );
147    }
148
149    int tf = stree[id].m_leftChild, tr = stree[id].m_rightChild, tmark, ts;
150    
151    ts = (stree[tf].m_max > stree[tr].m_max ? stree[tf].m_max : stree[tr].m_max);
152    tmark = (stree[tf].m_max > stree[tr].m_max ? stree[tf].m_markMax : stree[tr].m_markMax );
153    if ( stree[id].m_max < ts )
154    {
155        stree[id].m_max = ts;
156        stree[id].m_markMax = tmark;
157    }
158
159    ts = (stree[tf].m_min < stree[tr].m_min ? stree[tf].m_min : stree[tr].m_min);
160    tmark = (stree[tf].m_min < stree[tr].m_min ? stree[tf].m_markMin : stree[tr].m_markMin );
161    if ( stree[id].m_min > ts )
162    {
163        stree[id].m_min = ts;
164        stree[id].m_markMin = tmark;
165    }
166
167}
168
169void Query(const int& id, const int& s, const int& e)
170{
171    if ( s == stree[id].m_start && e == stree[id].m_end )
172    {
173        if ( gMax < stree[id].m_max )
174            gMax = stree[id].m_max;
175        if ( gMin > stree[id].m_min )
176            gMin = stree[id].m_min;
177
178        return;
179    }
180
181    int mid = (stree[id].m_start + stree[id].m_end) >> 1;
182
183    if ( mid >= e )
184    {
185        Query( stree[id].m_leftChild, s, e );
186    }
187    else if ( mid < s )
188    {
189        Query( stree[id].m_rightChild, s, e );
190    }
191    else {
192        Query( stree[id].m_leftChild, s, mid );
193        Query( stree[id].m_rightChild, mid + 1, e );
194    }
195}
196
197void Solve(const int& ep)
198{
199    gMax = 0;
200    gMin = INF;
201
202    __int64 ans;
203    int x, y, s, e;
204
205    x = edge[ep][0], y = edge[ep][1];
206
207    if ( y == father[x] )
208        y = x;
209
210    s = arr_pos[y].fst;
211    e = arr_pos[y].last;
212
213    if ( s == e )
214    {
215        gMax = gMin = arr_sc[y];
216    }
217    else {
218        Query( 0, s, e );
219    }
220
221    ans = gMax * gMin;
222
223    gMax = 0;
224    gMin = INF;
225
226    if ( s > 0 )
227        Query( 0, 0, s - 1 );
228
229    if ( e + 1 <= M - 1 )
230        Query( 0, e + 1, M - 1 );
231
232    ans += gMax * gMin;
233
234    printf("%I64d\n", ans);
235
236}
237
238void Init()
239{
240    int i;
241
242    for ( i = 0; i < SIZE; ++i )
243        tree[i].next = NULL;
244
245    index = 0;
246    tId = 1;
247    M = 0;
248}
249
250int main()
251 {
252     freopen("1.txt", "r", stdin);
253
254     int cs;
255     int i, x, y, Q;
256     char cmd[10];
257
258     scanf("%d", &cs);
259
260     while ( cs-- )
261     {
262         scanf("%d %d", &N, &Q);
263
264         for ( i = 1; i <= N; ++i )
265         {
266             scanf("%d", &arr_sc[i]);
267         }
268
269         Init();
270         Build( 0, 0, N - 1 );
271
272         for ( i = 0; i < N - 1; ++i )
273         {
274             scanf("%d %d", &x, &y);
275
276             edge[i + 1][0] = x;
277             edge[i + 1][1] = y;
278             Insert( x, y );
279         }
280
281         father[1] = -1;
282         DFS( 1, -1 );
283
284         for ( i = 0; i < M; ++i )
285         {
286             int t = arr_order[i];
287             InsertTree( 0, i, arr_sc[t] );
288         }
289
290         for ( i = 0; i < Q; ++i )
291         {
292             scanf("%s", cmd);
293
294             if ( cmd[0] == 'Q' )
295             {
296                 scanf("%d", &x);
297            
298                 Solve( x );
299             }
300             else if ( cmd[0] == 'C' )
301             {
302                 scanf("%d %d", &x, &y);
303                 arr_sc[x] = y;
304                 Change( 0, arr_index[x], y ); 
305             }
306         }
307     }
308     
309     return 0;
310 }
311
posted on 2009-05-20 00:13 巫 阅读(291) 评论(0)  编辑 收藏 引用 所属分类: 数据结构

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理