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
",ans);

return 0;

}

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！