题意
初始给了 1 2 两个数
第二步 因为第2个数是2 所以 在序列后面放上2个2 包括他自己之前有的 序列变成 1 2 2
第三步 因为第3个数是2 所以 在序列后面放上2个3 就变成了 1 2 2 3 3
第4步 第4个数为3 所以 在序列后面放上3个4 变成 1 2 2 3 3 4 4 4
以此类推 序列就是 1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8。。。
求的是n的最后出现位置 的最后出现位置， 也就是说 如果 n最后一次出现在第k位 那么 k的最后一次出现在哪里
我们可以知道 如果答案询问的是n 那么我们就可以知道 回答的肯定是 n最后所在的位置的前K项和，可想而知 ！！！比如查询 3 那么就是求前5项的和
但是好像100000000那么多不太如意
在分解
1*1+（2+3）*2 这个答案是3的答案
那么 10呢？
就是 1*1+(2+3)*2+(4+5)*3+(6+7+8)*4+(9+10)*5;
好像知道了 最后要计算的就是 括号里面最大的那个值得为止的上式的和 那么但是我并不知道 后面乘的那个k得有多大 可以使得括号里面的最大值为1000000000，打了一下表发现 500000足够了
于是 用二分 +求和了
#include <iostream> #include <algorithm> #include <string.h> #include <cstdio> using namespace std; typedef long long LL; const int maxn=500005; const LL MOD=1000000007; struct elem{ LL L,R; elem(LL cL=0,LL cR=0) { L=cL; R=cR; } }P[maxn]; int cnt; LL sum[maxn]; int look(LL d) { int L=1,R=cnt-1; int ans=0; while(L<=R){ int mid=(L+R)>>1; if(P[mid].L<=d&&P[mid].R>=d){ ans=mid;break; } if(P[mid].L>d){ R=mid-1; }else{ L=mid+1; } } return ans; } void init() { cnt=1; P[cnt++]=elem(1,1); P[cnt++]=elem(2,3); LL loc=4; for(int i=3; i<=500000; i++) { int d=look(i); P[cnt++]=elem(loc,loc+d-1); loc=loc+d; } sum[0]=0; for(LL i=1 ; i<cnt; i++) { LL nu=P[i].R-P[i].L+1; LL s= (P[i].L+P[i].R)*nu/2; s=(s*i)%MOD; sum[i]=(s+sum[i-1])%MOD; } } int main() { init(); int cas; scanf("%d",&cas); for(int cc=1; cc<=cas; cc++) { LL loc; scanf("%I64d",&loc); LL d=look(loc); LL ans=sum[d-1]; LL s=1LL*(loc-P[d].L+1)*(loc+P[d].L)/2; s=((s%MOD)*d)%MOD; ans=(ans+s)%MOD; printf("%I64d ",ans); } return 0; }