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

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>
            亚洲激情在线观看| 欧美高清在线视频| 久久久久一区二区三区| 99re这里只有精品6| 亚洲欧洲偷拍精品| 国产在线精品一区二区夜色| 欧美激情视频在线免费观看 欧美视频免费一| 欧美精品在线一区| 美女诱惑一区| 国产精品久久久久久亚洲毛片| 久久伊人亚洲| 欧美国产乱视频| 久久久国产视频91| 国产精品国产成人国产三级| 欧美多人爱爱视频网站| 欧美精品尤物在线| 久久精品夜色噜噜亚洲aⅴ| 一本大道av伊人久久综合| 国产一区二区三区在线免费观看| 亚洲精品美女在线| 日韩视频在线一区二区三区| 在线观看亚洲一区| 亚洲精品欧美精品| 国产精品99久久久久久白浆小说| 久久―日本道色综合久久| 欧美日韩在线一区| 亚洲欧洲精品一区二区精品久久久| 狠狠干狠狠久久| 亚洲人成7777| 亚洲第一网站免费视频| 欧美阿v一级看视频| 国产日韩亚洲| 在线一区二区三区四区五区| 国产一区99| 欧美一区二区三区免费看| 模特精品裸拍一区| 免费精品视频| 精品动漫3d一区二区三区免费| 亚洲精选在线| 亚洲一级黄色片| 欧美日韩一区二区三区免费| 亚洲精品一区二区三区99| 99视频精品| 欧美精选在线| 一区二区三区日韩精品视频| 亚洲精品久久久一区二区三区| 久久精品国产欧美亚洲人人爽| 久久aⅴ乱码一区二区三区| 欧美日韩国产美女| 亚洲欧美国产va在线影院| 一区二区三区高清不卡| 国产日韩欧美在线播放不卡| 国产婷婷97碰碰久久人人蜜臀| 欧美日韩亚洲视频一区| 亚洲少妇诱惑| 亚洲一区二区三区在线播放| 中文国产成人精品久久一| 91久久久久久久久久久久久| 久久精品一区二区三区不卡| 午夜在线视频一区二区区别| 亚洲老司机av| 一区二区欧美日韩| 亚洲天堂免费在线观看视频| 中文高清一区| 一区二区三区免费观看| 欧美aa在线视频| 快射av在线播放一区| 欧美国产高清| 欧美国产日本在线| 亚洲一区欧美一区| 亚洲永久免费视频| 久久免费精品日本久久中文字幕| 久久人人九九| 亚洲激情视频| 久久免费视频一区| 国产欧美日韩伦理| 国模私拍一区二区三区| 日韩亚洲欧美一区二区三区| 久久久国产精彩视频美女艺术照福利| 亚洲丰满少妇videoshd| 国产精品三级视频| 久久综合九色| 欧美一级久久久久久久大片| 99热免费精品| 久久美女性网| 国产综合av| 久久精品道一区二区三区| 欧美成va人片在线观看| 久久久精品免费视频| 久久午夜电影网| av不卡在线| 欧美福利一区| 欧美在线观看天堂一区二区三区| 亚洲欧洲日产国产网站| 国产日韩欧美日韩大片| 欧美成人dvd在线视频| 午夜免费在线观看精品视频| 欧美国产亚洲精品久久久8v| 久久精品国产精品| 亚洲欧美日韩精品一区二区 | 亚洲欧美国产不卡| 欧美激情第六页| 久久综合成人精品亚洲另类欧美| 亚洲伊人伊色伊影伊综合网| 亚洲毛片在线免费观看| 亚洲国产精品成人一区二区| 国产一区二区日韩| 国产精品久久久一区二区三区| 久久免费黄色| 亚洲欧美日韩一区二区三区在线| 亚洲国产经典视频| 激情欧美日韩| 黄色日韩在线| 国产一区清纯| 国产专区综合网| 国产一区二区三区免费不卡| 国产精品免费看片| 国产精品区二区三区日本 | 狠狠综合久久| 国产一区二区电影在线观看 | 在线综合亚洲欧美在线视频| 亚洲日韩欧美视频一区| 亚洲第一偷拍| 亚洲国产成人久久综合一区| 国产在线一区二区三区四区| 国产日产欧美一区| 国产欧美日韩综合| 国模一区二区三区| 樱桃成人精品视频在线播放| 黄色成人在线网站| 亚洲国产另类精品专区| 亚洲日本成人| 99在线热播精品免费99热| a91a精品视频在线观看| 一本不卡影院| 亚洲欧美精品一区| 久久国产高清| 欧美gay视频激情| 亚洲夫妻自拍| 一区二区av| 亚洲欧美另类国产| 久久―日本道色综合久久| 免费不卡视频| 欧美日韩综合视频网址| 国产精品中文字幕欧美| 激情久久久久久| 亚洲乱码久久| 亚洲欧美激情精品一区二区| 久久精品一区二区国产| 欧美大色视频| 一区二区高清在线| 久久9热精品视频| 欧美第一黄色网| 国产精品九九久久久久久久| 国产婷婷成人久久av免费高清| 在线电影一区| 亚洲一区二区视频在线观看| 久久精品论坛| 亚洲国产精品999| 亚洲欧美区自拍先锋| 久久综合九色综合欧美狠狠| 欧美日韩日韩| 精品999成人| 亚洲视频在线观看| 另类av导航| 在线视频亚洲一区| 老牛嫩草一区二区三区日本 | 国产精品欧美经典| 91久久国产综合久久| 小处雏高清一区二区三区| 欧美成人午夜视频| 亚洲在线中文字幕| 欧美a级一区| 国产亚洲综合精品| 亚洲一区二三| 亚洲国产91| 久久天堂国产精品| 国产日韩欧美日韩大片| 在线观看日韩av先锋影音电影院 | 亚洲黄一区二区三区| 亚洲天堂免费观看| 日韩一二在线观看| 国产精品日韩在线一区| 欧美午夜电影完整版| 久久嫩草精品久久久久| 美女性感视频久久久| 亚洲小说春色综合另类电影| 欧美电影专区| 一区二区免费在线播放| 亚洲在线播放| 噜噜噜久久亚洲精品国产品小说| 狼狼综合久久久久综合网| 麻豆免费精品视频| 欧美新色视频| 亚洲高清不卡| 亚洲影院色无极综合| 美女久久一区| 亚洲一区二区欧美日韩| 欧美精品久久久久久久免费观看| 国产精品久久久久久久久免费樱桃|