「模拟赛20190116 T2」序列
题意
给定一个序列的前\(n\)项（\(a_0,a_1,a_2,\cdots,a_{n-1}\)），保证对于所有\(0\le i\le n-1\)，\(a_i\in \{n-1,n,n+1\}\)。对于\(i\ge n\)，\(a_i\)的值为满足\(0\le j< i\)且\(a_j\ge i-j\)的整数\(j\)的数量。
\(q\)个询问，每次询问一个\(x\)，求\(a_x\)的值。
\(1\le n,q\le 10^5,0\le x\le 10^{15}\)。
题解
首先，我们可以利用归纳法证明对于任意\(i\)，\(a_i\in \{n-1,n,n+1\}\)：
假设对于\(0\le j< i\)都满足该性质，则有\[a_i=n-[a_{i-n}=n-1]+[a_{i-n-1}=n+1]\]显然仍有\(a_i\in \{n-1,n,n+1\}\)。
为方便讨论，用\(0,1,2\)分别代替\(n-1,n,n+1\)。
可以发现，假设初始时对于所有\(i\ge n\)，\(a_i=0\)。然后对于一个\(a_i\)，若\(a_i=0\)，则不产生贡献；若\(a_i=1\)，则对\(a_{i+n}\)产生\(1\)的贡献；若\(a_i=2\)，则对\(a_{i+n},a_{i+n+1}\)各产生\(1\)的贡献。
然后我们先考虑一些子问题。
若初始时\(a_i\in \{0,1\}\)，由于不存在\(2\)，一定有\(a_{i+n}=a_i\)，所以直接\(\bmod n\)即可。
若初始时\(a_i\in \{1,2\}\)，由于不存在\(0\)，即不存在没有贡献的情况，所以对于\(a_i=2\)，一定会导致\(a_{i+n}=1,a_{i+n+1}=2\)，观察一下可以发现，此时\(a_{i+n+1}=a_i\)，所以直接\(\bmod (n+1)\)即可。
考虑原问题，由于存在\(0\)，将会导致有些位置没有贡献，那么对于\(a_i=2\)，可能会导致\(a_{i+n}=1,a_{i+n+1}=1\)（即\(a_{i+1}=0\)时）。联系之前的两个问题，当不存在\(2\)时，这种情况下一定会导致\(a_{i+n+1}=0\)；当不存在\(0\)时，这种情况下一定会导致\(a_{i+n+1}=2\)。可是，当\(2,0\)同时存在时，就会导致\(a_{i+n+1}=1\)。
更形象一点地讲，把\(2\)当作石头，把\(1\)当作平地，把\(0\)当作洞，这种情况就是石头调入洞里形成平地的情况。
假设初始数组中第\(i\)个位置是洞，第\(j\)个位置是石头，石头\(j\)会在\(x\)位置与洞\(i\)重合，掉入洞中。又因为将会在所有满足\(p\equiv j\pmod{(n+1)}\)且\(p\le x\)的位置\(p\)出现石头，洞同理。所以\(x\)一定是满足下列同余方程组的最小正整数：
\[\begin{cases} x\equiv i\pmod{n}\\x\equiv j\pmod{(n+1)} \end{cases}\]
这个求解想怎么做怎么做吧...
然后由于会首尾拼接，我们把初始数组想成一个环，显然对于每个洞\(i\)，一定是在环上与\(i\)有向距离最短的石子最终掉落在洞\(i\)。那么我们直接扫两遍，用栈维护当前的石子（第二遍不清空栈，就相当于成了环），每次遇到洞就取出栈顶元素——石头\(j\)（如果栈为空则跳过），算出\(x\)的值，记录\(mat[i]=mat[j]=x\)，一个点若没有\(mat\)值，则记为\(INF\)。
\(mat\)的定义显而易见，\(mat[i]\)表示与\(i\)有向距离最近的石子/洞与\(i\)抵消的位置。
有了\(mat\)以后对于询问就可以\(\mathcal O(1)\)求了，可以根据\(mat[x\bmod n],mat[x\bmod (n+1)]\)与\(x\)的大小关系来计算贡献，注意除了比较\(mat\)和\(x\)的大小外，还需判断初始是否为石子/洞。
代码
1 |
|
