[bzoj4540][Hnoi2016]序列

来自FallDream的博客，未经允许，请勿转载，谢谢合作。

给定长度为n的序列：a1,a2,…,an，记为a[1:n]。类似地，a[l:r]（1≤l≤r≤N）是指序列：a_l,a_l+1,…,a_r-₁,a_r。若1≤l≤s≤t≤r≤n，则称a[s:t]是a[l:r]的子序列。现在有q个询问，每个询问给定两个数l和r，1≤l≤r≤n，求a[l:r]的不同子序列的最小值之和。例如，给定序列5,2,4,1,3，询问给定的两个数为1和3，那么a[1:3]有6个子序列a[1:1],a[2:2],a[3:3],a[1:2],a[2:3],a[1:3]，这6个子序列的最小值之和为5+2+4+2+2+2=17。

n,q<=10^5

是子串偏说子序列...

其实就是个矩形加矩形查可以用扫描线+线段树nlogn实现，但是中间量会爆longlong..........直接自然溢出就行了

写了个莫队考虑插入右端点时答案改变的量，只需要计算子串右端点为现在右端点的答案即可

找到[L,R]中的最小值位置pos,那么左端点在[L,pos]时候贡献是a[pos]

用单调栈求出每个数字前面第一个比他小的数字位置，做一个简单递推 f[i]=f[last[i]]+(i-last[i])*a[i] 脑补一下应该比较好理解。

这样[pos,R]的贡献直接相减即可。

删除/左端点移动同理

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define ll long long 
#define MN 100000
#define MD 17
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 * 10 + ch - '0';ch = getchar();}
    return x * f;
}

ll Rt[MN+5],Lt[MN+5],Ans[MN+5],ans=0;
int n,m,a[MN+5],block[MN+5],size,la[MN+5],L,R,ne[MN+5],Q[MN+5],top=0,f[MD+1][MN*3+5],Log[MN+5];
struct ques{int l,r,id;}q[MN+5];
bool cmp(ques x,ques y){return block[x.l]==block[y.l]?x.r<y.r:x.l<y.l;}
inline int U(int x,int y){return a[x]>a[y]?y:x;}
inline int Query(int l,int r){int s=Log[r-l+1];return U(f[s][l],f[s][r-(1<<s)+1]);}

void AddR(int x,int ad)
{
    int p=Query(L,R);
    ans+=1LL*ad*(Rt[x]-Rt[p]+1LL*(p-L+1)*a[p]);        
}

void AddL(int x,int ad)
{
    int p=Query(L,R); 
    ans+=1LL*ad*(Lt[x]-Lt[p]+1LL*(R-p+1)*a[p]);
}

int main()
{
    n=read();m=read();size=sqrt(n);a[0]=2e9;
    for(int i=1;i<=n;++i) a[i]=read(),block[i]=(i-1)/size+1,f[0][i]=i;
    for(int i=1;i<=m;++i) q[i].l=read(),q[i].r=read(),q[i].id=i;
    sort(q+1,q+m+1,cmp);Log[0]=-1;
    for(int i=1;i<=n;++i) Log[i]=Log[i>>1]+1;
    for(int i=1;i<=MD;++i)
        for(int j=1;j<=n;++j)
            f[i][j]=U(f[i-1][j],f[i-1][j+(1<<(i-1))]);
    for(int i=1;i<=n;++i)
    {
        while(top&&a[Q[top]]>a[i])    ne[Q[top]]=i,--top;
        la[i]=Q[top];Q[++top]=i;
    }
    for(int i=1;i<=top;++i) ne[Q[i]]=n+1;
    for(int i=1;i<=n;++i) Rt[i]=Rt[la[i]]+1LL*a[i]*(i-la[i]);
    for(int i=n;i;--i)    Lt[i]=Lt[ne[i]]+1LL*a[i]*(ne[i]-i);
    ans=a[L=R=1];
    for(int i=1;i<=m;++i)
    {
        while(R<q[i].r) ++R,AddR(R,1);    
        while(L>q[i].l) --L,AddL(L,1);
        while(R>q[i].r) AddR(R,-1),--R;
        while(L<q[i].l) AddL(L,-1),++L;
        Ans[q[i].id]=ans; 
    }
    for(int i=1;i<=m;++i) printf("%lld
",Ans[i]);
    return 0;
}