CF1677E Tokitsukaze and Beautiful Subsegments

(题目传送门)

你就算再怎么套路我也做不出来……

看到 \(\max a_k\)，根据套路想到用单调栈处理出 \(a_i\) 左边第一个比它大的位置 \(pre_i\)，右边第一个比它大的位置 \(nxt_i\)。枚举最大值 \(a_i\) 考虑它的贡献，显然若存在 \(j,k\) 满足 \(nxt_i<j,k<pre_i\) 且 \(a_j\times a_k=a_i\)，那么记 \(x=\min(i,j,k),y=\max(i,j,k)\)，那么 \((j,k)\) 就可以对区间 \((pre_i,x]\cup[y,nxt_i)\) 产生贡献。显然满足这种条件的数对不超过 \(\mathcal{O}(n\ln n)\) 个，可以预处理出来。

将这个区间贡献看成矩形的赋值，这是难操作的，尝试转化成矩形加。发现不同的 \(\max\) 值 \(a_i\) 的矩形不会相交，于是只需考虑单个 \(a_i\) 内部的矩形。假设现在有若干数对 \((x,y)\) 可以对 \((pre_i,x]\cup[y,nxt_i)\) 产生贡献，矩形可能相交。你发现如果 \(x_i<x_j\) 且 \(y_i>y_j\) 那么 \((x_i,y_i)\) 就被 \((x_j,y_j)\) 完全包含了，所以最后有用的数对必然满足 \(x_1<x_2<\dots <x_m\) 且 \(y_1<y_2<\dots <y_m\)，这可以排序后单调栈求出。

将单个 \(a_i\) 的矩形拆解后，画个图发现这样的矩形覆盖可以直接容斥变成矩形加。于是问题转化成了矩形加、矩形求和。将询问离线下来，扫描线+树状数组维护即可。

#include<bits/stdc++.h>
#define LL long long
#define pii pair<int,int>
using namespace std;

const int N=2e5+10,M=1e6+10;

int n,m,p[N],q[N];
int sta[N],top,pre[N],nxt[N];
vector <pii> P[N],tmp,Q[N];
vector < array<int,3> > mat[N];
LL ans[M];

struct BIT
{
	LL c1[N],c2[N];

	void add(int x,int y)
	{
		for(int i=x; i<=n; i+=(i&-i))
		{
			c1[i]+=(LL)y;
			c2[i]+=1LL*y*x;
		}
	}

	LL ask(int x)
	{
		LL res=0;
		for(int i=x; i; i-=(i&-i))
			res+=1LL*(x+1)*c1[i]-c2[i];
		return res;
	}

	void update(int l,int r,int v){add(l,v);add(r+1,-v);}

	LL query(int l,int r){return ask(r)-ask(l-1);}
}T1,T2;

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1; i<=n; i++)
		scanf("%d",&p[i]),q[p[i]]=i;

	for(int i=1; i<=n; i++)
	{
		while(top && p[sta[top]]<p[i])
			top--;
		pre[i]=sta[top];  sta[++top]=i;
	}
	sta[top=0]=n+1;
	for(int i=n; i>=1; i--)
	{
		while(top && p[sta[top]]<p[i])
			top--;
		nxt[i]=sta[top];  sta[++top]=i;
	}

	for(int i=1; i*(i+1)<=n; i++)
		for(int j=i+1; i*j<=n; j++)
			if(pre[q[i*j]]<min(q[i],q[j]) && nxt[q[i*j]]>max(q[i],q[j]))
				P[q[i*j]].push_back({min({q[i],q[j],q[i*j]}),max({q[i],q[j],q[i*j]})});

	for(int i=1; i<=n; i++)
	{
		tmp.clear();
		tmp.push_back({pre[i],i-1});
		sort(P[i].begin(),P[i].end(),[](pii A,pii B)
			{return A.first==B.first? A.second>B.second:A.first<B.first;});
		for(auto [l,r]:P[i])
		{
			while(r<=tmp.back().second)
				tmp.pop_back();
			tmp.push_back({l,r});
		}
		for(int j=1; j<tmp.size(); j++)
		{
			mat[tmp[j].second].push_back({tmp[j-1].first+1,tmp[j].first,1});
			mat[nxt[i]].push_back({tmp[j-1].first+1,tmp[j].first,-1});
		}
	}		

	for(int i=1; i<=m; i++)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		Q[r].push_back({l,i});
	}

	for(int i=1; i<=n; i++)
	{
		for(auto [l,r,op]:mat[i])
		{
			T1.update(l,r,op);
			T2.update(l,r,op*(i-1));
		}
		for(auto [l,id]:Q[i])
			ans[id]=1LL*i*T1.query(l,i)-T2.query(l,i);
	}

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

	return 0;
}