Rotating Segment Tree
IntuitionInitially there is a segment [0,inf].
Each query type 1 will split one segment into two.
We can store segments in segment tree and get max queries effi
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
Initially there is a segment [0,inf].
Each query type 1 will split one segment into two.
We can store segments in segment tree and get max queries efficiently.

# Approach
<!-- Describe your approach to solving the problem. -->
My first solution got TLE because my tree got too unbalanced in some cases.
I've tried rerooting it every time its size became a power of 2 but still got TLE. 
Finally, today I've learned about AVL trees and figured that segment tree can also be rotated in similar way to keep it balanced.
rotation visualized:
![rotate white.jpg](https://assets.leetcode.com/users/images/a599be1f-780e-4eaa-8af7-bd1d58078d20_1738002326.7371163.jpeg)
I havent found other solutions that use this kind of segment tree(with rotations). Is this kind of data structure well known? Let me know in the comments.



# Complexity
- Time complexity:$$O(nlogn)$$
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity$$O(n)$$:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```python3 []
class rotatingSegmentTree:
    def __init__(self,lo=0,hi=inf):
        self.lo=lo
        self.hi=hi
        self.val=hi-lo
        self.h=self.b=0
        self.left=self.right=None

    def split(self,x):
        if x<self.lo or self.hi<=x:
            return
        if not self.left:
            self.left=rotatingSegmentTree(self.lo,x)
            self.right=rotatingSegmentTree(x,self.hi)
            self.reEval()
        else:
            self.left.split(x)
            self.right.split(x)
            self.reEval()
            if self.b>1:
                if self.right.b<-1:
                    self.right.rotateRight()
                self.rotateLeft()
            elif self.b<-1:
                if self.left.b>1:
                    self.left.rotateLeft()
                self.rotateRight()
            
    
    def rotateLeft(self):
        l,r=self.left,self.right
        rl,rr=r.left,r.right
        self.right=rr
        self.left=rotatingSegmentTree(l.lo,rl.hi)
        self.left.left=l
        self.left.right=rl
        self.left.reEval()
        self.reEval()

    def rotateRight(self):
        l,r=self.left,self.right
        ll,lr=l.left,l.right
        self.left=ll
        self.right=rotatingSegmentTree(lr.lo,r.hi)
        self.right.left=lr
        self.right.right=r
        self.right.reEval()
        self.reEval()
        
    def reEval(self):
        self.h=1+max(self.left.h,self.right.h)
        self.val=max(self.left.val,self.right.val)
        self.b=self.right.h-self.left.h

    def query(self,x):
        if self.hi<=x:
            return self.val
        if x<self.lo:
            return 0
        if not self.left:
            return x-self.lo
        return max(self.left.query(x),self.right.query(x))

class Solution:
    def getResults(self, queries: List[List[int]]) -> List[bool]:
        ans=[]
        tree=rotatingSegmentTree()
        for q in queries:
            if q[0]==1:
                tree.split(q[1])
            else:
                _,x,size=q
                ans.append(tree.query(x)>=size)
        return ans
```
['Segment Tree', 'Python3']