51Nod-1589 移数博弈(链表)（51Nod-1589 移数博弈(链表初始化）

题意

定义一个区间的值为最大值乘次大值（可以一样）。按一定方法构造 n

n 个数，求元素个数大于等于 2

2 的所有区间值总和。

1≤n≤10

7

1≤n≤107

思路

累计区间的值这一类问题，一般的思路是按一定顺序单独计算每个数的贡献。发现从小到大统计，可以满足要求的最值。先按 n

n 个数的顺序构造双链表，然后从小到大依次删点，把要删的点作为次大值，然后分别统计左边、右边的数作最大值的区间个数乘上这些区间的贡献，然后相加即可。先是乘法原理，再是加法原理，具体看代码。

代码

#include<iostream>

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#define FOR(i,x,y) for(int i=(x);i<=(y);i++)

#define DOR(i,x,y) for(int i=(x);i>=(y);i--)

#define del(x) L[R[x]]=L[x],R[L[x]]=R[x]

#define P 1000000007

#define N 10000003

typedef long long LL;

using namespace std;

int a[N],b[N],cnt[N],L[N],R[N];

void counting_sort(int *a,int n)

{ //用计排的原理构造“第几小”到“位置”的索引

FOR(i,1,n)cnt[a[i]]++;

FOR(i,1,N-3)cnt[i]+=cnt[i-1];

DOR(i,n,1)b[cnt[a[i]]--]=i;

return;

}

int main()

{

int n,A,B,p;

LL ans=0;

scanf("%d%d%d%d%d",&n,&a[0],&A,&B,&p);

FOR(i,1,n)a[i]=(int)(((LL)a[i-1]*A+B)%p);

counting_sort(a,n);

a[0]=a[n+1]=0;

R[0]=1;

FOR(i,1,n)L[i]=i-1,R[i]=i+1;

L[n+1]=n;

FOR(i,1,n)

{

int now=b[i]; //l2 l1 now r1 r2

int l1=L[now],r1=R[now],l2=L[l1],r2=R[r1];

(ans+=(LL)a[l1]*a[now]%P*(l1-l2)%P*(r1-now))%=P;//[l2+1,l1] [now,r1-1]

(ans+=(LL)a[r1]*a[now]%P*(r2-r1)%P*(now-l1))%=P;//[l1+1,now] [r1,r2-1]

del(now);

}

printf("%lld\n",ans);

return 0;

}