[JZOJ6247]【NOI2019模拟2019.6.27】C【计数】

Description

n<=200000

Solution

比赛时没做出这道题真的太弟弟了
首先我们从小到大插入数i，考虑B中有多少个区间的最大值为i
恰好出现的次数不太好计算，我们考虑计算最大值小于等于i，再做一个差分即可。

然后直接分成长度在一段内的和长度跨过一段边界的考虑，跨过完整的一段的区间的答案一定是整个序列最大值

分类讨论即可，式子并不难推，有一个地方可以直接暴力计算前缀和。

复杂度O(N)或加上O(MAX(a))

Code

#include 
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fod(i,a,b) for(int i=a;i>=b;--i)
typedef long long LL;
const int mo=1000000007;
const int N=200005;
using namespace std;
int n,a[N],ft[N],sz[N],d[N];
LL ans[N];
int getf(int k)
{return (!ft[k]||ft[k]==k)?k:ft[k]=getf(ft[k]);
}
void merge(int x,int y)
{x=getf(x),y=getf(y);ft[y]=x,sz[x]+=sz[y];
}
bool cmp(int x,int y)
{return (a[x]>n;fo(i,1,n) scanf("%d",&a[i]),ft[i]=i,d[i]=i;sort(d+1,d+n+1,cmp);ans[0]=0;fo(i,1,n) sm[i]=(sm[i-1]+(LL)i*(i+1)/2)%mo;sp[1]=1;fo(i,2,n) sp[i]=(sp[i-2]+(LL)i*(i+1)/2)%mo;calc(1,4);fo(i,1,n-1){int w=d[i];ans[i]=ans[i-1];if(sz[n]&&sz[1]) ans[i]=(ans[i]-calc(sz[getf(n)],sz[getf(1)])+mo)%mo; sz[w]=1;if(sz[w-1]){ans[i]-=sm[sz[getf(w-1)]];merge(w-1,w);}if(sz[w+1]){ans[i]-=sm[sz[getf(w+1)]];merge(w,w+1);}ans[i]=(ans[i]%mo+sm[sz[getf(w)]])%mo;if(sz[n]&&sz[1]) ans[i]=(ans[i]+calc(sz[getf(n)],sz[getf(1)]))%mo; }   LL c=(LL)n*(n+1)/2%mo;ans[n]=c*(c+1)%mo*((mo+1)/2)%mo;LL s1=0;fo(i,1,n) {s1=(s1+(LL)(ans[i]-ans[i-1]+mo)%mo*a[d[i]])%mo;}printf("%lld\n",s1);
}

转载于:https://www.cnblogs.com/BAJimH/p/11123500.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！