<p>You are given an integer <code>n</code> denoting the total number of servers and a <strong>2D</strong> <strong>0-indexed </strong>integer array <code>logs</code>, where <code>logs[i] = [server_id, time]</code> denotes that the server with id <code>server_id</code> received a request at time <code>time</code>.</p>

<p>You are also given an integer <code>x</code> and a <strong>0-indexed</strong> integer array <code>queries</code>.</p>

<p>Return <em>a <strong>0-indexed</strong> integer array</em> <code>arr</code> <em>of length</em> <code>queries.length</code> <em>where</em> <code>arr[i]</code> <em>represents the number of servers that <strong>did not receive</strong> any requests during the time interval</em> <code>[queries[i] - x, queries[i]]</code>.</p>

<p>Note that the time intervals are inclusive.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 3, logs = [[1,3],[2,6],[1,5]], x = 5, queries = [10,11]
<strong>Output:</strong> [1,2]
<strong>Explanation:</strong> 
For queries[0]: The servers with ids 1 and 2 get requests in the duration of [5, 10]. Hence, only server 3 gets zero requests.
For queries[1]: Only the server with id 2 gets a request in duration of [6,11]. Hence, the servers with ids 1 and 3 are the only servers that do not receive any requests during that time period.

</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 3, logs = [[2,4],[2,1],[1,2],[3,1]], x = 2, queries = [3,4]
<strong>Output:</strong> [0,1]
<strong>Explanation:</strong> 
For queries[0]: All servers get at least one request in the duration of [1, 3].
For queries[1]: Only server with id 3 gets no request in the duration [2,4].

</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= logs.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= queries.length &lt;= 10<sup>5</sup></code></li>
	<li><code><font face="monospace">logs[i].length == 2</font></code></li>
	<li><code>1 &lt;= logs[i][0] &lt;= n</code></li>
	<li><code>1 &lt;= logs[i][1] &lt;= 10<sup>6</sup></code></li>
	<li><code>1 &lt;= x &lt;= 10<sup>5</sup></code></li>
	<li><code>x &lt;&nbsp;queries[i]&nbsp;&lt;= 10<sup>6</sup></code></li>
</ul>

class Solution:
    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:
        m=defaultdict(set)
        for sid,t in logs:
            m[t].add(sid)
        times=list(sorted(m.keys()))
        ps={}
        ps[times[0]]=Counter(m[times[0]])
        for i in range(1,len(times)):
            nc=ps[times[i-1]].copy()
            for server in m[times[i]]:
                nc[server]+=1
            ps[times[i]]=nc
        # print(ps)

        res=[]
        for end in queries:
            start=end-x
            left=bisect_left(times, start)
            if left==len(times):
                res.append(n)
                continue
            right=bisect_right(times, end)-1
            if right<0:
                res.append(n)
                continue
            # print(left,right)
            leftcounter=ps[times[left]]
            rightcounter=ps[times[right]]
            cnt=0
            for k,v in rightcounter.items():
                if v-leftcounter[k] + (1 if k in m[times[left]] else 0)>0:
                    cnt+=1
            res.append(n-cnt)
        return res

class Solution:
    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:
        logs.sort(key=lambda x: x[1])
        # print(logs)
        qs=[[q,i] for i,q in enumerate(queries)]
        qs.sort()
        # print(qs)
        res=[0 for _ in range(len(queries))]
        first_start=qs[0][0]-x
        first_end=qs[0][0]
        i=0
        left=0
        while i<len(logs) and logs[i][1]<first_start:
            i+=1
        left=i
        counter=Counter()
        while i<len(logs) and logs[i][1]<=first_end:
            counter[logs[i][0]]+=1
            i+=1
        res[qs[0][1]]=n-len(counter)
        for j in range(1,len(qs)):
            # print(counter)
            # print("start left,i",left,i)
            start=qs[j][0]-x
            end=qs[j][0]
            while left<i and logs[left][1]<start:
                counter[logs[left][0]]-=1
                if counter[logs[left][0]]==0:
                    del counter[logs[left][0]]
                left+=1
            while left<len(logs) and logs[left][1]<start:
                left+=1
            i=max(i,left)
            while i<len(logs) and logs[i][1]<=end:
                counter[logs[i][0]]+=1
                i+=1
            res[qs[j][1]]=n-len(counter)
            # print("end left,i",left,i)
            # print("end - start,end",start,end)
        return res


79000