【2022 NOIP 模拟赛 24】求和 做题记录

定义：

$A_i=(1023^i\ mod\ 10^9)\ xor\ (1025^i\ mod\ 10^9)$

求：

$sum=\sum_{i=l_1}^{r_1}\sum_{j=max(i,l_2)}^{r_2}\left \{ max\{A_{i\cdots j}\}-min\{A_{i\cdots j}\} \right \}$

$t$ 组询问。

$1\le t\le 40000,1\le L_1\le R_1\le10^5,1\le L_2\le R_2\le10^5$。

洛谷原题

在线算法，瓶颈在建出 ST 表，时间复杂度 $O(n\log n+q)$，吊打所有奇奇怪怪数据结构做法。

首先有：

$\sum\limits_{l=l_1}^{r_1}\sum\limits_{r=\max(l,l_2)}^{r_2}\{\max\{A_{[l,r]}\}-\min\{A_{[l,r]}\}\}\\ =\sum\limits_{l=l_1}^{r_1}\sum\limits_{r=\max(l,l_2)}^{r_2}\max\{A_{[l,r]}\}-\sum\limits_{l=l_1}^{r_1}\sum\limits_{r=\max(l,l_2)}^{r_2}\min\{A_{[l,r]}\}\\ =\sum\limits_{l=l_1}^{r_1}\sum\limits_{r=\max(l,l_2)}^{r_2}\max\{A_{[l,r]}\}+\sum\limits_{l=l_1}^{r_1}\sum\limits_{r=\max(l,l_2)}^{r_2}\max\{-A_{[l,r]}\}$

那么只需要会求 $\sum\limits_{l=l_1}^{r_1}\sum\limits_{r=\max(l,l_2)}^{r_2}\max\{A_{[l,r]}\}$ 就行了，记 $f(L,R)=\sum\limits_{[l,r]\subseteq [L,R]}\max\{A_{[l,r]}\}$ 并且由于 $\sum\limits_{l=l_1}^{r_1}\sum\limits_{r=\max(l,l_2)}^{r_2}\max\{A_{[l,r]}\}=f(l_1,r_2)-f(l_1,l_2-1)-f(r_1+1,r_2)+f(r_1+1,l_2-1)$，所以只要会求 $f(L,R)$ 就行了。

考虑怎么求解 $f(L,R)$，考虑 $[L,R]$ 中最左边的最大值的位置 $p$，它的地位是无法撼动的，所有包含 $p$ 的区间最大值都是 $A_p$，所以它的贡献为 $(p-L+1)(R-p+1)A_p$。

除去包含 $p$ 的区间后，只剩下 $[l,r]\subseteq [L,p-1]$ 和 $[l,r]\subseteq [p+1,R]$ 的区间了。

考虑求 $[l,r]\subseteq [p+1,R]$ 的贡献，设 $dp_{i,j}$ 为 $r=j,l\in[i,j]$ 的 $[l,r]$ 的贡献，设 $A_0=\infin,pmx_i=\max\limits_{0\le j<i,A_j\ge A_i} j$，那么有转移 $dp_{i,j}=dp_{i,pmx_i}+(j-pmx_i)A_j$，$[l,r]\subseteq [p+1,R]$ 的贡献显然即为 $\sum\limits_{i=p+1}^R dp_{p+1,i}$。

观察到由于 $A_p$ 是 $A_{[L,R]}$ 中的最大值，所以把 $\sum\limits_{i=p+1}^R dp_{p+1,i}=\sum\limits_{i=p+1}^Rdp_{1,i}-dp_{1,p}=-(R-p) dp_{1,p}+\sum\limits_{i=p+1}^Rdp_{1,i}$，那么预处理出 $dp_{1,i}$ 和它的前缀和即可。

$[l,r]\subseteq [L,p-1]$ 的贡献也差不多，倒着求一遍 $dp$ 即可。

用单调栈求 $dp_{1,i}$ 和前缀和的时间复杂度是 $O(n)$ 的，预处理 ST 表的时间复杂度是 $O(n\log n)$ 的，两个东西查询都是 $O(1)$ 的，所以时间复杂度为 $O(n\log n+q)$。

代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

#define fio(name) freopen(name".in","r",stdin),freopen(name".out","w",stdout)

const int S=100005,p=1000000000;

int n,a[S];
int top1,top2,sta1[S],sta2[S];
int pmn[S],pmx[S],smn[S],smx[S];
long long fmn[S],fmx[S],gmn[S],gmx[S];
long long sfmn[S],sfmx[S],sgmn[S],sgmx[S];
int mylog[S],mn[S][25],mx[S][25];

inline int quemn(int l,int r)
{
	int k=mylog[r-l+1];
	return a[mn[l][k]]<a[mn[r-(1<<k)+1][k]]?mn[l][k]:mn[r-(1<<k)+1][k];
}

inline int quemx(int l,int r)
{
	int k=mylog[r-l+1];
	return a[mx[l][k]]>a[mx[r-(1<<k)+1][k]]?mx[l][k]:mx[r-(1<<k)+1][k];
}

inline void slove(int l,int r,long long &mns,long long &mxs,int p)
{
	int mnp=quemn(l,r);
	mns+=1ll*p*a[mnp]*(mnp-l+1)*(r-mnp+1);
	mns+=1ll*p*((sgmn[mnp-1]-sgmn[l-1]-gmn[mnp]*(mnp-l))+(sfmn[r]-sfmn[mnp]-fmn[mnp]*(r-mnp)));
	int mxp=quemx(l,r);
	mxs+=1ll*p*a[mxp]*(mxp-l+1)*(r-mxp+1);
	mxs+=1ll*p*((sgmx[mxp-1]-sgmx[l-1]-gmx[mxp]*(mxp-l))+(sfmx[r]-sfmx[mxp]-fmx[mxp]*(r-mxp)));
}

int main()
{
	fio("c");
	n=100000;
	for(int i=1,pw1=1023,pw2=1025;i<=n;i++)
	{
		a[i]=pw1^pw2;
		pw1=1ll*pw1*1023%p,pw2=1ll*pw2*1025%p;
	}
	for(int i=1;i<=n;i++)
	{
		while(top1>0&&a[sta1[top1]]>a[i]) top1--;
		while(top2>0&&a[sta2[top2]]<a[i]) top2--;
		pmn[i]=sta1[top1],pmx[i]=sta2[top2];
		sta1[++top1]=sta2[++top2]=i;
	}
	sta1[top1=0]=sta2[top2=0]=n+1;
	for(int i=n;i>=1;i--)
	{
		while(top1>0&&a[sta1[top1]]>a[i]) top1--;
		while(top2>0&&a[sta2[top2]]<a[i]) top2--;
		smn[i]=sta1[top1],smx[i]=sta2[top2];
		sta1[++top1]=sta2[++top2]=i;
	}
	for(int i=1;i<=n;i++) fmn[i]=fmn[pmn[i]]+1ll*a[i]*(i-pmn[i]),fmx[i]=fmx[pmx[i]]+1ll*a[i]*(i-pmx[i]);
	for(int i=n;i>=1;i--) gmn[i]=gmn[smn[i]]+1ll*a[i]*(smn[i]-i),gmx[i]=gmx[smx[i]]+1ll*a[i]*(smx[i]-i);
	for(int i=1;i<=n;i++) sfmn[i]=sfmn[i-1]+fmn[i],sfmx[i]=sfmx[i-1]+fmx[i];
	for(int i=1;i<=n;i++) sgmn[i]=sgmn[i-1]+gmn[i],sgmx[i]=sgmx[i-1]+gmx[i];
	mylog[0]=-1;
	for(int i=1;i<=n;i++) mylog[i]=mylog[i>>1]+1,mn[i][0]=mx[i][0]=i;
	for(int j=1;j<=mylog[n];j++)
	{
		for(int i=1;i<=n-(1<<j)+1;i++)
		{
			mn[i][j]=a[mn[i][j-1]]<a[mn[i+(1<<j-1)][j-1]]?mn[i][j-1]:mn[i+(1<<j-1)][j-1];
			mx[i][j]=a[mx[i][j-1]]>a[mx[i+(1<<j-1)][j-1]]?mx[i][j-1]:mx[i+(1<<j-1)][j-1];
		}
	}
	int q;
	scanf("%d",&q);
	while(q--)
	{
		int l1,r1,l2,r2;
		scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
		if(l1>r2)
		{
			puts("0");
			continue;
		}
		long long mns=0,mxs=0;
		slove(l1,r2,mns,mxs,1);
		if(l1<l2) slove(l1,l2-1,mns,mxs,-1);
		if(r1<r2) slove(r1+1,r2,mns,mxs,-1);
		if(r1<l2-1) slove(r1+1,l2-1,mns,mxs,1);
		printf("%lld\n",mxs-mns);
	}
	return 0;
}