题目链接：https://ac.nowcoder.com/acm/contest/634/B
这题是我喜欢的类型——没有复杂的数据结构和算法，只需认真思考，我行，你也行。
思路：没有复杂高深的算法，只需对暴力法优化。
分析：
一.拿到题目，先看数据范围，分析时间复杂度
n的范围是2e7，似乎连O(n)的算法都可能TLE。不过注意到，数据的读入就需要O(n)，所以O(n)的算法肯定是可行的。
二.先思考Brute force
这题的Brute force做法显而易见：模拟。双重循环。外循环枚举每个线段i，内循环计算从线段i的0位置到线段n的步数。求和即得答案。不过，在没有优化的情况下，时间复杂度是O(n^2)，显然是无法AC的。
三.思考优化方法
既然Brute force是没办法AC的，而这题又似乎也没办法用什么高大上的算法做，我们就只能思考如何优化Brute force。下面我就介绍一下我的思考过程。
1.哪里可以优化？
a.递推是否可行？
由于我们横下心不用什么数据结构和算法，所以优化的方法就比较少了。这一题看上去似乎可以递推，那我们就认真分析一下。
我们模仿数学上的证明过程，先来设置一个引理：当能在O(1)的时间得到从线段i的0位置往下走，第一次被卡住的线段编号，那么我们就能在O(n)的时间用递推得出答案。
很玄学对吧。没关系，我们慢慢证明。令kz[i]（卡住ka zhu)表示从线段i的0位置往下走，第一次被卡住的线段编号，根据引理，我们已经将kz数组求出来了。那么，我们就可以递推了。
我们注意到题目中的条件：如果第i+1条线段长度不到j+1，那么就会回到第i条线段的0位置，然后继续跳。也就是说，从第i条线段的0位置往下跳，跳到kz[i]被卡住了，需要返回kz[i]-1行的0位置继续跳。那么从第i条的0位置跳到第n条线段的代价比从kz[i-1]行的0位置跳到第n行的代价多出了kz[i]-i，这个是可以在O(1)的时间求出来的。所以，第i行的代价可以转化为第kz[i-1]行的代价，只不过从第kx[i-1]行的0位置到第n行的代价在求的时候要加倍。我们可以用一个cnt数组来记录遍历到这一行时有几个点同时往下走。所以我们只需一次遍历，就能求出来答案，时间复杂度为O(n)。
理解不了？没关系，配合下面的图，理解起来就方便多了。
b.引理如何优化？
虽然推出来了上一步里的递推关系，但是别高兴的太早：上一步的成立是建立在引理成立的基础上。也就是说，我们同样需要在O(n)的时间里求出kz数组。这一步的方法和证明就比较有难度了，希望各位能耐心看下去。
对于这张图，我们要证明三个结论：
（1）对于任意m，i<m<j，kz[m]>=j;
（2）对于任意k，i<k<=j-a[j]-1，kz[k]=j;
（3）对于任意p，j-a[i]<=p<j，kz[p]>j;
下面证明：
（1）由于kz[i]表示i第一次需要回退一行的编号，所以对于任意m属于(i,j)，a[m]>=m-i;所以对于任意t属于(i,m)，a[m]>m-t;所以t肯定不被m卡住。对于所以的m，m不被m到j-1的行卡住，即kz[m]>=j。证毕。
（2）由于kz[i]=j，则a[j]<j-i;对于任意k属于（i,j-a[j]-1]]，a[j]<j-k，所以kz[k]<=j，又由（1）得知kz[k]>j-1，所以kz[k]=j;
（3）由于a[j]>j-p，又由（1）知，kz[p]>j，所以kz[p]>j;
现在，证明完毕，我也可以介绍我的做法了。
首先，我们将kz数组赋值为无穷大，从i=nxt到n遍历一遍，nxt初始为1，维护下次开始遍历的位置。每次从nxt开始往下找到第一个会卡住的位置j。则从任意k属于[nxt,j-a[j]-1]，kz[k]=j;nxt=j-a[j];
然后，再一次倒序遍历，若kz[i]!=无穷大，则将所有i到下一个kz[j]!=无穷大的j，任意k属于[j,i]，kz[k]=kz[i];即可得kz数组。
至此，两个优化均完成，且总时间复杂度为O(n)，最后提醒的是，注意用long long int 记录答案。于是，AC！
代码如下：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=2e7+5;
const int INF=0x3f3f3f3f;
unsigned int SA, SB, SC,a[maxn];
int mod,n;
int kz[maxn],cnt[maxn];
ll ans=0;
unsigned int Rand() {
SA ^= SA << 16;
SA ^= SA >> 5;
SA ^= SA << 1;
unsigned int t = SA;
SA = SB;
SB = SC;
SC ^= t ^ SA;
return SC;
}
int main() {
ios::sync_with_stdio(false);
freopen("小y的线段.in","r",stdin);
cin>>n>>mod>>SA>>SB>>SC;
for(int i = 1; i <= n; ++i)
{
a[i] = Rand() % mod + 1;
kz[i]=-INF;
cnt[i]=1;
}
int i=1;
a[n+1]=0;
bool needxg=true;
int nxt=2;
while(i<=n)
{
int j=nxt;
for(;j<=n+1;j++)
{
if(j-i>a[j])//i kazhu
{
kz[j-a[j]-1]=j;
i=j-a[j];
nxt=j+1;
break;
}
}
}
int temp;
for(int j=n;j>=1;j--)
{
if(kz[j]!=-INF)
temp=kz[j];
else
kz[j]=temp;
}
for(int i=1;i<=n;i++)
{
if(kz[i]>n) continue;
ans+=((ll)kz[i]-i)*cnt[i];
cnt[kz[i]-1]+=cnt[i];
}
for(int i=1;i<=n;i++){
if(kz[i]>n){
ans+=(ll)(n-i)*cnt[i];
}
}
cout<<ans<<endl;
return 0;
}
