题目大意：
由1开始不断往数组中添加数
就是按照当前所在位置所在的数表示的个数添加这个数目的数
1 2 2 3 3 后面因为要填4，而4号位置为3，说明之后要填3个4
问题就是给定一个n，找到n出现的最后位置p，再找p出现的最后位置即可
这里可以考虑先找到g[i]表示 i 连续出现了多少次
这里想一下的话，因为g[i] 相当于 i 位置出现的数
所以g[i]也满足这个序列
令f[i] 表示 i 出现的最后位置，也就是1~i的总个数
后面去计算g[i]的时候就可以考虑的是找到第 i 个位置在那个f[]的区间内 ， 如果f[k-1]< i <= f[k]
那么说明此时 g[i] = k
那么就可以logn的复杂度计算g[n]了
要计算最后的答案，要考虑的是，给定的n，找到最后出现的p，中间长度 p = g[1]+g[2]....+g[p]
然后再找对应的ans ，那么每次增加的g[i]，就会让整个序列 的长度增加 i*g[i]
i*g[i] 可以理解为的是，长度为i的数量有g[i]个， 所以总长度是i*g[i]
所以ans = sigma(i*g[i]) i<=n
那么对于n <= 1e9
那么大致计算一下会发现f[500000]>1e9
所以g[n]<500000只要暴力求出前500000的g[] , f[]
那么答案计算前，先找到g[n]是多少
g[n]= lower_bound(f+1 , f+N+1 , n)-f
然后说明[1 , g[n]-1]这一段区间内的所有长度都被用到了
所以之前预处理这个长度的前缀和 sum[]
对于每一个长度 i ，他出现的次数都是 f[i]-f[i-1]
sigma(n*g[n]) f[i-1]<n<=f[i] -> g[n] = i
那么答案就是 i*等差数列了，记得取模(⊙o⊙)哦
然后（g[n]-1 , g[n]]这一段只要枚举 （g[n]-1 , n] 就可以了
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
#define M 26
#define N 500000
#define ull unsigned long long
#define ll long long
const int MOD = ;
int f[N+] , g[N+] , cnt[N+];
ll sum[N+]; int Hash(int v)
{
return lower_bound(f+ , f+N+ , v)-f;
} void init()
{
g[] = , f[] = ;
g[] = , f[] = ;
for(int i= ; i<=N ; i++){
g[i] = lower_bound(f+ , f+i , i)-f;
f[i] = f[i-]+g[i];
}
// for(int i=1 ;i<=100 ; i++)
// cout<<i<<" "<<g[i]<<" "<<f[i]<<endl;
// cout<<f[N]<<endl; sum[] = ;
for(int i= ; i<=N ; i++){
sum[i] = sum[i-]+(ll)(f[i-]++f[i])*(f[i]-f[i-])/ % MOD * (ll)i % MOD;
// if(i<=10) cout<<"sum: "<<i<<" "<<sum[i]<<endl;
}
}
int main() {
// freopen("a.in" , "r" , stdin);
// freopen("out.txt" , "w" , stdout); init();
int T , n;
scanf("%d" , &T);
while(T--){
scanf("%d" , &n);
int pos = Hash(n);
ll ret = sum[pos-];
for(int i=f[pos-]+ ; i<=n ; i++) //这个区间每个长度都为pos
{
ret = (ret+(ll)i*pos)%MOD;
}
printf("%I64d\n" , ret);
}
return ;
}