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 阅读(133) 评论(0)  编辑 收藏 引用 所属分类: 数据结构

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