CVBB ACM Team

$q$ 次询问，每次给出一个 $n$，问 $n$ 个点最多能连几条边使得桥的个数大于等于边数的一半。 $q\le10^5,n\le2\cdot10^9$

考虑 $n$ 个点最多形成 $n-1$ 个桥，因此将 $n$ 个点顺次链接。现在考虑向其中加边，若前 $x$ 个点构成了完全图，显然之后是依次连接 $1\sim x$ 和 $x+1$ 最优，因此我们考虑 $x$ 最大为多少。 $x$ 要满足以下式子：$$sum=C(x,2)+n-x,n-x\ge \frac{ans}{2}$$合并得到 $x^2+x\le2n$，可以通过解方程 $O(1)$ 得到。接下来考虑加边，考虑桥的数量和非桥边的数量的差值 $s$，要求 $s\ge0$ ，加的第一条边会增加两条非桥边并且减少一条桥边， 即 $s=s-3$ ，之后每加一条边 $s=s-1$，因此当 $s\ge3$ 时可以增加 $s-2$ 条边 ，否则不可以加边，因此每个询问可以 $O(1)$ 计算出答案。