luoguP3246 [HNOI2016]序列

题意

这题很难想到用莫队去做，因为第一印象是这个没办法O(1)移动指针。

考虑从\([l,r]\)移动到\([l,r+1]\) (从\([l,r]\)移动到\([l-1,r]\)同理)。

我们用ST表\(O(1)\)找到\([l,r+1]\)的最小值的位置\(mid\)，考虑新加入的r+1会产生哪些贡献：显然是很多以\(r+1\)为右端点的子序列的最小值之和。

对于左端点分类讨论:

左端点在\([l,mid]\)：这里的子序列最小值都为\(a[mid]\),因此贡献为\((mid-l+1)*a[mid]\)。

左端点在\([mid+1,r+1]\):这个似乎没法处理。

于是要考虑左端点在\([mid+1,r+1]\)如何处理：

正解是用前缀和处理的，很难想到。

\(R[i]\)表示\([1,i]\)这段区间的答案，\(pre[i]\)表示\(i\)左边第一个比它小的数的位置，那么就会有：

\(R_i=R_{pre_i}+(i-pre_i)*a_i\)

发现对于左端点在\([mid+1,r+1]\)的是可以用前缀和相减的：

\(R[r+1]-R[mid]\)。

至于为什么左端点在\([l,mid]\)不能用前缀和相减，主要是\(R[i]\)不一定从\(pre[i]\)转移，因为有\(l\)的限制。

其他同理。

注意个细节。

code:

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=100010;

int n,m,t,top,nowl,nowr;

int pre[maxn],nxt[maxn],pos[maxn];

ll nowans;

ll a[maxn],s[maxn],ans[maxn],L[maxn],R[maxn];

ll f[maxn][20];

struct Query

{

	int l,r,id;

}qr[maxn];

inline bool cmp(Query x,Query y){return pos[x.l]==pos[y.l]?x.r<y.r:pos[x.l]<pos[y.l];}

inline void ST()

{

	for(int i=1;i<=n;i++)f[i][0]=i;

	for(int j=1;j<=18;j++)

		for(int i=1;i+(1<<j)-1<=n;i++)

			f[i][j]=a[f[i][j-1]]<a[f[i+(1<<(j-1))][j-1]]?f[i][j-1]:f[i+(1<<(j-1))][j-1];

}

inline int query(int l,int r)

{

	int t=(int)log2(r-l+1);

	return a[f[l][t]]<a[f[r-(1<<t)+1][t]]?f[l][t]:f[r-(1<<t)+1][t];

}

inline void addl(int x,int k)

{

	//if(nowl>nowr)puts("!!!");

	//printf("nowl::%d nowr::%d x::%d\n",nowl,nowr,x);

	int mid=query(nowl,nowr);

	//printf("%d %d %d\n",nowl,nowr,a[mid]);

	nowans+=1LL*(L[x]-L[mid]+1LL*(nowr-mid+1)*a[mid])*k;

}

inline void addr(int x,int k)

{

	//if(nowl>nowr)puts("!!!");

	//printf("nowl::%d nowr::%d x::%d\n",nowl,nowr,x);

	int mid=query(nowl,nowr);

	//printf("%d %d %d\n",nowl,nowr,a[mid]);

	nowans+=1LL*(R[x]-R[mid]+1LL*(mid-nowl+1)*a[mid])*k;

}

signed main()

{

	//freopen("test.in","r",stdin);

	//freopen("test.out","w",stdout);

	scanf("%d%d",&n,&m);t=sqrt(n);a[0]=844828908;

	for(int i=1;i<=n;i++)scanf("%lld",&a[i]),pos[i]=(i-1)/t+1;

	for(int i=1;i<=m;i++)scanf("%d%d",&qr[i].l,&qr[i].r),qr[i].id=i;

	sort(qr+1,qr+m+1,cmp);

	ST();

	for(int i=1;i<=n;i++)

	{

		while(top&&a[s[top]]>a[i])nxt[s[top]]=i,top--;

		pre[i]=s[top];s[++top]=i;

	}

	for(int i=1;i<=top;i++)nxt[s[i]]=n+1;

	for(int i=1;i<=n;i++)R[i]=R[pre[i]]+1LL*a[i]*(i-pre[i]);

	for(int i=n;i;i--)L[i]=L[nxt[i]]+1LL*a[i]*(nxt[i]-i);

	nowans=a[nowl=nowr=1];

	//for(int i=1;i<=n;i++)printf("%lld ",pos[i]);

	//puts("");

	for(int i=1;i<=m;i++)

	{

		while(nowr<qr[i].r)nowr++,addr(nowr,1);

		while(nowl>qr[i].l)nowl--,addl(nowl,1);

		while(nowr>qr[i].r)addr(nowr,-1),nowr--;

		while(nowl<qr[i].l)addl(nowl,-1),nowl++;

		ans[qr[i].id]=nowans;

	}

	for(int i=1;i<=m;i++)printf("%lld\n",ans[i]);

	return 0;

}

巴特西

luoguP3246 [HNOI2016]序列

题意

最新文章

热门文章