P6617 查找 Search 笔记

由于只要求两个数，所以可能对答案的贡献是一对一对的点对。

根据支配点对的想法，如果有 $(l,r)$ 满足 $a_l+a_r=w$，且存在 $l<x<r$ 满足 $a_x+a_r=w$，那么 $(l,r)$ 对答案无贡献，因此，与每个点有关的点对最多只有两对，由于每次只做单点修改，所以使用 set 找到修改前后相关的配对位置进行点对修改即可。

对于每个 $l$，线段树维护其配对的位置 ${\mathrm{nxt}}_l=r$，则询问就相当于问是否有 $\underset{i=l}{\overset{r}{min}}{\mathrm{nxt}}_{\mathrm{i}}\le r$，维护单点修改、区间取 $min$ 的线段树。

时间复杂度 $O(n\log n)$，空间复杂度 $O(n)$。