Cheaters and Queries

Let the liar segment be $[L,R]$. Person $i$ is a liar exactly when $i \in [L,R]$, while person $i$'s claim is true exactly when $[l_i,r_i]$ intersects $[L,R]$. These two Boolean values must be different.

For every person, define

$$a_i=\min(i,r_i),\qquad b_i=\max(i,l_i),\qquad c_i=\min(i,l_i),\qquad d_i=\max(i,r_i).$$

Person $i$ is inside the liar segment and has a true claim exactly when $L \leq a_i$ and $b_i \leq R$.

Person $i$ is outside the liar segment and also has a false claim in one of the following three forms.

• $R<c_i$.
• $d_i<L$.
• $a_i<L \leq R<b_i$. The last form occurs when the liar segment lies strictly between person $i$ and their claim interval.

Define

$$A=\min_i d_i,\qquad B=\max_i c_i,$$ $$M(L)=\max_{a_i<L} b_i,\qquad G(L)=\min_{a_i\geq L} b_i.$$

If the set for $M(L)$ is empty, use $0$. If the set for $G(L)$ is empty, use $N+1$.

An interval $[L,R]$ is valid if and only if

$$L\leq A,\qquad \max(B,L,M(L))\leq R<G(L).$$

The first inequality eliminates every case of the form $d_i<L$. The bound $R\geq B$ eliminates every case of the form $R<c_i$. The bound $R\geq M(L)$ eliminates every case of the form $a_i<L \leq R<b_i$. Finally, $R<G(L)$ eliminates every person satisfying $L\leq a_i$ and $b_i\leq R$. Thus the criterion removes exactly all contradictions listed above.

We now maintain $M(L)$ and $G(L)$ dynamically. For every coordinate $x$, maintain

$$\mathrm{hi}_x=\max_{a_i=x} b_i,\qquad \mathrm{lo}_x=\min_{a_i=x} b_i.$$

Then $M(L)$ is a prefix maximum of $\mathrm{hi}$, and $G(L)$ is a suffix minimum of $\mathrm{lo}$. People with the same $a_i$ are stored in a multiset. The values $A$ and $B$ are maintained with multisets of $d_i$ and $c_i$ as well.

Split the coordinates $1,2,\cdots,N$ into blocks of size about $\sqrt N$. For every candidate $L$ in a block $[s,e]$, precompute

$$X_L=\max\left(L,\max_{s\leq x<L}\mathrm{hi}_x\right),\qquad Y_L=\min_{L\leq x\leq e}\mathrm{lo}_x.$$

Both $X_L$ and $Y_L$ are nondecreasing as $L$ increases. Also store all positions satisfying $X_L<Y_L$.

Let $P$ be the maximum $\mathrm{hi}$ value in all earlier blocks, and let $S$ be the minimum $\mathrm{lo}$ value in all later blocks. A candidate $L$ in this block is feasible exactly when

$$\max(B,P,X_L)<\min(S,Y_L).$$

This is equivalent to the following four conditions.

• $\max(B,P)<S$.
• $X_L<S$.
• $Y_L>\max(B,P)$.
• $X_L<Y_L$.

Because $X_L$ and $Y_L$ are monotone, two binary searches give the range of positions satisfying the middle bounds. We then check whether one of the stored positions with $X_L<Y_L$ lies in that range. Once such an $L$ is found, set

$$R=\max(B,P,X_L).$$

Only candidates with $L\leq A$ are considered.

One claim update changes only the blocks containing the old and new values of $a_i$. Therefore, at most two blocks need to be rebuilt.

The time complexity per update is $O(\sqrt N\log N)$, and the memory complexity is $O(N)$.

Solution written by GPT5.6