「HNOI 2016」序列

\(Description\)

给你一个序列,每次询问一个区间,求其所有子区间的最小值之和

\(Solution\)

这里要用莫队算法

首先令\(val\)数组为原序列

我们考虑怎么由一个区间\([l,r]\)到\([l,r+1]\)

我们发现新增加的区间为:

\[[l,r+1],[l+1,r+1],[l+2,r+1]...[r,r+1],[r+1,r+1]
\]

我们令\([l,r+1]\)内的最小值的位置为\(x\)

则\([l,r+1],[l+1,r+1]...[x-1,r+1],[x,r+1]\)的最小值都为\(val[x]\).

所以现在我们只需要考虑\([x+1,r+1],[x+2,r+1]...[r,r+1],[r+1,r+1]\)区间对答案的影响即可

用单调栈处理出\(pre[i]\)

\(pre[i]\)表示在\(i\)前第一个小于他的数的位置

这样子就可以知道左端点在\([pre_i,i]\)之间的数时,最小值都为\(i\)

求出这个就可以求出来\([x+1,r+1],[x+2,r+1]...[r,r+1],[r+1,r+1]\)的答案了

代码为:

for(int i=1;i<=n;i++) suml[i]=suml[pre[i]]+c[i]*(i-pre[i]);

有点类似前缀和,询问也差不多

具体直接见代码吧

\(Code\)

#include<bits/stdc++.h>

#define int long long

using namespace std;

typedef long long ll;

const int mod=1e9+7;

int read(){

    int x=0,f=1;char c=getchar();

    while(c<'0'||c>'9') f=(c=='-')?-1:1,c=getchar();

    while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();

    return x*f;

}

struct node {

    int l,r,id,ans;

}a[100010];

int block[100010],c[500001],lg[500001];

bool cmp1(const node & a , const node & b ){

    return block[a.l]==block[b.l]?a.r<b.r:a.l<b.l;

}

bool cmp2(const node & a , const node & b ){

    return a.id<b.id;

}

int p,m,sqr,n,f[100010][60],suml[500001],sumr[500001];

int pre[500001],nex[500001];

stack<int> s;

int min(int a,int b){

    return c[a]>c[b]?b:a;

}

void init() {

    for(int i=1; i<=n; i++)

        f[i][0]=i;

    for(int i=1; i<=lg[n]; i++)

        for(int j=1; j<=n-(1<<i)+1; j++)

	        f[j][i]=min(f[j][i-1],f[j+(1<<(i-1))][i-1]);

    for(int i=1;i<=n;i++){

	    while(!s.empty()&&c[s.top()]>c[i]) s.pop();

	    if(s.empty())

	        pre[i]=0,s.push(i);

    	else

	        pre[i]=s.top(),s.push(i);

    }

    while(!s.empty()){

    	p=s.top(),s.pop();

	    if(s.empty())

	        pre[p]=0;

    	else

	        pre[p]=s.top();

    }

    for(int i=n;i>=1;i--){

    	while(!s.empty()&&c[s.top()]>c[i]) s.pop();

    	if(s.empty())

    	    nex[i]=n+1,s.push(i);

    	else

    	    nex[i]=s.top(),s.push(i);

    }

    while(!s.empty()){

    	p=s.top(),s.pop();

	    if(s.empty())

	        nex[p]=n+1;

    	else

	        nex[p]=s.top();

    }

    for(int i=1;i<=n;i++)

    	suml[i]=suml[pre[i]]+c[i]*(i-pre[i]);

    for(int i=n;i>=1;i--)

	    sumr[i]=sumr[nex[i]]+c[i]*(nex[i]-i);

}

int find(int a,int b) {

    int k=lg[b-a+1];

    return min(f[a][k],f[b-(1<<k)+1][k]);

}

int work(int l,int r){

    int p=find(l,r);

    return c[p]*(r-p+1)+sumr[l]-sumr[p];

}

int solve(int l,int r){

    int p=find(l,r);

    return c[p]*(p-l+1)+suml[r]-suml[p];

}

main(){

    n=read(),m=read(),sqr=sqrt(n);

    for(int i=1;i<=n;i++)

        scanf("%lld",&c[i]),block[i]=i/sqr+1,lg[i]=log(i)/log(2);

    for(int i=1;i<=m;i++)

        scanf("%lld%lld",&a[i].l,&a[i].r),a[i].id=i;

    sort(a+1,a+1+m,cmp1);

    init();

    int l=1,r=0,ans=0;

    for(int i=1;i<=m;i++){

    	int x=a[i].l,y=a[i].r;

	    while(r<y) ans+=solve(l,r+1),r++;

	    while(l>x) ans+=work(l-1,r),l--;

        while(r>y) ans-=solve(l,r),r--;

    	while(l<x) ans-=work(l,r),l++;

	    a[i].ans=ans;

    }

    sort(a+1,a+1+m,cmp2);

    for(int i=1;i<=m;i++)

	    cout<<a[i].ans<<endl;

}

巴特西

「HNOI 2016」序列

\(Description\)

\(Solution\)

\(Code\)

最新文章

热门文章

巴特西

「HNOI 2016」 序列

\(Description\)

\(Solution\)

\(Code\)

最新文章

热门文章

「HNOI 2016」序列