「HNOI2016」序列 解题报告

「HNOI2016」序列

有一些高妙的做法，懒得看

考虑莫队，考虑莫队咋移动区间

然后你在区间内部找一个最小值的位置，假设现在从右边加

最小值左边区间显然可以\(O(1)\)，最小值右边的区间是断掉的，但注意它是单调的

于是每个点假装向左边第一个小于它的位置连边，就可以处理出前缀和一样的东西，然后预处理后也是\(O(1)\)的

---

Code:

#include <cstdio>

#include <cctype>

#include <algorithm>

#include <cmath>

#define ll long long

const int N=1e5+10;

template <class T>

void read(T &x)

{

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

	while(!isdigit(c)) f|=c=='-',c=getchar();

	while(isdigit(c)) x=x*10+c-'0',c=getchar();

	x=f?-x:x;

}

int n,q,Log[N],st[17][N],s[N],a[N],tot;

struct koito_yuu

{

	int l,r,lp,id;

	bool friend operator <(koito_yuu a,koito_yuu b){return a.lp==b.lp?a.r<b.r:a.lp<b.lp;}

}yuu[N];

int query(int l,int r)

{

	int d=Log[r+1-l],x=st[d][l],y=st[d][r-(1<<d)+1];

	return a[x]<a[y]?x:y;

}

ll ans[N],sum,fl[N],fr[N];

void addl(int l,int r)

{

	int x=query(l,r);

	sum+=fr[l]-fr[x]+1ll*a[x]*(r+1-x);

}

void dell(int l,int r)

{

	int x=query(l,r);

	sum-=fr[l]-fr[x]+1ll*a[x]*(r+1-x);

}

void addr(int l,int r)

{

	int x=query(l,r);

	sum+=fl[r]-fl[x]+1ll*a[x]*(x+1-l);

}

void delr(int l,int r)

{

	int x=query(l,r);

	sum-=fl[r]-fl[x]+1ll*a[x]*(x+1-l);

}

int main()

{

	read(n),read(q);

	Log[0]=-1;

	for(int i=1;i<=n;i++) st[0][i]=i,read(a[i]),Log[i]=Log[i>>1]+1;

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

	{

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

		{

			int x=st[j-1][i],y=st[j-1][i+(1<<j-1)];

			st[j][i]=a[x]<a[y]?x:y;

		}

	}

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

	{

		while(tot&&a[s[tot]]>=a[i]) --tot;

		fl[i]=fl[s[tot]]+1ll*a[i]*(i-s[tot]);

		s[++tot]=i;

	}

	s[tot=0]=n+1;

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

	{

		while(tot&&a[s[tot]]>=a[i]) --tot;

		fr[i]=fr[s[tot]]+1ll*a[i]*(s[tot]-i);

		s[++tot]=i;

	}

	int B=sqrt(n)+1;

	for(int i=1;i<=q;i++) read(yuu[i].l),read(yuu[i].r),yuu[i].id=i,yuu[i].lp=(yuu[i].l-1)/B;

	std::sort(yuu+1,yuu+1+q);

	int l=1,r=0;

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

	{

		while(r<yuu[i].r) addr(l,++r);

		while(l<yuu[i].l) dell(l++,r);

		while(l>yuu[i].l) addl(--l,r);

		while(r>yuu[i].r) delr(l,r--);

		ans[yuu[i].id]=sum;

	}

	for(int i=1;i<=q;i++) printf("%lld\n",ans[i]);

	return 0;

}

---

2019.3.10