【HNOI2016】序列（线段树）

题意扩展版：有两个长度为 \(n\) 的序列 \(a,b\)，你需要维护 \(m\) 次操作：

• 对 \(a\) 区间赋值。
• 给定 \(l,r\)，对于所有 \(i\in[l,r]\)，执行 \(b_i\gets b_i+a_i\)。
• 询问区间 \(b\) 的和。

题解：

UPD：可以线段树上每个点维护矩阵 \([suma,sumb,1]\) 简单做到 \(O(n\log n)\)。

感觉整篇题解都有点表达不清，但是我也不清楚应该怎样表达才好。

考虑使用线段树，发现操作一和操作二的懒标记是不好合并的，因为会出现两个操作二中间夹着一个操作一的情况。

但我们可以这样：进行操作一时，只有当前节点代表的区间中的所有 \(a_i\) 都相同时才更新并结束递归。

这时操作二的懒标记就可以变成区间加的标记：因为这个区间的 \(a_i\) 都相同，所以对这个区间进行 \(t\) 次操作二相当于对这个区间的每一个 \(b_i\) 都加上 \(a_it\)。

这时只需要维护这几个标记即可：区间加、\(a\) 区间赋值标记、操作二次数标记。规定先执行 \(a\) 区间赋值标记再执行操作二次数标记，而且保证当 \(a\) 区间赋值标记存在时，当前区间原来的 \(a_i\) 都是相同的。

代数的理解是每个位置维护了一条直线 \(y=a_ix+c\)，操作二相当于是区间 \(x\) 加一，而对于区间 \(a_i\) 赋值，若原本区间内所有的 \(a_i\) 都相等，你会发现这个区间内所有的直线的 \(c\) 的变化量都是相同的。这时三个标记对应着：区间直线截距（\(c\)）加、区间直线斜率（\(a_i\)）赋值、区间 \(x\) 加一。

考虑这么做的时间复杂度，瓶颈在于进行操作一时遍历线段树的时间。

设 \(S\) 表示 \(a\) 序列中的极长相等段个数，规定这里的 “段” 必须能被线段树上的某个节点所代表。初始时 \(S\) 为 \(O(n)\) 级别。

考虑一次操作一的过程：它会在线段树上访问到 \(a\) 序列中连续的若干个相等段 \(p_1,\cdots,p_k\)，时间复杂度为 \(O(k\log n)\)，但是访问完之后 \(p_1,\cdots,p_k\) 将会合并为至多 \(O(\log n)\) 个极长相等段，\(S\) 至少会减少 \(O(k-\log n)\)。但由于 \(p_1\) 和 \(p_k\) 原来不一定是极长的相等段，访问到它们的过程中会把它们原本所属的极长相等段各拆成至多 \(O(\log n)\) 个极长相等段，所以 \(S\) 又会增加至多 \(O(2\log n)\)。所以总的来说，\(S\) 还是至少会减少 \(O(k-\log n)\)。

由于 \(S\) 应该满足始终大于 \(0\)，所以 \(n-\sum_{i=1}^m(k-\log n)>0\)，于是 \(\sum_{i=1}^m k<n+m\log n\)，于是总时间复杂度为 \(O((n+m\log n)\log n)=O(n\log n+m\log ^2n)\)。

#include<bits/stdc++.h>

#define ll long long
#define fi first
#define se second
#define pii pair<int,int>
#define mk(a,b) make_pair(a,b)
#define N 100010

using namespace std;

inline int read()
{
	int x=0,f=1;
	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;
}

ll ans[N];
int n,Q,a[N];
int top,sta[N];
ll sum[N<<2],suma[N<<2],add[N<<2];
int na[N<<2],tim[N<<2],reset[N<<2];
bool tag[N<<2];

vector<pii>q[N];

void up(int k)
{
	sum[k]=sum[k<<1]+sum[k<<1|1];
	suma[k]=suma[k<<1]+suma[k<<1|1];
	na[k]=na[k<<1];
}

void downa(int k,int nowa,int l,int r)
{
	add[k]+=1ll*tim[k]*na[k],tim[k]=0;
	tag[k]=1,na[k]=reset[k]=nowa,suma[k]=1ll*(r-l+1)*nowa;
}

void downt(int k,int t)
{
	sum[k]+=1ll*suma[k]*t;
	tim[k]+=t;
}

void downn(int k,ll v,int l,int r)
{
	sum[k]+=1ll*(r-l+1)*v;
	add[k]+=v;
}

void down(int k,int l,int r,int mid)
{
	if(tag[k])
	{
		downa(k<<1,reset[k],l,mid);
		downa(k<<1|1,reset[k],mid+1,r);
		tag[k]=0;
	}
	if(tim[k])
	{
		downt(k<<1,tim[k]);
		downt(k<<1|1,tim[k]);
		tim[k]=0;
	}
	if(add[k])
	{
		downn(k<<1,add[k],l,mid);
		downn(k<<1|1,add[k],mid+1,r);
		add[k]=0;
	}
}

void update(int k,int l,int r,int ql,int qr,int nowa)
{
	if(ql<=l&&r<=qr)
	{
		downa(k,nowa,l,r);
		return;
	}
	int mid=(l+r)>>1;
	down(k,l,r,mid);
	if(ql<=mid) update(k<<1,l,mid,ql,qr,nowa);
	if(qr>mid) update(k<<1|1,mid+1,r,ql,qr,nowa);
	up(k);
}

ll query(int k,int l,int r,int ql,int qr)
{
	if(ql<=l&&r<=qr) return sum[k];
	int mid=(l+r)>>1;
	down(k,l,r,mid);
	ll ans=0;
	if(ql<=mid) ans+=query(k<<1,l,mid,ql,qr);
	if(qr>mid) ans+=query(k<<1|1,mid+1,r,ql,qr);
	return ans;
}

int main()
{
	n=read(),Q=read();
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<=Q;i++)
	{
		int l=read(),r=read();
		q[r].push_back(mk(l,i));
	}
	for(int i=1;i<=n;i++)
	{
		update(1,1,n,sta[top]+1,i,a[i]);
		while(top&&a[sta[top]]>a[i])
		{
			update(1,1,n,sta[top-1]+1,sta[top],a[i]);
			top--;
		}
		sta[++top]=i;
		downt(1,1);
		for(pii que:q[i])
			ans[que.se]=query(1,1,n,que.fi,i);
	}
	for(int i=1;i<=Q;i++)
		printf("%lld\n",ans[i]);
	return 0;
}

另一个很像的例题：【XSY3813】漏网之鱼。