1677E - Tokitsukaze and Beautiful Subsegments - CodeForces Solution

#include <bits/stdc++.h>
#define IOS() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define int long long
#define fir first
#define se second
#define pb(x) push_back(x)
#define pii pair<int,int>
#define all(a) (a).begin(),(a).end()
#define mp(a,b) make_pair(a,b)
#define ls k<<1
#define rs k<<1|1
using namespace std;
int lowbit(int x){
	return x&-x;
}
inline int rd(){
    int f=0;int x=0;char ch=getchar();
    for(;!isdigit(ch);ch=getchar())f|=(ch=='-');
    for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+ch-'0';
    if(f)x=-x;
    return x;
}
bool cmp(int x,int y){
	return x>y;
}
int n,q,a[200005],t[200005],st[200005],top,L[200005],R[200005],val[200005],ans[1000005];
vector<pii> m[200005],add[200005],del[200005];
vector<pair<pii,int>> qe[200005]; 
struct segmentTree{
	int l,r,sum,cnt,as,ac;
}d[800005];
void build(int k,int l,int r){
	d[k].l=l,d[k].r=r;
	if(l==r)
		return ;
	int mid=l+r>>1;
	build(ls,l,mid);
	build(rs,mid+1,r);
}
void pushdown(int k){
	if(d[k].as){
		d[ls].sum+=(d[ls].r-d[ls].l+1)*d[k].as;
		d[rs].sum+=(d[rs].r-d[rs].l+1)*d[k].as;
		d[ls].as+=d[k].as,d[rs].as+=d[k].as;
		d[k].as=0;
	}
	if(d[k].ac){
		d[ls].cnt+=(d[ls].r-d[ls].l+1)*d[k].ac;
		d[rs].cnt+=(d[rs].r-d[rs].l+1)*d[k].ac;
		d[ls].ac+=d[k].ac,d[rs].ac+=d[k].ac;
		d[k].ac=0;
	}
}
void update(int k,int x,int y,int v1,int v2){
	if(x<=d[k].l && d[k].r<=y){
		d[k].cnt+=(d[k].r-d[k].l+1)*v1,d[k].ac+=v1;
		d[k].sum+=(d[k].r-d[k].l+1)*v2,d[k].as+=v2;
		return ;
	}
	pushdown(k);
	int mid=d[k].l+d[k].r>>1;
	if(x<=mid)
		update(ls,x,y,v1,v2);
	if(mid+1<=y)
		update(rs,x,y,v1,v2);
	d[k].sum=d[ls].sum+d[rs].sum;
	d[k].cnt=d[ls].cnt+d[rs].cnt;
}
int query(int k,int x,int y,int v){
	if(x<=d[k].l && d[k].r<=y)
		return d[k].cnt*v+d[k].sum;
	pushdown(k);
	int mid=d[k].l+d[k].r>>1,res=0;
	if(x<=mid)
		res+=query(ls,x,y,v);
	if(mid+1<=y)
		res+=query(rs,x,y,v);
	return res;
}
signed main(){
	//freopen("文件名.in","r",stdin);
    //freopen("文件名.out","w",stdout);
    IOS();
	cin>>n>>q;
	for(int i=1;i<=n;i++)
		cin>>a[i],t[a[i]]=i;
	a[0]=a[n+1]=1e9;
	st[top=1]=0;
	for(int i=1;i<=n;i++){
		while(top && a[i]>a[st[top]])
			top--;
		L[i]=st[top]+1;
		st[++top]=i;
	}
	st[top=1]=n+1;
	for(int i=n;i>=1;i--){
		while(top && a[i]>a[st[top]])
			top--;
		R[i]=st[top]-1;
		st[++top]=i;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;i*j<=n;j++){
			if(t[i]>=t[j])
				continue;
			if(t[i]<L[t[i*j]] || t[j]>R[t[i*j]])
				continue;
			m[t[i*j]].pb(mp(min(t[i],t[i*j]),max(t[j],t[i*j])));
		}
	}
	for(int i=1;i<=n;i++){
		if(m[i].empty())
			continue;
		sort(all(m[i]));
		st[top=1]=L[i]-1;
		for(auto v:m[i]){
			while(top>1 && v.se<=val[top-1])
				top--;
			st[++top]=v.fir;
			val[top-1]=v.se;
		}
		for(int j=1;j<top;j++){
			add[val[j]].pb(mp(st[j]+1,st[j+1]));
			del[R[i]].pb(mp(st[j]+1,st[j+1]));
		}
	}
	for(int i=1;i<=q;i++){
		int ll,rr;
		cin>>ll>>rr;
		qe[rr].pb(mp(mp(ll,rr),i));
		qe[ll-1].pb(mp(mp(ll,rr),-i));
	}
	build(1,1,n);
	for(int i=1;i<=n;i++){
		for(auto v:add[i])
			update(1,v.fir,v.se,1,-i+1);
		for(auto v:del[i])
			update(1,v.fir,v.se,-1,i);
		for(auto v:qe[i])
			ans[abs(v.se)]+=(v.se>0?1:-1)*query(1,v.fir.fir,v.fir.se,i);
	}
	for(int i=1;i<=q;i++)
		cout<<ans[i]<<"\n";
	return 0;
}