P6604 [HNOI2016] 序列 加强版

链接：P6604 [HNOI2016] 序列 加强版
首先，像这种题可以转化为计算贡献，即计算每一个元素成为最小值的次数。

这个次数怎么求呢？显然单调栈模板，对于每一个数计算左边和右边第一个比它小的数\(l[i]\)和\(r[i]\)。

CODE 1:

for(int i=1;i<=n;i++){
	while(k && a[i]<a[sta[k]]){
		k--;
	}
	if(!k) l[i]=0;
	else{
		l[i]=sta[k];
	}
	sta[++k]=i;
}
k=0;
for(int i=n;i>=1;i--){
	while(k && a[i]<a[sta[k]]){
		k--;
	}
	if(!k) r[i]=n+1;
	else{
		r[i]=sta[k];
	}
	sta[++k]=i;
}

求出\(l[i]\)和\(r[i]\)后，我们发现虽然在线询问\([l,r]\),不好做，但是询问\([1,r]\)和\([l,n]\)是好做的，考虑先求出这两者，观察能否推广。

令\(dp[i]\)为以\(i\)结尾的所有字串的最小值之和，显然左端点在\(l[i]\)之前的部分最小值跟\(l[i]+1到i\)这一段毫无关系，所以这一部分的答案是\(dp[l[i]]\)。

而对于左端点在\(l[i]\)之后的部分，显然此时最小值是\(a[i]\)（第\(i\)的数的值），这一种情况有\(i-l[i]\)个区间，贡献是\(a[i]\times (i-l[i])\)

综上，\(dp[i]=dp[l[i]]+a[i]\times (i-l[i])\)

相同地，令\(DP[i]\)为从\(i\)开始的的所有字串的最小值之和，有\(DP[i]=DP[r[i]]+a[i]\times (r[i]-i)\)

令\(sum[i]\)为\([1,i]\)的答案，显然就是以\(1到i\)结尾的所有字符串的最小值之和，即\(sum[i]=\sum_{j=1}^{i} dp[j]\)

同样的，令\(SUM[i]\)为\([i,n]\)的答案，有\(SUM[i]=\sum_{j=i}^{n}DP[j]\)

CODE 2:

for(int i=1;i<=n;i++){
	dp[i]=dp[l[i]]+a[i]*(i-l[i]);
}
for(int i=n;i>=1;i--){
	DP[i]=DP[r[i]]+a[i]*(r[i]-i);
}
for(int i=1;i<=n;i++){
	sum[i]=sum[i-1]+dp[i];
}
for(int i=n;i>=1;i--){
	SUM[i]=SUM[i+1]+DP[i];
}

现在考虑怎么求出\([l,r]\)类型的答案。考虑分类贡献。我们使用\(st\)表预处理出\([l,r]\)区间内的最小值所在位置\(pos\)。

那么\([l,r]\)的所有子区间分为\(3\)种：

• 1.左端点和右端点在\(pos\)两侧
• 2.左端点和右端点在\(pos\)左侧
• 3.左端点和右端点在\(pos\)右侧

第一种情况很简单，区间的个数是\((pos-l+1)\times (r-pos+1)\),每一个区间的最小值都是\(pos\),所以这部分的贡献是\((pos-l+1)\times (r-pos+1)\times a_{pos}\)

考虑第二种情况，你可能认为直接就是\(SUM[l]-SUM[pos]\)，其实不然。因为这样只确定了左端点在\([l,pos)\)内而没有限制右端点。

考虑容斥，减去右端点在\(pos\)右侧的情况。此时左端点在\([l,pos)\)内，有\(pos-l\)种选择，对于每一种选择，既然\(pos\)是\([l,r]\)的最小位置，右端点落在\(pos\)右侧的贡献自然是\(DP[pos]\)。所以要减去\(DP[pos] \times (pos-l)\)

综上，第二种情况的贡献是\(SUM[l]-SUM[pos]-DP[pos]\times (pos-l)\)

同样的，第三种情况的贡献是\(sum[r]-sum[pos]-dp[pos]\times (r-pos)\)

把这三者加起来就是\([l,r]\)的贡献了。

下面是完整代码（ps:有的变量重名改了名）

CODE 3:

#include<bits/stdc++.h>
#define int long long
using namespace std;
int sum[100011];
int SUM[100011];
int dp[100011];
int DP[100011];
int st[100011][21],pos[100011][21];
int n,q,type,sta[100011],k;
int a[100011];
int l[100011];
int r[100011];
unsigned long long re=0;

namespace gen{
	typedef unsigned long long ull;
	ull s,a,b,c,lastans=0;
	void in(){
		cin>>s>>a>>b>>c;
	}
	ull rand(){
		return s^=(a+b*lastans)%c;
	}
};

signed main(){
	cin>>n>>q>>type;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++){
		st[i][0]=a[i];
		pos[i][0]=i;
	}
	for(int j=1;(1<<j)<=n;j++){
		for(int i=1;i+(1<<j)-1<=n;i++){
			if(st[i][j-1]<=st[i+(1<<j-1)][j-1]){
				st[i][j]=st[i][j-1];
				pos[i][j]=pos[i][j-1];
			}
			else{
				st[i][j]=st[i+(1<<j-1)][j-1];
				pos[i][j]=pos[i+(1<<j-1)][j-1];
			}
		}
	}
	for(int i=1;i<=n;i++){
		while(k && a[i]<a[sta[k]]){
			k--;
		}
		if(!k) l[i]=0;
		else{
			l[i]=sta[k];
		}
		sta[++k]=i;
	}
	k=0;
	for(int i=n;i>=1;i--){
		while(k && a[i]<a[sta[k]]){
			k--;
		}
		if(!k) r[i]=n+1;
		else{
			r[i]=sta[k];
		}
		sta[++k]=i;
	}
	for(int i=1;i<=n;i++){
		dp[i]=dp[l[i]]+a[i]*(i-l[i]);
	}
	for(int i=n;i>=1;i--){
		DP[i]=DP[r[i]]+a[i]*(r[i]-i);
	}
	for(int i=1;i<=n;i++){
		sum[i]=sum[i-1]+dp[i];
	}
	for(int i=n;i>=1;i--){
		SUM[i]=SUM[i+1]+DP[i];
	}
	if(type==1){
		gen::in();
	}
	int lt,rt;
	for(int i=1;i<=q;i++){
		if(!type){
			cin>>lt>>rt;
		}
		else{
			lt=gen::rand()%n+1;
			rt=gen::rand()%n+1;
			if(lt>rt) std::swap(lt,rt);
		}
		int poss;
		int kk=log2(rt-lt+1);
		if(a[pos[lt][kk]]<=a[pos[rt-(1<<kk)+1][kk]]) poss=pos[lt][kk];
		else poss=pos[rt-(1<<kk)+1][kk];
		unsigned long long ans=(unsigned long long)(a[poss]*(poss-lt+1)*(rt-poss+1));
		ans+=(unsigned long long)(sum[rt]-sum[poss]-dp[poss]*(rt-poss));
		ans+=(unsigned long long)(SUM[lt]-SUM[poss]-DP[poss]*(poss-lt));
		gen::lastans=ans;
		re^=ans;
	}
	cout<<re;
	return 0;
}