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

gzwzm06

  C++博客 :: 首頁 :: 新隨筆 :: 聯系 :: 聚合  :: 管理 ::
  1 隨筆 :: 52 文章 :: 17 評論 :: 0 Trackbacks

第一次寫接近5KB的代碼,故發帖留念.
- generate M:如果集合原來沒有M,則添加M;否則,不操作
- remove M:如果集合存在M,則刪除M;否則,不操作
- query:查出集合各元素之間最小間隔
其中,M (1, 100000)

  1#include <cstdio>
  2#include <cstring>
  3#include <queue>
  4using namespace std;
  5
  6const int SIZE = 100200;
  7
  8//線段樹
  9struct STREE
 10{
 11    int m_left, m_right; //區間的左右端值
 12    int m_start, m_end;
 13    int m_lChild, m_rChild;
 14}
stree[SIZE * 2];
 15
 16int gMin, gMax, arr[SIZE][2], arr_dif[SIZE], N;
 17bool mark[SIZE];
 18
 19//保存間隔
 20bool cmp(const int& a, const int& b)
 21{
 22    return ( a > b );
 23}

 24priority_queue<int, vector<int>, greater<int> > PQ;
 25
 26void Build(int& index, const int& s, const int& e)
 27{
 28    stree[index].m_start = s;
 29    stree[index].m_end = e;
 30    stree[index].m_left = stree[index].m_right = -1;
 31    if ( s == e )
 32    {
 33        return;
 34    }

 35
 36    int mid = (s + e) >> 1;
 37    int t = index;
 38
 39    index++;
 40    stree[t].m_lChild = index;
 41    Build( index, s, mid );
 42    index++;
 43    stree[t].m_rChild = index;
 44    Build( index, mid + 1, e );
 45
 46}

 47void Insert(const int& index, const int& num)
 48{
 49    if ( gMin < stree[index].m_left && stree[index].m_left < num )
 50        gMin = stree[index].m_left;
 51    if ( (gMax > stree[index].m_right || gMax == -1&& stree[index].m_right > num )
 52        gMax = stree[index].m_right;
 53
 54    if ( stree[index].m_start == stree[index].m_end )
 55    {
 56        stree[index].m_left = stree[index].m_right = num;
 57        return;
 58    }

 59
 60    int mid = (stree[index].m_start + stree[index].m_end) >> 1;
 61    int t;
 62
 63    if ( num <= mid )
 64    {
 65        t = stree[index].m_rChild;
 66        if ( gMax > stree[t].m_left && stree[t].m_left != -1 )
 67            gMax = stree[t].m_left;
 68
 69        Insert( stree[index].m_lChild, num );
 70    }

 71    else {
 72        t = stree[index].m_lChild;
 73        if ( gMin < stree[t].m_right && stree[t].m_right != -1 )
 74            gMin = stree[t].m_right;
 75        Insert( stree[index].m_rChild, num );
 76    }

 77
 78    if ( stree[index].m_left > num || stree[index].m_left == -1 )
 79        stree[index].m_left = num;
 80    if ( stree[index].m_right < num )
 81        stree[index].m_right = num;
 82}

 83
 84void Delete(const int& index, const int& num)
 85{
 86    if ( stree[index].m_left == num )
 87    {
 88        if ( arr[num][0>= stree[index].m_start )
 89            stree[index].m_left = arr[num][0];
 90        else if ( arr[num][1<= stree[index].m_end )
 91            stree[index].m_left = arr[num][1];
 92        else
 93            stree[index].m_left = -1;
 94    }

 95    if ( stree[index].m_right == num )
 96    {
 97        if ( arr[num][1<= stree[index].m_end )
 98            stree[index].m_right = arr[num][1];
 99        else if ( arr[num][0>= stree[index].m_start )
100            stree[index].m_right = arr[num][0];
101        else
102            stree[index].m_right = -1;
103    }

104    
105    if ( stree[index].m_start == stree[index].m_end )
106    {
107        stree[index].m_left = stree[index].m_right = -1;
108        return;
109    }

110
111    int mid = (stree[index].m_start + stree[index].m_end) >> 1;
112
113    if ( num <= mid )
114    {
115        Delete( stree[index].m_lChild, num );
116    }

117    else {
118        Delete( stree[index].m_rChild, num );
119    }

120}

121
122void Init()
123{
124    memset(arr, 0xffsizeof(arr));
125    memset(mark, 0sizeof(mark));
126    memset(arr_dif, 0sizeof(arr_dif));
127
128    for (int i = 0; i < SIZE * 2++i )
129        stree[i].m_left = stree[i].m_right = -1;
130
131    N = 0;
132
133    while ( !PQ.empty() )
134        PQ.pop();
135}

136
137void Remove(const int& num)
138{
139    if ( mark[num] )
140    {
141        Delete( 0, num );
142
143        if ( arr[num][0!= -1 )
144        {
145            arr_dif[num - arr[num][0]]++;
146            if ( arr[num][1!= -1 )
147                arr[arr[num][1]][0= arr[num][0];
148        }

149        else if ( arr[num][1!= -1 ) 
150            arr[arr[num][1]][0= -1;
151        if ( arr[num][1!= -1 )
152        {
153            arr_dif[arr[num][1- num]++;
154            if ( arr[num][0!= -1 )
155            arr[arr[num][0]][1= arr[num][1];
156            
157        }

158        else if ( arr[num][0!= -1 )
159            arr[arr[num][0]][1= -1;
160
161        if ( arr[num][0!= -1 && arr[num][1!= -1 )
162            PQ.push( arr[num][1- arr[num][0] );
163        
164        arr[num][0= arr[num][1= -1;
165        mark[num] = false;
166        N--;
167    }

168}

169
170void Generate(const int& num)
171{
172    if ( !mark[num] )
173    {
174        gMin = gMax = -1;
175        Insert( 0, num );
176
177        if ( gMin > num )
178            gMin = -1;
179        if ( gMax < num )
180            gMax = -1;
181
182        if ( gMin != -1 )
183        {
184            PQ.push( num - gMin );
185            arr[gMin][1= num;
186        }

187        if ( gMax != -1 )
188        {
189            PQ.push( gMax - num );
190            arr[gMax][0= num;
191        }

192
193        arr[num][0= gMin;
194        arr[num][1= gMax;
195        
196        if ( gMin != -1 && gMax != -1 )
197            arr_dif[gMax - gMin]++;
198        mark[num] = true;
199        N++;
200    }

201}

202
203void Query()
204{
205    if ( N < 2 )
206    {
207        printf("-1\n");
208        return;
209    }

210    int i, t;
211
212    t = PQ.top();
213    while ( arr_dif[t] != 0 )
214    {
215        for ( i = 0; i < arr_dif[t]; ++i )
216            PQ.pop();
217        arr_dif[t] = 0;
218        t = PQ.top();
219    }

220
221    printf("%d\n", t);
222}

223
224int main()
225{
226//    freopen("1.txt", "r", stdin);
227
228    int t, n, i, num;
229    char str[20];
230    t = 0;
231    Build( t, 1100000 );
232
233    scanf("%d"&t);
234
235    while ( t-- )
236    {
237        Init();
238        scanf("%d"&n);
239        
240        for ( i = 0; i < n; ++i )
241        {
242            scanf("%s", str);
243
244            if ( str[0== 'q' )
245            {
246                Query();
247            }

248            else if ( str[0== 'r' )
249            {
250                scanf("%d"&num);
251                Remove( num );
252            }

253            else {
254                scanf("%d"&num);
255                Generate( num );
256            }

257        }

258        printf("\n");
259    }

260    return 0;
261}
posted on 2009-04-20 21:20 閱讀(153) 評論(0)  編輯 收藏 引用 所屬分類: 數據結構
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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| 免费一级欧美片在线观看| 久久久久久亚洲精品杨幂换脸 | 国产一区二区三区不卡在线观看 | 欧美亚韩一区| 国产欧美日韩在线播放| 永久免费精品影视网站| 亚洲日本在线观看| 欧美在线视频全部完| 欧美激情免费在线| 亚洲欧美国产精品va在线观看| 久久久久久久一区二区| 国产精品igao视频网网址不卡日韩 | 亚洲综合精品自拍| 免费观看在线综合色| 亚洲视频综合| 欧美88av| 在线国产精品播放| 先锋影音一区二区三区| 亚洲欧洲视频在线| 久久夜色精品亚洲噜噜国产mv | 久久艳片www.17c.com| 国产精品尤物| 中文在线资源观看视频网站免费不卡| 久久婷婷蜜乳一本欲蜜臀| 一本色道久久综合亚洲精品高清| 久久久亚洲国产天美传媒修理工 | 欧美日韩综合不卡| 亚洲欧洲视频| 男女精品网站| 久久久噜噜噜久久狠狠50岁| 国产欧美日韩亚洲| 欧美亚洲免费电影| 一区二区三区四区精品| 欧美激情视频一区二区三区在线播放 | 亚洲无限av看| 91久久国产综合久久| 美女久久网站| 永久域名在线精品| 狂野欧美一区| 久久久欧美精品sm网站| 国产三区二区一区久久| 欧美专区在线观看| 欧美怡红院视频| 国产综合视频| 久久先锋影音| 久久深夜福利免费观看| 亚洲第一精品影视| 亚洲高清久久网| 欧美大香线蕉线伊人久久国产精品| 欧美福利电影网| 久久久久久亚洲精品杨幂换脸 | 99热精品在线观看| 亚洲人屁股眼子交8| 欧美精品二区三区四区免费看视频| 亚洲日本欧美| 日韩亚洲欧美精品| 国产精品视频一| 久久狠狠一本精品综合网| 欧美一区二区三区免费看| 国产亚洲视频在线| 欧美成年人视频| 欧美激情欧美狂野欧美精品| 亚洲淫片在线视频| 午夜精品久久久久久久99水蜜桃| 国内久久婷婷综合| 亚洲国产精品欧美一二99| 欧美日韩国产美女| 欧美亚洲在线| 男女精品视频| 午夜精品久久久| 久久先锋资源| 夜夜躁日日躁狠狠久久88av| 亚洲欧美电影在线观看| 亚洲国产精品t66y| 一区二区三区精密机械公司 | 欧美特黄一区| 另类春色校园亚洲| 欧美亚洲第一区| 蜜桃久久av| 欧美网站在线观看| 免费日韩视频| 国产精品久久久久久久免费软件 | 中文精品在线| 狠狠色狠狠色综合日日五| 亚洲精品久久| 国内综合精品午夜久久资源| 亚洲人人精品| 在线观看一区视频| 亚洲一区二区三区高清不卡| 亚洲高清视频一区二区| 亚洲主播在线观看| 日韩视频一区二区| 久久亚洲综合网| 久久国产欧美| 国产精品jizz在线观看美国 | 欧美韩日一区二区| 国产亚洲欧美激情| 一本色道久久综合狠狠躁篇怎么玩| 国产一区二区三区在线观看免费 | 亚洲国产一区在线观看| 狠狠v欧美v日韩v亚洲ⅴ| 一区二区高清| 在线视频免费在线观看一区二区| 久久se精品一区精品二区| 午夜精品久久久久久久久久久久| 欧美黑人多人双交| 欧美成人资源网| 在线播放中文字幕一区| 欧美一区二区视频97| 欧美在线免费播放| 国产精品久久久久久久久久直播| 日韩网站免费观看| 一区二区三区|亚洲午夜| 欧美激情亚洲精品| 亚洲精品一区二区三区99| 亚洲国产一区视频| 免费一区视频| 欧美福利视频在线观看| 亚洲国产精品视频| 免费不卡中文字幕视频| 亚洲第一级黄色片| 日韩一级大片在线| 欧美人交a欧美精品| 亚洲伦理精品| 亚洲一区二区三区精品视频| 欧美日韩中文字幕在线| 99国产精品久久久久久久| 中日韩男男gay无套| 国产精品久久久亚洲一区 | 久久亚洲精品伦理| 欧美成人亚洲| 日韩一级网站| 国产精品扒开腿爽爽爽视频 | 亚洲自拍偷拍麻豆| 久久九九精品| 亚洲第一中文字幕在线观看| 免费中文日韩| 日韩午夜精品| 久久精精品视频| 亚洲国产精品va| 欧美三区在线视频| 欧美亚洲自偷自偷| 欧美sm视频| 亚洲图片在线| 国语对白精品一区二区| 免费在线观看日韩欧美| 99精品欧美一区二区三区| 欧美一区午夜精品| 亚洲国产精品成人一区二区| 欧美日韩一区二区在线观看视频| 亚洲欧美日本另类| 欧美高清视频一区二区| 亚洲一区二区高清| 国内成人自拍视频| 欧美日韩精品在线视频| 欧美一级欧美一级在线播放| 欧美国产成人精品| 午夜精品www| 91久久线看在观草草青青| 欧美少妇一区二区| 久久一区免费| 亚洲午夜精品福利| 亚洲国产精品欧美一二99| 欧美一区二区三区视频| 亚洲精品一区二区在线| 国产精品一国产精品k频道56| 久久久蜜桃精品| 亚洲午夜激情免费视频| 亚洲黄色av一区| 久久不见久久见免费视频1| 99国产精品久久久| 永久免费视频成人| 国产欧美日韩不卡| 欧美日韩成人在线| 久热成人在线视频| 亚洲欧美中文另类| 正在播放欧美视频| 亚洲美女黄色| 欧美福利视频| 麻豆精品一区二区av白丝在线| 亚洲欧美久久久久一区二区三区| 91久久精品www人人做人人爽 | 欧美激情免费观看| 免费看精品久久片| 久久久伊人欧美| 欧美伊人精品成人久久综合97| 一本一本久久a久久精品综合妖精 一本一本久久a久久精品综合麻豆 | 一区二区视频欧美| 国产亚洲一区二区在线观看 | 欧美一区二区三区男人的天堂| 99这里有精品| 日韩午夜电影av| 99在线观看免费视频精品观看| 91久久在线观看| 亚洲精品乱码久久久久久日本蜜臀 | 免费观看成人| 免播放器亚洲一区|