【纪中集训2019.3.11】Cubelia

题目：

描述

给出长度为$n$的数组$a$和$q$个询问$l,r$。

求区间$[l,r]$的所有子区间的前缀和的最大值之和；

范围：

$n \le 2 \times 10^5 , q \le 10^7 $；

数据给出的$S,A,B,P$参数随机生成，附加文件给出数据生成器；

保证任意一个连续子序列的最大前缀和不超过$10^6$ ;

题解：

Part1
$[1,l-1]$的$a_{i}$对区间$[l,r]$的前缀和的大小是没用影响的，所以直接算答案就是；

\[记sum_{i} = \sum_{j=1}^{i}a_{i} \\
\begin{align} ans_{l,r} = \sum_{i=l}^{r}\sum_{j=i}^{r} max^{j}_{k=i}\{sum_{k}\} - \sum_{i=l-1}^{r-1} sum_{i}(r-i) \end{align}
\]

考虑如何求区间连续子序列最大值之和；
$kczno1$的做法： https://loj.ac/article/489
一个奇葩做法：
对$sum$建出笛卡尔树，考虑一个节点的有效区间是$[l_{i},r_{i}]$；
预先处理出每个点的贡献:$s_{i} = (i - l_{i}+1) \ (r_{i} - i + 1)$ ;
考虑直接求$\sum_{i=l}^{r}s_{i}$多算了什么，多算的部分其实就是$l_{i}$超出$l$或者$r_{i}$$超出$r$的情况；
记$u为l的祖先且u>l，v为r的祖先且v<r ， w = lca(l,r)$;
多算的部分就是：$\sum_{u=l}^{u<w} (l-l_{u})(r_{u}-u+1) + \sum_{v=r}^{v>w} (r-r_{v})(v-l_{v}+1) $
这个式子可以在笛卡尔的左树和右树上处理一下前缀；
注意在$w$的时候（也就是区间最值的位置）$u$和$v$都会超出，特判一下即可；
Part2 $\pm rmq$
标算需要一个$O(1)$的$rmq$ ，(我没写这个，卡一卡常数也可以过的);
区间最值问题可以通过笛卡尔树转化成$lca$;
注意到$lca$的$rmq$相邻的值相差为$1或-1$
对序列分块令分块大小$B = \frac{log \ n}{2}$，差分后$2^B B^2$处理所有本质不同的块的区间最值的位置；
对$\frac{n}{B}$个块做$rmq$, 整块直接$O(1)$查询rmq$，散块调用预处理的块内最值；

复杂度是：$O(\sqrt{n}log^2n \ + \ n ) = O(n)$ ；

#include <bits/stdc++.h>

#define ll long long

#define mod 998244353

#define inf 1e18

#define il inline

#define rg register

using namespace std;

inline int R() {

    int rt = 0;

    char ch = getchar();

    bool isn = false;

    for (; ch < '0' || ch > '9'; ch = getchar()) isn = ch == '-' ? true : isn;

    for (; ch >= '0' && ch <= '9'; ch = getchar()) rt = rt * 10 + ch - '0';

    return isn ? -rt : rt;

}

const int N=2000010;

ll a[2000007];

int n, q, ans;

int S, A, B, P, tp;

long long lastans;

inline int Rand() {

    S = (S * A % P + (B ^ (tp * lastans))) % P;

    S = S < 0 ? -S : S;

    return S;

}

int f[N][21],bin[21],rt,lg[N],le[N],ri[N],ls[N],rs[N];

ll fl[N],Ls1[N],Ls2[N],fr[N],Rs1[N],Rs2[N];

ll S1[N],S2[N],s[N];

int sta[N],top;

il int Max(int x,int y){

	if(a[x]==a[y])return x>y?x:y;

	return a[x]>a[y]?x:y;

}//

il int ask(int x,int y){

	int t = lg[y - x + 1];

	return Max(f[x][t], f[y-bin[t]+1][t]);

}//

il void dfs1(int k){

	le[k]=ri[k]=k;

	if(ls[k])dfs1(ls[k]),le[k]=le[ls[k]];

	if(rs[k])dfs1(rs[k]),ri[k]=ri[rs[k]];

}

il void dfs2(int k){

	s[k] = (ll)(k - le[k] + 1)*(ri[k] - k + 1)*a[k];

	int t = fl[k] ; ll x = a[k]*(k-le[k]+1);

	Ls1[k] = Ls1[t] + x;

	Ls2[k] = Ls2[t] + x*ri[k];

	//

	t = fr[k]; x = a[k]*(ri[k]-k+1);

	Rs1[k] = Rs1[t] + x;

	Rs2[k] = Rs2[t] + x*le[k];

	//

	if(ls[k]){

		fr[ls[k]]=k;

		fl[ls[k]]=fl[k];

		dfs2(ls[k]);

	}

	if(rs[k]){

		fl[rs[k]]=k;

		fr[rs[k]]=fr[k];

		dfs2(rs[k]);

	}

}//

il void pre_solve(){

	for(rg int i=bin[0]=1;i<=20;++i)bin[i]=bin[i-1]<<1;

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

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

		S1[i] = S1[i-1] + a[i];

		S2[i] = S2[i-1] + a[i]*i;

	}

	lg[0]=-1;a[0]=-inf;

	for(rg int i=1;i<=n;++i)f[i][0]=i,lg[i]=lg[i>>1]+1;

	for(rg int i=1;i<=20;++i)

	for(rg int j=1;j+bin[i]-1<=n;++j){

		f[j][i] = Max(f[j][i-1], f[j+bin[i-1]][i-1]);

	}

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

		while(top&&Max(sta[top],i)==i)ls[i]=sta[top--];

		if(top)rs[sta[top]]=i;

		sta[++top]=i;

	}

	rt = sta[1];

	dfs1(rt);

	dfs2(rt);

	for(rg int i=1;i<=n;++i)s[i]+=s[i-1];

}//

il ll cal1(int l,int r){

	l = max(2, l);

	return r * (S1[r-1] - S1[l-2]) - (S2[r-1] - S2[l-2]) ;

}//

il ll cal2(int l,int r){

	int t = ask(l,r);

	ll re = (s[r]-s[l-1]) - (ll)(t - le[t] + 1) * (ri[t] - t + 1) * a[t] + (ll)(t - l + 1) * (r - t + 1) * a[t] ;

	re -= l * (Rs1[l] - Rs1[t]) - (Rs2[l] - Rs2[t]);

	re -= (Ls2[r] - Ls2[t]) - r * (Ls1[r] - Ls1[t]);

	return re;

}//

il long long solve(int l, int r){

	return cal2(l, r)-cal1(l, r);

}//

int main() {

    freopen("cubelia.in", "r", stdin);

    freopen("cubelia.out", "w", stdout);

    n=R(),q=R();

    for(rg int i=1;i<=n;++i)a[i]=R();

    S=R(),A=R(),B=R(),P=R(),tp=R();

    pre_solve();

    for (;q;--q){

        int l=Rand()%n+1,r=Rand()%n+1;

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

        lastans=solve(l,r);

    	ans=(ans+lastans%mod)%mod;

	}

	cout<<(ans+mod)%mod<<endl;

    return 0;

}//

巴特西

【纪中集训2019.3.11】Cubelia

题目：

描述

范围：

题解：

Part1

Part2 \(\pm rmq\)

最新文章

热门文章