线段树处理集合里的最小差值

题意：给你一个集合，集合里没有重复元素。集合可以添加元素，也可以删除元素(前提是集合里有)，另外还有一个询问操作，问集合里最小的差值是多少(只有一个元素的时候询问无效)

例如，集合开始的时候有1 7两个元素，那么最小差值就是6。当再添加一个新的元素3，集合就变成了1 3 7，那么最小差值就是2。

解法：对于每一个区间线段，我们给它3个属性，最小值minf，最大值maxf，以及最小差值deff。

从下而上，我们很容易可以看出，某一个线段 i 的最小值为min(left_child[i].minf，right_child[i].minf)

最大值为max(left_child[i].maxf，right_child[i].maxf)

最小差值等于min（min（左右子区间的最小差值），右子区间的最小值减去左子区间的最大值）

View Code

  1 #include<iostream>
  2 #include<string>
  3 #include<cmath>
  4 #include<algorithm>
  5 using namespace std;
  6 #define inf 0xfffffff
  7 
  8 struct node
  9 {
 10     int l;
 11     int r;
 12     int minf; //该区间最小值
 13     int maxf; //该区间最大值
 14     int deff; //该区间的最小差值
 15 };
 16 
 17 node tree[1000000];
 18 
 19 int max(int a,int b)
 20 {
 21     return a>b?a:b;
 22 }
 23 
 24 int min(int a,int b)
 25 {
 26     return a<b?a:b;
 27 }
 28 
 29 void build(int i,int l,int r)
 30 {
 31     tree[i].l=l;
 32     tree[i].r=r;
 33     tree[i].minf=inf;
 34     tree[i].maxf=-inf;
 35     tree[i].deff=inf;
 36     if(l==r)
 37         return;
 38     int mid=(l+r)/2;
 39     build(2*i,l,mid);
 40     build(2*i+1,mid+1,r);
 41 }
 42 
 43 int query()
 44 {
 45     return tree[1].deff<100100?tree[1].deff:-1;
 46 }
 47 
 48 void updata(int i)
 49 {
 50     tree[i].minf=min(tree[2*i].minf,tree[2*i+1].minf);
 51     tree[i].maxf=max(tree[2*i].maxf,tree[2*i+1].maxf);
 52     tree[i].deff=min(tree[2*i].deff,tree[2*i+1].deff);
 53     tree[i].deff=min(tree[i].deff,tree[2*i+1].minf-tree[2*i].maxf);
 54 }
 55 
 56 void add(int i,int l,int r)
 57 {
 58     if(tree[i].l>r || tree[i].r<l)
 59         return;
 60     if(tree[i].l>=l && tree[i].r<=r)
 61     {
 62         tree[i].maxf=l;
 63         tree[i].minf=l;
 64         return;
 65     }
 66     add(2*i,l,r);
 67     add(2*i+1,l,r);
 68     updata(i);
 69 }
 70 
 71 void det(int i,int l,int r)
 72 {
 73     if(tree[i].l>r || tree[i].r<l)
 74         return;
 75     if(tree[i].l>=l && tree[i].r<=r)
 76     {
 77         tree[i].maxf=-inf;
 78         tree[i].minf=inf;
 79         return;
 80     }
 81     det(2*i,l,r);
 82     det(2*i+1,l,r);
 83     updata(i);
 84 }
 85 
 86 int main()
 87 {
 88     int cas,n,a,flag=0;
 89     char str[20];
 90     freopen("E.in","r",stdin);
 91     freopen("E.out","w",stdout);
 92     scanf("%d",&cas);
 93     while(cas--)
 94     {
 95         if(flag)
 96             printf("\n");
 97         flag=1;
 98         scanf("%d",&n);
 99         build(1,1,100000);
100         while(n--)
101         {
102             scanf("%*c%s",str);
103             if(str[0]=='g')
104             {
105                 scanf("%d",&a);
106                 add(1,a,a);
107             }
108             else if(str[0]=='r')
109             {
110                 scanf("%d",&a);
111                 det(1,a,a);
112             }
113             else
114             {
115                 a=query();
116                 printf("%d\n",a);
117             }
118         }
119     }
120     return 0;
121 }