ACM winter vacation training 5

Line segment tree

Line segment tree is a binary search tree , Similar to interval trees , It divides an interval into some cell intervals , Each cell interval corresponds to a leaf node in the line segment tree .
Using line segment tree can quickly find the number of times a node appears in several line segments , The time complexity is O(logN). The unoptimized space complexity is 2N, In practical application, it usually needs to be opened 4N To avoid crossing the bounds , So sometimes discretization is needed to compress space .
For each non leaf node in the segment tree [a,b], Its left son represents the interval [a,(a+b)/2], The range represented by the right son is [(a+b)/2+1,b]. Therefore, the segment tree is a balanced binary tree , The last number of child nodes is N, That is, the length of the whole segment interval .
Using line segment tree can quickly find the number of times a node appears in several line segments , The time complexity is O(logN）. The unoptimized space complexity is 2N, So sometimes discretization is needed to compress space .

The basic structure

Segment tree is based on segment , Each node represents a line segment [a,b]. The length is 1 The line segment of is called meta line segment . Non element line segments have two child nodes , The line segment represented by the left node is [a,(a + b) / 2], The line segment represented by the right node is [((a + b) / 2）+1,b].
The length range is [1,L] The depth of a segment tree is log (L) + 1. This is obviously , And the space complexity of storing a segment tree is O(L）.
The most basic operations supported by the segment tree are inserting and deleting a segment . Let's take insertion as an example , To narrate in detail , Delete something like .
Put a line segment [a,b] Insert into the representative line segment [l,r] The node of p in , If p Not a meta line segment , So make mid=（l+r）/2. If b<mid, Then the line segment [a,b] Also inserted into p In the left son node of , If a>mid, Then the line segment [a,b] Also inserted into p In the right son node of .
Insert （ Delete ） The time complexity of the operation is O（logn）.

Basic code

The following operations are supported
1 x if x non-existent , Insert x
2 x if x There is , Delete x
3 Output the current minimum value , If there is no output -1
4 Output the current maximum , If there is no output -1
5 x Output x The precursor of , If there is no output -1
6 x Output x In the subsequent , If there is no output -1
7 x if x There is , Output 1, Otherwise output -1

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<queue>
#define inf 1000000000
using namespace std;
int n,m;
struct seg{
    int l,r,v;}t[3000005];
void build(int k,int l,int r)                       // Build up trees  k： Current node subscript   The left of the line segment is l, The right of the line segment is r
{
    
   t[k].l=l;t[k].r=r;                              // Left end of line segment , The right end of the line segment 
   if(l==r)return;                                 // The length of the line segment is zero , end 
   int mid=(l+r)>>1;                               // Take the midpoint of the line 
   build(k<<1,l,mid);                              //k<<1: Subscript to be k The left subscript of the node , The left of the line segment is l, The right of the line segment is mid k<<1==k*2
   build(k<<1|1,mid+1,r);                          //k<<1|1: Subscript to be k The right subscript of the node , The left of the line segment is mid+1, The right of the line segment is r k<<1|1==k*2+1
}
 
int mn(int k)
{
    
    if(!t[k].v)return -1;
    int l=t[k].l,r=t[k].r;
    if(l==r)return l;
    if(t[k<<1].v)return mn(k<<1);
    else return mn(k<<1|1);
}
int mx(int k)
{
    
    if(!t[k].v)return -1;
    int l=t[k].l,r=t[k].r;
    if(l==r)return l;
    if(t[k<<1|1].v)return mx(k<<1|1);
    else return mx(k<<1);
}
void insert(int k,int val)
{
    
    int l=t[k].l,r=t[k].r;
    if(l==r){
    t[k].v=1;return;}
    int mid=(l+r)>>1;
    if(val<=mid)insert(k<<1,val);
    else insert(k<<1|1,val);
    t[k].v=t[k<<1].v+t[k<<1|1].v;
}
int find(int k,int val)
{
    
    int l=t[k].l,r=t[k].r;
    if(l==r)
    {
    
        if(t[k].v)return 1;
        return -1;
    }
    int mid=(l+r)>>1;
    if(val<=mid)return find(k<<1,val);
    else return find(k<<1|1,val);
}
void del(int k,int val)
{
    
    int l=t[k].l,r=t[k].r;
    if(l==r){
    t[k].v=0;return;}
    int mid=(l+r)>>1;
    if(val<=mid)del(k<<1,val);
    else del(k<<1|1,val);
    t[k].v=t[k<<1].v+t[k<<1|1].v;
}
int findpr(int k,int val)
{
    
    if(val<0)return -1;
    if(!t[k].v)return -1;
    int l=t[k].l,r=t[k].r;
    if(l==r)return l;
    int mid=(l+r)>>1;
    if(val<=mid)return findpr(k<<1,val);
    else 
    {
    
        int t=findpr(k<<1|1,val);
        if(t==-1)return mx(k<<1);
        else return t;
    }
}
int findsu(int k,int val)
{
    
    if(!t[k].v)return -1;
    int l=t[k].l,r=t[k].r;
    if(l==r)return l;
    int mid=(l+r)>>1;
    if(val>mid)return findsu(k<<1|1,val);
    else 
    {
    
        int t=findsu(k<<1,val);
        if(t==-1)return mn(k<<1|1);
        else return t;
    }
}
int main()
{
    
    scanf("%d %d",&n,&m);
    build(1,0,n);
    int opt,x;
    for(int i=1;i<=m;i++)
    {
    
        scanf("%d",&opt);
        switch(opt)
        {
    
        case 1:scanf("%d",&x);if(find(1,x)==-1)insert(1,x);break;
        case 2:scanf("%d",&x);if(find(1,x)==1)del(1,x);break;
        case 3:printf("%d\n",mn(1));break;
        case 4:printf("%d\n",mx(1));break;
        case 5:scanf("%d",&x);printf("%d\n",findpr(1,x-1));break;
        case 6:scanf("%d",&x);printf("%d\n",findsu(1,x+1));break;
        case 7:scanf("%d",&x);printf("%d\n",find(1,x));break;
        }
    }
    return 0;
}