「HNOI2016」序列

传送门

Description

有 \(q\) 个询问，每个询问给定两个数\(l\) 和\(r\)，求 \(a[l:r]\) 的不同子序列的最小值之和

Solution

校内模拟赛用了这道题，但是莫队只能拿\(80\)分，正解是猫树

当然还是莫队啦

考虑一个数加入时的贡献，就是以它为端点的区间的贡献

发现可以将现有的区间分成一段一段的，每段的最小值不同

这个可以用单调栈\(+\)倍增解决

于是就有了\(O(n\sqrt n\log n)\)的做法

但是显然过不了原题

所以想办法把\(\log\)去掉

以右端点为例，令\(f[i]\)表示\(a_i\)对区间\([1,i-1]\)的贡献

发现答案可以看成是\(f[i]-f[k],(k\leq i)\)然后再加上\(k\)以后的贡献

但是，这里的\(k\)得满足它是端点之一，且它往左的贡献很好算

那是什么？就是区间最小值啦，它往左的贡献就是\(a[k]*(k-nowl+1)\)

所以可以先预处理所有的\(f[i]\)，用\(RMQ\)算法\(O(1)\)求出区间最小值就行了

复杂度\(O(n\sqrt n)\)

附上不能看的代码

Code

#include<bits/stdc++.h>

#define ll long long

#define db double

#define dbg1(x) cerr<<#x<<"="<<(x)<<" "

#define dbg2(x) cerr<<#x<<"="<<(x)<<"\n"

#define dbg3(x) cerr<<#x<<"\n"

#define int ll

using namespace std;

inline int read()

{

	int f=1,x=0;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

	return x*f;

}

const int MN=1e5+5,Mod=1e9+7;

int A,B,C,P;

ll lastAns=0;

inline int rnd(){return A=(A*B+(C^(int)(lastAns&0x7fffffffll))%P)%P;}

int n,q,l,r,a[MN];

bool f1,f2;

namespace solve1

{

	int L[MN],R[MN],st[MN],top;

	void Main()

	{

		int i;

		st[top=0]=0;

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

		{

			while(top&&a[st[top]]>=a[i]) --top;

			L[i]=st[top]+1;

			st[++top]=i;

		}

		st[top=0]=n+1;

		for(i=n;i;--i)

		{

			while(top&&a[st[top]]>a[i]) --top;

			R[i]=st[top]-1;

			st[++top]=i;

		}

		while(q--)

		{

			l=read(),r=read();

			ll ans=0ll;

			for(i=l;i<=r;++i)

				ans+=1ll*a[i]*1ll*(min(r,R[i])-i+1)*1ll*(i-max(l,L[i])+1);

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

		}

	}

}

ll suf1[MN],suf2[MN];

void init()

{

	int i;suf1[n+1]=suf2[n+1]=0ll;

	for(i=n;i;--i)

		suf1[i]=suf1[i+1]+1ll*a[i]*(n-i+1),

		suf2[i]=suf2[i+1]+a[i];

}

ll cal(int x,int y){return suf1[x]-suf1[y+1]-1ll*(suf2[x]-suf2[y+1])*1ll*(n-y);}

struct Ques{int l,r,id;}_[MN];int tt;

namespace solve2

{

	int Bl,bel[MN],nowl,nowr;

	ll ans[MN],Sum,nowans;

	ll s1[20][MN],s2[20][MN],p1[20][MN],p2[20][MN],f[MN],g[MN];

	bool cmp(Ques x,Ques y)

	{

		return bel[x.l]!=bel[y.l]?bel[x.l]<bel[y.l]

			:(bel[x.l]&1?x.r<y.r:x.r>y.r);

	}

	int st[MN],top;

	ll cal(int x,bool ty)

	{

		int tmp=0;

		if(!ty)

		{

			for(int i=17;~i;--i)

				if(s1[i][x]==nowr) return tmp+s2[i][x];

				else if(s1[i][x]<nowr)tmp+=s2[i][x],x=s1[i][x]+1;

			return tmp+1ll*a[x]*(nowr-x+1);

		}

		else

		{

			for(int i=17;~i;--i)

				if(p1[i][x]==nowl) return tmp+p2[i][x];

				else if(p1[i][x]>nowl)tmp+=p2[i][x],x=p1[i][x]-1;

			return tmp+1ll*a[x]*(x-nowl+1);

		}

	}

	int Log[MN],mi[20][MN];

	int cmp_(int x,int y){return a[x]<a[y]?x:y;}

	int gmin(int x,int y){int og=Log[y-x+1];return cmp_(mi[og][x],mi[og][y-(1<<og)+1]);}

	void Init()

	{

		int i,j;

		for(i=2;i<=n;++i) Log[i]=Log[i>>1]+1;

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

		for(j=1;j<18;++j)for(i=1;i<=n;++i)if(i-1+(1<<j)<=n)mi[j][i]=cmp_(mi[j-1][i],mi[j-1][i+(1<<j-1)]);

		st[top=0]=0;

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

		{

			while(top&&a[st[top]]>=a[i]) --top;

			p1[0][i]=st[top]+1;

			p2[0][i]=1ll*(i-p1[0][i]+1)*a[i];

			st[++top]=i;

		}

		st[top=0]=n+1;

		for(i=n;i;--i)

		{

			while(top&&a[st[top]]>a[i]) --top;

			s1[0][i]=st[top]-1;

			s2[0][i]=1ll*(s1[0][i]-i+1)*a[i];

			st[++top]=i;

		}

		for(i=1;i<18;++i)

			for(j=1;j<=n;++j)

			{

				if(s1[i-1][j]>=n) s1[i][j]=n+1;

				else s1[i][j]=s1[i-1][s1[i-1][j]+1],

					 s2[i][j]=s2[i-1][j]+s2[i-1][s1[i-1][j]+1];

				if(p1[i-1][j]<=1) p1[i][j]=0;

				else p1[i][j]=p1[i-1][p1[i-1][j]-1],

				     p2[i][j]=p2[i-1][j]+p2[i-1][p1[i-1][j]-1];

			}

		nowl=1;nowr=n;

		for(i=1;i<=n;++i) f[i]=cal(i,1),g[i]=cal(i,0);

	}

	ll Cal(int x,int ty)

	{

		ll tmp=0ll;

		if(ty)

		{

			int pos=gmin(nowl,x);

			tmp=f[x]-f[gmin(nowl,x)];

			tmp+=1ll*a[pos]*(pos-nowl+1);

		}

		else

		{

			int pos=gmin(x,nowr);

			tmp=g[x]-g[gmin(x,nowr)];

			tmp+=1ll*a[pos]*(nowr-pos+1);

		}

		return tmp;

	}

	void Add(int x,bool ty){nowans+=Cal(x,ty);}

	void Del(int x,bool ty){nowans-=Cal(x,ty);}

	void Main()

	{

		Init();Bl=sqrt((db)(n));

		for(int i=1;i<=n;++i)bel[i]=(i+Bl-1)/Bl;

		std::sort(_+1,_+tt+1,cmp);

		nowl=1,nowr=0;Sum=0;nowans=0;

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

		{

			while(nowr<_[i].r) Add(++nowr,1);

			while(nowl>_[i].l) Add(--nowl,0);

			while(nowr>_[i].r) Del(nowr--,1);

			while(nowl<_[i].l) Del(nowl++,0);

			if(f2) (Sum+=nowans)%=Mod;

			else ans[_[i].id]=nowans;

		}

		if(f2) printf("%lld\n",Sum);

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

	}

}

signed main()

{

	n=read();q=read();

	if(f2) A=read(),B=read(),C=read(),P=read();

	int i;bool c1=1,c2=1;a[0]=-Mod;

	for(i=1;i<=n;++i) a[i]=read(),c1&=(a[i]==a[1]),c2&=(a[i]>a[i-1]);

	if(c2) init();

	if(n*q<=Mod&&!f1&&!f2) {solve1::Main();return 0;}

	while(q--)

	{

		if(f2)

		{

			l=rnd()%n+1;r=rnd()%n+1;

			if(l>r)swap(l,r);

		}

		else if(f1)

		{

			l=read();r=read();

			l=((l+lastAns)%n+n)%n+1;

			r=((r+lastAns)%n+n)%n+1;

			if(l>r)swap(l,r);

		}

		else l=read(),r=read();

		if(c1) printf("%lld\n",lastAns=1ll*(1ll*(r-l+1)*1ll*(r-l+2)/2)*1ll*a[1]);

		else if(c2) printf("%lld\n",lastAns=cal(l,r));

		else _[++tt].l=l,_[tt].r=r,_[tt].id=tt;

	}

	if(!c1&&!c2){solve2::Main();return 0;}

	return 0;

}

Blog来自PaperCloud，未经允许，请勿转载，TKS！

巴特西

「HNOI2016」序列

传送门

Description

Solution

Code

最新文章

热门文章