(Problem)
有(T)组数据，对于每组数据：
给你一个(n)和一个长度为(n)的数组(a[])，其中的(a[i])属于({n,n+1,n-1})。
而对于任意的(i>n)，(a[i]=sum [i-j<=a[j]])
然后有(Q)次询问，每次询问给你(x)，求(a[x])。
(Solution)
首先考虑暴力，显然可以用差分做到线性解决。
把({n-1,n,n+1})看作({0,1,2})。
考虑观察法找规律。
考虑将每(n)个数看成一行。
则对于第(i)行第(j)个，(a[i][j]=[a[i-1][j]>=1]+[a[i-1][j-1]==2])
也就是说，(0)和(1)相对于列不变，而(2)会不停向右下一格移动。直到填了一个(0)以后就消失了。
那么我们就可以先求出对于第一行的(0)和(2)，求出(0)被(2)填充和(2)填充(0)的时间。
那么我们对于每个询问(x)，看一下对应在第一行的那一列是否为(0)和是否被填充。
若是(0)且被填充或者为(1)或为(2)，则看一下(t=(x-1)%(n+1)+1)的位置（我这里将下标设为([1,n])）是(2)与否。
对于特殊的(t=n+1)则肯定不是(2)。
上述过程注意细节即可。
(Code)
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 1100010
#define ll long long
#define mem(x, a) memset(x, a, sizeof x)
#define mpy(x, y) memcpy(x, y, sizeof x)
#define fo(x, a, b) for (int x = (a); x <= (b); x++)
#define fd(x, a, b) for (int x = (a); x >= (b); x--)
using namespace std;
int T, n, Q, a[N << 2], cf[N << 2];
int b[N], z[N], fro[N];
ll q[N], sum = 0;
inline int read() {
int x = 0, f = 0; char c = getchar();
while (c < '0' || c > '9') f = (c == '-') ? 1 : f, c = getchar();
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return f ? -x : x;
}
int main() {
freopen("way.in", "r", stdin);
freopen("way.out", "w", stdout);
T = read();
while (T--) {
n = read(), Q = read();
mem(a, 0), mem(cf, 0);
bool tag = 0, label = 0;
sum = a[1] = read();
if (a[1] == n + 1) label = 1;
fo(i, 2, n) {
a[i] = read(); sum += a[i];
if (a[i] != a[i - 1]) tag = 1;
if (a[i] == n + 1) label = 1;
}
if (! tag) {
ll x;
if (a[1] <= n) {
while (Q--) {scanf("%lld", &x); printf("%d ", a[x % n + 1]);}
printf("
");
} else {
while (Q--) {
scanf("%lld", &x); x++;
if (x % (n + 1) == 0) printf("%d ", n); else printf("%d ", n + 1);
} printf("
");
} continue;
}
if (! label) {
ll x;
while (Q--) {scanf("%lld", &x); printf("%d ", a[x % n + 1]);}
printf("
"); continue;
}
fo(i, 1, Q) scanf("%lld", &q[i]), q[i]++;
mem(fro, 0);
z[0] = 0;
fo(j, 0, 2) fo(i, 1, n) {
if (a[i] == n + 1 && j == 0) z[++z[0]] = i;
if (a[i] == n - 1 && z[0] && ! fro[i])
fro[i] = fro[z[z[0]]] = (i + n - z[z[0]]) % n, z[0]--;
}
fo(i, 1, Q) {
// if (i == 2798) return 0 & printf("%lld
", q[i]);
if (q[i] <= n) printf("%d ", a[q[i]]);
else {
ll cs = (q[i] - 1) / n;
int x = (q[i] - 1) % n + 1; int yuan_x = x;
if (a[x] == n - 1 && (! fro[x] || fro[x] > cs || (fro[x] == cs && cs >= x)))
{printf("%d ", n - 1); continue;}
// x = (x + n + 1 - cs % (n + 1) - 1) % (n + 1) + 1;
x = (q[i] - 1) % (n + 1) + 1;
// 以上两种都可以
if (x == n + 1) printf("%d ", n);
else if (a[x] == n + 1 && (! fro[x] || fro[x] > cs || (fro[x] == cs && cs >= yuan_x))) printf("%d ", n + 1);
else printf("%d ", n);
}
}
printf("
");
}
return 0;
}