loj2051 「HNOI2016」序列

ref
#include <algorithm>

#include <iostream>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long ll;

int n, q, a[100005], l[100005], r[100005], sta[100005], din, blc, bel[100005], st[100005][19], mii[17], mlg[100005];

ll sl[100005], sr[100005], now, ans[100005];

struct Ques{

	int ll, rr, id;

}qu[100005];

bool cmp(Ques x, Ques y){

	if(bel[x.ll]!=bel[y.ll])	return bel[x.ll]<bel[y.ll];

	if(bel[x.ll]&1)	return x.rr<y.rr;

	return x.rr>y.rr;

}

int getPos(int x, int y){

	int l=mlg[y-x+1], k=y+1-mii[l];

	return a[st[x][l]]<a[st[k][l]]?st[x][l]:st[k][l];

}

ll calL(int x, int y){

	int p=getPos(x, y);

	return (ll)a[p]*(y-p+1)+sr[x]-sr[p];

}

ll calR(int x, int y){

	int p=getPos(x, y);

	return (ll)a[p]*(p-x+1)+sl[y]-sl[p];

}

int main(){//freopen("sequence9.in", "r", stdin);

	cin>>n>>q;

	blc = sqrt(n);

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

		scanf("%d", &a[i]);

		bel[i] = (i - 1) / blc + 1;

		st[i][0] = i;

	}

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

		scanf("%d %d", &qu[i].ll, &qu[i].rr);

		qu[i].id = i;

	}

	sort(qu+1, qu+1+q, cmp);

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

		while(din && a[sta[din]]>=a[i])	din--;

		if(din)	l[i] = sta[din];

		sta[++din] = i;

	}

	din = 0;

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

		r[i] = n + 1;

		while(din && a[sta[din]]>=a[i])	din--;

		if(din)	r[i] = sta[din];

		sta[++din] = i;

	}

	mii[0] = 1;

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

		mii[i] = mii[i-1] << 1;

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

		mlg[i] = mlg[i>>1] + 1;

	for(int j=1; j<=16; j++)

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

			st[i][j] = st[i][j-1];

			int k=i+mii[j-1];

			if(k<=n)	st[i][j] = (a[st[i][j-1]]<a[st[k][j-1]])?st[i][j-1]:st[k][j-1];

		}

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

		sl[i] = sl[l[i]] + (ll)(i - l[i]) * a[i];

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

		sr[i] = sr[r[i]] + (ll)(r[i] - i) * a[i];

	int gtl=qu[1].ll, zzh=gtl-1;

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

		while(gtl>qu[i].ll)	now += calL(--gtl, zzh);

		while(zzh<qu[i].rr)	now += calR(gtl, ++zzh);

		while(gtl<qu[i].ll)	now -= calL(gtl++, zzh);

		while(zzh>qu[i].rr)	now -= calR(gtl, zzh--);

		ans[qu[i].id] = now;

	}

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

		printf("%lld\n", ans[i]);

	return 0;

}
巴特西

loj2051 「HNOI2016」序列

最新文章

热门文章
