题意扩展版：有两个长度为 \(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】漏网之鱼。
原文地址：http://www.cnblogs.com/ez-lcw/p/16837451.html
