问题B : 绝地求生 珂朵莉树

题目描述
吃鸡开局了，你降落的森林中有一条长度为S的小路(编号从1到S)，且在小路上时常会起雾，你手上的激光发射器可以让雾消散。
你肯定你所在位置的视野。若位置x有浓雾，则位置x的视野为0。若从x一直到S或从x一直到1全都没有浓雾，则视野为INF。其他情况下，位置x的视野定义为max{R-L-1}，其中L,R满足:，x0格子没有浓雾。
具体来说，会有以下事件发生:
1、“1 L R”小路的[L,R]部分产生了浓雾;
2、“2 L R”小路的[L,R]部分浓雾散去了；
3、“3 X”查询X点的视野。
一开始，小路上没有任何浓雾。

输入
第一行一个整数，为小路的长度S。
第二行一个整数，为事件数Q。
接下来Q行，每行一个事件，格式如题目描述。

输出
对于每一个询问事件，输出一个整数或一行字符串“INF”，代表所求视野。

样例输入
复制样例数据
5
5
1 2 4
3 1
3 4
2 3 3
3 3
样例输出
INF
0
1

提示
对于 40%的数据，SQ <= 510^7。
对于 100%的数据，2≤S≤100,000,2≤Q≤200,000，1≤L≤R≤S，1≤X≤S。

这个题目用线段树不会写， 网上的题解看的也迷迷糊糊的，忽然发现一个很很牛逼又很玄学的做法
珂朵莉树

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
typedef long long ll ;
const int N = 1e5 + 10 , mod = 1e9 + 7 ;
struct node
{
    int l , r ;
    mutable ll val ;
    bool operator<(const node o) const {
    return l < o.l ;
    }
};
int n , q , ans , op , l , r , x , y ;
set<node> T ;
typedef set<node>::iterator It ;
It split(int pos)
{
    It it = T.lower_bound({pos , pos , 0}) ;
    if(it != T.end() && it->l == pos) return it ;
    -- it ;
    int L = it->l , R = it->r ;
    ll val = it->val ;
    T.erase(it) , T.insert({L , pos - 1 , val}) ;
    return T.insert({pos , R , val}).first ;
}
void Assign(int l , int r , int val)
{
    It itr = split(r + 1) , itl = split(l) ;
    T.erase(itl , itr) , T.insert({l , r , 1ll * val}) ;
}
void query(int x)
{
    It pos = split(x) ;
    if(pos->val == 1)
     {
        puts("0") ;
        return ;
     }
     int l = 1 , r = n ;
     for(It i = pos ;  ;i --)
      {
        if(i->val == 1)
         {
            l = i->r + 1 ;
            break ;
           }
           if(i == T.begin()) break ;
      }
      for(It i = pos ;i != T.end() ;i ++)
       {
        if(i->val == 1)
         {
            r = i->l - 1 ;
            break ;
            }
       }
       if(l == 1 || r == n)
        {
            puts("INF") ;
        }
        else printf("%d
" , r - l + 1) ;
}
int main()
{
    scanf("%d%d" , &n , &q) ;
    T.insert({1 , n , 0}) ;
    while(q --)
    {
        scanf("%d" , &op) ;
        if( op == 1)
         {
            scanf("%d%d" , &l , &r) ;
            Assign(l , r , 1) ;
         }
         else if(op == 2)
          {
            scanf("%d%d" , &l , &r) ;
            Assign(l , r , 0) ;
          }
          else
          {
            scanf("%d" , &l) ;
            query(l) ;
          }
    }
    return 0 ;
}