题解：CF1677E Tokitsukaze and Beautiful Subsegments

· · 题解

尝试找到可以贡献的区间放到二维平面内，其中横坐标代表左端点，纵坐标代表右端点，然后求子区间就是平面矩阵求和。

对于 p_i\times p_j 是一个经典的调和级数处理，我们枚举 p_i，再枚举 p_j 满足 p_i\times p_j\le n，是 O(n\operatorname{ln} n)。此时确定了 i,j 之后可以唯一确定 k，接着根据三者位置关系可以得到若干满足条件的区间。

可以用单调栈求出 p_k 作为最大值的区间 [ml_k,mr_k]，如果 i,j\in [ml_k,mr_k] 的话，我们就可以得到左端点在 [ml_k,\min(i,j,k)] 之间，右端点在 [\max(i,j,k),mr_k] 之间的区间可以对于答案产生贡献。

对于一个 k 可能有多个贡献区间，某些贡献会算重。考虑去重，对于 k 所支配的若干个区间 (l_i,r_i)，我们以 l_i 为第一关键字降序排序，r_i 为第二关键字升序排序。考虑 (l_{i-1},r_{i-1}) (棕线) 和 (l_i,r_i) （银线），可以发现银线中去除棕线内容后就是红色部分，于是我们每次截取这个红色部分矩阵加入贡献即可。

这样子就不会算重了，问题就变成了若干次矩阵加之后进行若干次矩阵求和，可以用扫描线加历史和来解决。

时间复杂度 O(n\log^2 n)。贡献区间个数是 O(n\operatorname{ln} n) 级别的，所以是 2log。

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
using namespace std;
typedef long long ll;
const int maxn=2e5+10;
const int maxm=1e6+10;
int n,m,p[maxn],pos[maxn]; ll ans[maxm];
int st[maxn],ml[maxn],mr[maxn],top=0,tot=0;
vector<pair<int,int> > vec[maxn]; pair<int,int> b[maxn]; 
void chkmax(int &x,int y){ x=x>y?x:y; }
void chkmin(int &x,int y){ x=x<y?x:y; }
struct Info{
    ll s,hs; int len;
}info[maxn<<2];
struct Tag{
    ll ad,had;
}tag[maxn<<2];
Info operator + (Info a,const Info b){ return {a.s+b.s,a.hs+b.hs,a.len+b.len}; }
Info operator + (Info a,Tag b){ return {a.s+b.ad*a.len,a.hs+b.had*a.len,a.len}; }
Tag operator + (Tag a,Tag b){ return {a.ad+b.ad,a.had+b.had}; }
struct SegmentTree{
    #define ls (p<<1)
    #define rs (p<<1|1)
    #define mid (l+r>>1)
    void pushup(int p){ info[p]=info[ls]+info[rs]; }
    void upd(int p,Tag z){ info[p]=info[p]+z; tag[p]=tag[p]+z; }
    void pushdown(int p){
        upd(ls,tag[p]); upd(rs,tag[p]);
        tag[p]={0,0};
    }
    void build(int p,int l,int r){
        if(l==r){ info[p]={0,0,1}; return ; }
        build(ls,l,mid); build(rs,mid+1,r); pushup(p);
    }
    void modify(int p,int l,int r,int ql,int qr,Tag z){
        if(ql<=l&&r<=qr){ upd(p,z); return ; }
        pushdown(p);
        if(ql<=mid) modify(ls,l,mid,ql,qr,z);
        if(qr>mid) modify(rs,mid+1,r,ql,qr,z);
        pushup(p);
    }
    Info query(int p,int l,int r,int ql,int qr){
        if(ql<=l&&r<=qr) return info[p];
        pushdown(p); Info res={0,0};
        if(ql<=mid) res=res+query(ls,l,mid,ql,qr);
        if(qr>mid) res=res+query(rs,mid+1,r,ql,qr);
        return res;
    }
}seg;
struct Q{
    int l,r,v,id;
}; vector<Q> qu[maxn];
struct Add{
    int l,r,v;
}; vector<Add> ad[maxn];
int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n>>m; seg.build(1,1,n);
    for(int i=1;i<=n;i++) cin>>p[i];
    for(int i=1;i<=n;i++) pos[p[i]]=i;
    st[top=1]=0;
    for(int i=1;i<=n;i++){
        while(p[i]>p[st[top]]&&top>1) top--;
        ml[i]=st[top]+1; st[++top]=i; 
    }
    st[top=1]=n+1;
    for(int i=n;i>=1;i--){
        while(p[i]>p[st[top]]&&top>1) top--;
        mr[i]=st[top]-1; st[++top]=i;
    }
    for(int i=1;i*i<n;i++){
        for(int j=1;j*i<=n;j++){
            if(i>=j) continue;
            int p1=pos[i],p2=pos[j],p3=pos[i*j];
            if(min(p1,p2)<ml[p3]||max(p1,p2)>mr[p3]) continue;
            int L=min(min(p1,p2),p3),R=max(max(p1,p2),p3);
            vec[p3].pb(L,-R);
        }
    }
    for(int i=1;i<=n;i++){
        if(!vec[i].size()) continue;
        sort(vec[i].begin(),vec[i].end()); 
        reverse(vec[i].begin(),vec[i].end());
        int l=i+1,r=mr[i]+1;
        for(auto z:vec[i]){
            int ql=z.fi,qr=-z.se;
            if(ql<l&&qr<r){
                ad[ml[i]].pb((Add){qr,r-1,1});
                ad[ql+1].pb((Add){qr,r-1,-1});
            }
            chkmin(l,ql); chkmin(r,qr);
        }
    }
    for(int i=1;i<=m;i++){
        int l,r; cin>>l>>r;
        qu[l-1].pb((Q){l,r,-1,i});
        qu[r].pb((Q){l,r,1,i});
    }
    seg.build(1,1,n); int T=0;
    for(int i=1;i<=n;i++,T++){
        for(auto z:ad[i]) seg.modify(1,1,n,z.l,z.r,Tag{z.v,T*z.v});
        for(auto z:qu[i]){
            Info res=seg.query(1,1,n,z.l,z.r);
            ans[z.id]+=z.v*(res.s*(T+1)-res.hs);
        }
    }
    for(int i=1;i<=m;i++) cout<<ans[i]<<"\n";
    return 0;
}