本来以为柯以打线段树,结果搜了题解,发现的确可以打,不过矩阵乘法是什么东西???
先打莫队吧。
对于这种区间的题,还是有目的的一个个来。
对于询问区间 $[l,r] $,如果变成了区间 $[l,r+1]$ ,那么增加的贡献应该是
$[l,r+1],[l+1,r+1],[l+2.r+1],\cdots,[r+1,r+1]$。
显然右端点是固定的,考虑如何$O(1)$求得这串贡献。
开个数组?记录贡献?
但是这个数组的范围很难确定,因为不知道这个区间最小的数,是否会超出区间。
为了解决这个问题,可以手动求一下,这个区间最小的数的位置$p$,之后它的贡献就是$[l\sim p,p]$
这个可以用ST表解决。
有了这个基础,意味着这个区间已经拥有一个断点$p$,也就是在求数组的时候会用到这个$p$,有助于理解。
那么$[p+1\sim r+1,r+1]$这段贡献,可以用类似前缀和的数组解决:
其中$pre_i$表示在$i$之前第一个比$i$小的数的位置,可以用单调栈求得,$sl$的意义为$[1sim l,l]的最小贡献。
for(int i=1;i<=n;i++)sl[i]=sl[pre[i]]+1ll*c[i]*(i-pre[i]);
这里其实可以发现一个问题,它不是线性继承的,意味着差分的时候不能乱差分。
上面求的$p$就发挥了很大的作用,因为它是这个区间最小的数,那么$sl[r]$一定是从$sl[p]$来的,它不能绕过去(否则$p$不是最小的),所以$sl[r+1]-sl[p]$就是$[p+1\sim r+1,r+1]$的贡献。
$[l,r]->[l,r-1],[l,r]->[l+1,r],[l,r]->[l-1,r]$的情况与上面类似,就不一一列举了。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#define gc getchar()
#define ll long long
#define ld long double
#define ull unsigned long long
using namespace std;
const int N=1e5+5,M=4e5+5;
template<class o>
inline void qr(o &x)
{
x=0;char c=gc;int f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
x*=f;
}
template<class o>
void qw(o x)
{
if(x<0)putchar('-'),x=-x;
if(x/10)qw(x/10);
putchar(x%10+48);
}
ll sl[N],sr[N];
int bel[N],pre[N],nex[N],n,m,f[18][N],Log[N],c[N],sta[N];
inline int mmin(int x,int y){return c[x]>c[y]?y:x;}
void init()
{
for(int i=2;i<=n;i++)Log[i]=Log[i>>1]+1;
for(int i=1;i<=n;i++)f[0][i]=i;
for(int i=1;i<=17;i++)
for(int j=1;j+(1<<i)-1<=n;j++)
f[i][j]=mmin(f[i-1][j],f[i-1][j+(1<<(i-1))]);
int top=0;
for(int i=1;i<=n;i++)
{
while(top&&c[sta[top]]>c[i])--top;
pre[i]=sta[top];sta[++top]=i;
}
while(top)pre[sta[top]]=sta[top-1],--top;
sta[top]=n+1;
for(int i=n;i;i--)
{
while(top&&c[sta[top]]>c[i])--top;
nex[i]=sta[top];sta[++top]=i;
}
while(top)nex[sta[top]]=sta[top-1],--top;
for(int i=1;i<=n;i++)sl[i]=sl[pre[i]]+1ll*c[i]*(i-pre[i]);
for(int i=n;i;i--)sr[i]=sr[nex[i]]+1ll*c[i]*(nex[i]-i);
}
inline int find(int a,int b)
{
int k=Log[b-a+1];
return mmin(f[k][a],f[k][b-(1<<k)+1]);
}
inline ll workr(int l,int r)
{
int p=find(l,r);
return 1ll*c[p]*(p-l+1)+sl[r]-sl[p];
}
inline ll workl(int l,int r)
{
int p=find(l,r);
return 1ll*c[p]*(r-p+1)+sr[l]-sr[p];
}
struct node{int l,r,id;}a[N];
ll Ans[N];
inline bool cmp(node a,node b){return bel[a.l]==bel[b.l]?a.r<b.r:bel[a.l]<bel[b.l];}
int main()
{
qr(n),qr(m);
for(int i=1;i<=n;i++)qr(c[i]);
int sqr=sqrt(n),T=(n-1)/sqr+1;
for(int i=1;i<=T;i++)
{
int L=(i-1)*sqr+1,R=min(L+sqr-1,n);
for(int j=L;j<=R;j++)bel[j]=i;
}
init();
for(int i=1;i<=m;i++)qr(a[i].l),qr(a[i].r),a[i].id=i;
sort(a+1,a+m+1,cmp);int l=1,r=0;ll ans=0;
for(int i=1;i<=m;i++)
{
int x=a[i].l,y=a[i].r;
while(r<y)ans+=workr(l,++r);
while(l>x)ans+=workl(--l,r);
while(r>y)ans-=workr(l,r--);
while(l<x)ans-=workl(l++,r);
Ans[a[i].id]=ans;
}
for(int i=1;i<=m;i++)qw(Ans[i]),puts("");
return 0;
}
线段树做法
适用性很广,便于理解。
首先一次询问的答案是 $\sum\limits_{i=l}^r\sum\limits_{j=i}^r\min\{C_k\}(k\in[i,j])$
假设现在记录到了$last$,记录一个 $val,sum$
$val_i=\min\{C_k\}(k\in[i,last])$,$sum_i$ 则记录历史版本的 $val_i$ 和,即
$sum_i=\sum\limits_{j=i}^{last}val_i=\sum\limits_{j=i}^{last}\min\{C_k\}(k\in[i,j])$
当$last$到了$r$时,上面的答案,其实就是$\sum\limits_{i=l}^r sum_i$
那么就可以用线段树维护 $val,sum $ ,只需要打四个标记 $(a,b,c,d)$ 。
即
$newsum=sum+val*c+d*(R-L+1)\\newval=val*a+b*(R-L+1)$
如果两个标记撞在一起,
列举一下 $val$ 的变化,
$a_2(a_1*val+b_1*(R-L+1))+b_2(R-L+1)=a_1a_2*val+b_1a_2*(R-L+1)+b_2*(R-L+1)$
对号入座,$a=a_1a_2,b=b_1a_2+b_2$
$c,d$也是如此。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#define gc getchar()
#define ll long long
#define ld long double
#define ull unsigned long long
using namespace std;
const int N=1e5+5,M=4e5+5;
template<class o>
inline void qr(o &x)
{
x=0;char c=gc;int f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
x*=f;
}
template<class o>
void qw(o x)
{
if(x<0)putchar('-'),x=-x;
if(x/10)qw(x/10);
putchar(x%10+48);
}
struct node
{
ll a,b,c,d;
node(ll a=1,ll b=0,ll c=0,ll d=0):a(a),b(b),c(c),d(d){}
node operator +(const node y)const{return node(a*y.a,y.b+b*y.a,a*y.c+c,d+y.d+b*y.c);}
};
struct SGT{node w;ll v,s;int siz;}t[N<<2];
inline void update(int p)
{
t[p].s=t[p<<1].s+t[p<<1|1].s;
t[p].v=t[p<<1].v+t[p<<1|1].v;
}
inline void cw(int p,node w)
{
t[p].s+=w.c*t[p].v+w.d*t[p].siz;
t[p].v=w.a*t[p].v+w.b*t[p].siz;
t[p].w=t[p].w+w;
}
void pushdown(int p)
{
node w=t[p].w;
if(w.a!=1||w.b||w.c||w.d)cw(p<<1,w),cw(p<<1|1,w),t[p].w=node(1,0,0,0);
}
void build(int p,int l,int r)
{
t[p].siz=r-l+1;t[p].w=node(1,0,0,0);
if(l==r){return ;}
int mid=l+r>>1;
build(p<<1,l,mid);build(p<<1|1,mid+1,r);
}
void change(int p,int l,int r,int L,int R,node w)
{
if(L<=l&&R>=r){cw(p,w);return ;}
int mid=l+r>>1;pushdown(p);
if(L<=mid)change(p<<1,l,mid,L,R,w);
if(R>mid)change(p<<1|1,mid+1,r,L,R,w);
update(p);
}
ll query(int p,int l,int r,int L,int R)
{
if(L<=l&&R>=r)return t[p].s;
int mid=l+r>>1;pushdown(p);ll val=0;
if(L<=mid)val+=query(p<<1,l,mid,L,R);
if(R>mid)val+=query(p<<1|1,mid+1,r,L,R);
return val;
}
struct Query{int l,r,id;}a[N];
inline bool cmp(Query a,Query b){return a.r==b.r?a.l<b.l:a.r<b.r;}
int sta[N],c[N],top;
ll ans[N];
int main()
{
int n,m;qr(n),qr(m);
for(int i=1;i<=n;i++)qr(c[i]);
for(int i=1;i<=m;i++)qr(a[i].l),qr(a[i].r),a[i].id=i;
sort(a+1,a+m+1,cmp);
build(1,1,n);top=0;int j=1;
for(int i=1;i<=n;i++)
{
while(top&&c[sta[top]]>c[i])--top;
change(1,1,n,sta[top]+1,i,node(0,c[i],0,0));
cw(1,node(1,0,1,0));sta[++top]=i;
while(j<=m&&a[j].r==i)ans[a[j].id]=query(1,1,n,a[j].l,a[j].r),++j;
}
for(int i=1;i<=m;i++)qw(ans[i]),puts("");
return 0;
}
0 条评论