青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

gzwzm06

  C++博客 :: 首頁 :: 新隨筆 :: 聯(lián)系 :: 聚合  :: 管理 ::
  1 隨筆 :: 52 文章 :: 17 評(píng)論 :: 0 Trackbacks
  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( 00, 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( 00, 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 閱讀(317) 評(píng)論(0)  編輯 收藏 引用 所屬分類: 數(shù)據(jù)結(jié)構(gòu)
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            欧美韩日一区| 国产欧美日韩亚洲| 99精品国产一区二区青青牛奶| 亚洲黄色av一区| 欧美大香线蕉线伊人久久国产精品| 亚洲高清av| 亚洲视频 欧洲视频| 国产九九视频一区二区三区| 欧美一区在线看| 欧美国产日本| 亚洲一区二区在线视频| 国产日韩在线不卡| 麻豆免费精品视频| 一本色道久久加勒比88综合| 久久都是精品| 亚洲激情第一区| 国产精品色婷婷| 噜噜噜噜噜久久久久久91 | 国产精品视频自拍| 久久都是精品| 日韩亚洲视频| 麻豆精品在线视频| 亚洲一区二区三区四区中文 | 欧美激情无毛| 午夜综合激情| 91久久久精品| 国产一区在线播放| 欧美日韩中文字幕综合视频| 久久av在线| 一本大道久久a久久精品综合| 久久精品一二三区| 在线一区二区三区四区| 精品电影在线观看| 国产精品捆绑调教| 欧美国产日产韩国视频| 久久精彩免费视频| 在线一区二区日韩| 亚洲欧洲日产国产综合网| 久久精品国产96久久久香蕉| 亚洲少妇中出一区| 亚洲日本视频| 在线观看国产精品淫| 国产精品免费在线| 欧美日韩色婷婷| 欧美aⅴ一区二区三区视频| 欧美一区二区三区久久精品茉莉花 | 欧美激情精品久久久久久免费印度 | 亚洲欧美一区二区激情| 亚洲日本欧美| 在线欧美影院| 黄色精品免费| 国产亚洲欧美中文| 国产精品自拍小视频| 欧美视频在线观看一区| 欧美国产日韩精品| 免费久久99精品国产自在现线| 久久成人亚洲| 久久精品一区二区三区不卡牛牛 | 欧美日韩国产区| 欧美成在线观看| 欧美寡妇偷汉性猛交| 久久午夜羞羞影院免费观看| 午夜综合激情| 篠田优中文在线播放第一区| 亚洲女人天堂成人av在线| 在线一区欧美| 亚洲在线播放| 亚洲欧美日韩在线| 性欧美1819性猛交| 午夜日韩在线| 久久精品99国产精品酒店日本| 欧美一区二区三区视频免费播放| 亚洲欧美激情诱惑| 亚洲综合色激情五月| 午夜老司机精品| 久久精品人人| 久久亚洲视频| 欧美激情91| 欧美日韩在线观看一区二区| 国产精品家教| 国产三级欧美三级| 影音先锋另类| 亚洲精品视频啊美女在线直播| 日韩一区二区免费高清| 一本色道久久综合亚洲精品小说| 亚洲视频高清| 久久电影一区| 欧美成人在线影院| 日韩视频免费在线| 亚洲午夜精品17c| 久久激情综合网| 欧美成人蜜桃| 国产精品任我爽爆在线播放| 国产区欧美区日韩区| 在线免费观看欧美| 一本色道久久综合亚洲精品按摩| 亚洲欧美另类中文字幕| 久久久无码精品亚洲日韩按摩| 美女久久网站| 亚洲精品日产精品乱码不卡| 亚洲一区中文| 麻豆av一区二区三区久久| 欧美三级不卡| 狠色狠色综合久久| 在线亚洲高清视频| 久久在线91| 99re66热这里只有精品4| 欧美亚洲免费电影| 欧美激情区在线播放| 国产日韩欧美一区二区三区在线观看| 精品999成人| 亚洲影院一区| 欧美韩日一区| 午夜精品视频在线观看一区二区| 免费成人你懂的| 国产精品永久入口久久久| 91久久精品国产91久久| 欧美在线观看视频一区二区| 亚洲第一伊人| 久久黄色影院| 国产精品久久一级| 亚洲七七久久综合桃花剧情介绍| 亚洲无限乱码一二三四麻| 亚洲一区制服诱惑| 久久综合给合| 一区二区电影免费观看| 久久www成人_看片免费不卡| 欧美日本亚洲视频| 国产一区二区三区在线观看网站 | 亚洲色图综合久久| 欧美aa在线视频| 亚洲视频在线一区观看| 蜜臀久久99精品久久久久久9| 欧美日韩一区在线| 国产亚洲欧美另类中文| 亚洲一区二区不卡免费| 媚黑女一区二区| 亚洲免费在线观看| 欧美激情综合在线| 伊人成年综合电影网| 亚洲在线电影| 欧美激情国产日韩| 欧美在线观看日本一区| 欧美三级电影一区| 亚洲视频日本| 亚洲高清不卡一区| 欧美自拍偷拍| 国产精品亚洲一区二区三区在线| 亚洲电影在线| 欧美成人精品不卡视频在线观看| 亚洲天堂成人在线视频| 欧美精品三级| 亚洲人人精品| 玖玖精品视频| 久久精品国产亚洲一区二区| 国产精品区二区三区日本| 日韩午夜激情| 最新亚洲电影| 欧美日韩一区高清| 99国产精品私拍| 欧美韩国日本一区| 久久这里只精品最新地址| 亚洲国产网站| 欧美va天堂| 久久综合激情| 激情综合网址| 美女免费视频一区| 樱花yy私人影院亚洲| 中文无字幕一区二区三区| 欧美国产在线观看| 久久久久久久999精品视频| 经典三级久久| 男人天堂欧美日韩| 久久久综合香蕉尹人综合网| 黑人中文字幕一区二区三区| 麻豆精品视频在线观看视频| 久久精品国产精品亚洲综合| 国产日韩欧美成人| 久久国产乱子精品免费女| 久久精品91久久久久久再现| 国产专区综合网| 久久蜜桃av一区精品变态类天堂| 欧美一区二区三区的| 国产欧美精品在线播放| 美女精品网站| 免费观看在线综合| 99综合在线| 一本久久a久久精品亚洲| 国产欧美日韩亚洲精品| 久久精品一二三区| 久久噜噜亚洲综合| 亚洲国产专区| 亚洲一区二区成人| 国模大胆一区二区三区| 蜜臀av一级做a爰片久久| 浪潮色综合久久天堂| 亚洲综合色视频| 午夜欧美电影在线观看| 亚洲国产精品久久久久秋霞不卡| 亚洲午夜精品一区二区|