学步园

新手赛的题目，让我回想起打酱油的时光

//线段树<br /> #include<iostream><br /> #include<cstdio><br /> #include<cstring><br /> #define INF 100000000<br /> using namespace std;<br /> int T,M;<br /> char cmd[10],n;<br /> bool R[100005],G[100005];<br /> struct seg<br /> {<br /> int l,r,_max,_min,delta;//记录最大值，最小值，最优差值，_max,_min为0表示不存在这个数<br /> }tree[100005*4];<br /> void update(int x)//回溯更新<br /> {<br /> tree[x]._max = max(tree[2*x]._max,tree[2*x+1]._max);<br /> if(!tree[2*x]._min) tree[x]._min = tree[2*x+1]._min;//如果左子树不存在最小值，就用右子树的最小值<br /> else tree[x]._min = tree[2*x]._min;//否则去左子树的最小值<br /> tree[x].delta = min(tree[2*x].delta,tree[2*x+1].delta);//取最优子树的最小差值<br /> if(tree[2*x]._max && tree[2*x+1]._min)//左子树的最大值和右子树的最小值存在的话<br /> tree[x].delta = min(tree[x].delta,tree[2*x+1]._min - tree[2*x]._max);<br /> }<br /> void buildTree(int x,int l,int r)<br /> {<br /> tree[x].l = l;<br /> tree[x].r = r;<br /> tree[x]._max = 0;<br /> tree[x]._min = 0;<br /> tree[x].delta = INF;<br /> if(l == r) return;<br /> int mid = (l+r) >> 1;<br /> buildTree(2*x,l,mid);<br /> buildTree(2*x+1,mid+1,r);<br /> }<br /> void Insert(int x,int l,int r)<br /> {<br /> int mid = (tree[x].l + tree[x].r) >> 1;<br /> if(tree[x].l == l && tree[x].r == r)<br /> {<br /> tree[x]._max = tree[x]._min = l;<br /> return;<br /> }<br /> if(r <= mid) Insert(2*x,l,r);<br /> else if(l > mid) Insert(2*x+1,l,r);<br /> tree[x]._max = max(tree[2*x]._max,tree[2*x+1]._max);<br /> if(!tree[2*x]._min) tree[x]._min = tree[2*x+1]._min;<br /> else tree[x]._min = tree[2*x]._min;<br /> update(x);<br /> }<br /> void Remove(int x,int l,int r)<br /> {<br /> int mid = (tree[x].l + tree[x].r) >> 1;<br /> if(tree[x].l == l && tree[x].r == r)<br /> {<br /> tree[x]._max = tree[x]._min = 0;<br /> tree[x].delta = INF;<br /> return;<br /> }<br /> if(r <= mid) Remove(2*x,l,r);<br /> else if(l > mid) Remove(2*x+1,l,r);<br /> update(x);<br /> }<br /> int Query(int x)//直接询问根结点就能得出结果<br /> {<br /> if(tree[x].delta == INF)<br /> return -1;<br /> else return tree[x].delta;<br /> }</p> <p>int main()<br /> {<br /> int x;<br /> bool first = 1;<br /> //freopen("in.txt","r",stdin);<br /> scanf("%d",&T);<br /> while(T--)<br /> {<br /> if(first) first = 0;<br /> else printf("/n");<br /> buildTree(1,1,100000);<br /> memset(R,0,sizeof(R));//标记是否remove过<br /> memset(G,0,sizeof(G));//标记是否generate过<br /> scanf("%d",&M);<br /> while(M--)<br /> {<br /> scanf("%s",cmd);<br /> if(cmd[0] == 'g')<br /> {<br /> scanf("%d",&x);<br /> if(!G[x])<br /> {<br /> G[x] = 1;<br /> Insert(1,x,x);<br /> R[x] = 0;<br /> }<br /> }<br /> if(cmd[0] == 'r')<br /> {<br /> scanf("%d",&x);<br /> if(!R[x])<br /> {<br /> R[x] = 1;<br /> Remove(1,x,x);<br /> G[x] = 0;<br /> }<br /> }<br /> if(cmd[0] == 'q') printf("%d/n",Query(1));<br /> }<br /> }<br /> }