题解 P8078 [WC2022] 秃子酋长

FZzzz · 2022-03-22 21:19:30 · 题解

怎么题解区全是莫队，来发 2log 的正解。

考虑分治，每次处理跨过中间点的询问。把两边的部分拉出来排序，考虑若右边有两个位置 i 和 j（a_i<a_j）在排序后是相邻的，它们会产生怎样的贡献。

• 若左边有 a_i 和 a_j 之间的数，那么一定是从 i 走到左边，走走走再走回 j，这样贡献是 i+j；
• 否则，就是从 i 直接走到 j，这样贡献是 |i-j|。

对于最大值和最小值也是类似，考虑左边有没有比它大或者小的。

考虑改写第一种贡献成立的条件。找到分治中点左边最靠右的 a_i 和 a_j 之间的数，那么第一种贡献的条件就是询问左端点在这个位置左边，这是一个一维数点。

对询问的右端点做扫描线，每次插入或删除一个数会插入和删除 O(1) 对这样的 (i,j)，相当于我们做动态一维数点，树状数组维护。对于左边的对的贡献也类似维护即可。

更新这样的 (i,j) 需要支持找到当前插入或删除的数的前驱和后继，并支持在另一边找到第一个在某个区间内的数。前者可以 set 维护，后者可以线段树。

但是这样常数很大，也可以右端点从右往左，左端点从左往右，这样只需要删数，可以归并排序和链表维护。

时间复杂度 O(n\log^2n+m\log n)，如果你用链表的话瓶颈就是动态一维数点，n 和 m 同阶时可以平衡到 O\left(\dfrac{n\log^2n}{\log\log n}\right)。

下面的代码是 2log，提交时和题解提交时可以排到最优解第一并且碾压大部分莫队做法。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
inline ll read(){
    ll x=0;
    bool f=0;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-') f=1;
        c=getchar();
    }
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return f?-x:x;
}
const int maxn=5e5+5;
int n,m,a[maxn],p[maxn],ql[maxn],qr[maxn];
ll c[maxn];
void modify(int x,ll k){
    while(x){
        c[x]+=k;
        x-=x&-x;
    }
}
ll query(int x){
    ll s=0;
    while(x<=n){
        s+=c[x];
        x+=x&-x;
    }
    return s;
}
ll ans[maxn];
vector<int> q[maxn];
int ord[maxn],pre[maxn],suc[maxn],mx[maxn];
void solve(int l,int r,vector<int> vec){
    if(l==r){
        ord[r]=a[r];
        return;
    }
    int mid=l+(r-l)/2;
    vector<int> vec1,vec2,vec3;
    for(int i:vec)
        if(qr[i]<=mid) vec1.push_back(i);
        else if(ql[i]>mid) vec2.push_back(i);
        else vec3.push_back(i);
    solve(l,mid,vec1);
    solve(mid+1,r,vec2);
    int c=l;
    suc[0]=ord[mid+1];
    mx[0]=0;
    while(c<=mid&&ord[c]<ord[mid+1])
        mx[0]=max(mx[0],p[ord[c++]]);
    for(int i=mid+1;i<=r;i++){
        pre[ord[i]]=i==mid+1?0:ord[i-1];
        suc[ord[i]]=i==r?n+1:ord[i+1];
        mx[ord[i]]=0;
        while(c<=mid&&ord[c]<suc[ord[i]])
            mx[ord[i]]=max(mx[ord[i]],p[ord[c++]]);
    }
    pre[n+1]=ord[r];
    for(int i:vec3) q[qr[i]].push_back(i);
    ll res=0;
    auto upd1=[&res](int x,int f){
        int y=suc[x];
        if(x&&y<=n){
            res+=abs(p[x]-p[y])*f;
            modify(mx[x],(p[x]+p[y]-abs(p[x]-p[y]))*f);
        }
        else modify(mx[x],(x?p[x]:p[y])*f);
    };
    upd1(0,1);
    for(int i=mid+1;i<=r;i++) upd1(ord[i],1);
    for(int i=r;i>mid;i--){
        for(int j:q[i]) ans[j]=res+query(ql[j]);
        upd1(pre[a[i]],-1);
        upd1(a[i],-1);
        pre[suc[a[i]]]=pre[a[i]];
        suc[pre[a[i]]]=suc[a[i]];
        mx[pre[a[i]]]=max(mx[pre[a[i]]],mx[a[i]]);
        if(i>mid+1) upd1(pre[a[i]],1);
    }
    for(int i=mid+1;i<=r;i++) vector<int>().swap(q[i]);
    c=mid+1;
    suc[0]=ord[l];
    mx[0]=0;
    while(c<=r&&ord[c]<ord[l]) mx[0]=max(mx[0],n+1-p[ord[c++]]);
    for(int i=l;i<=mid;i++){
        pre[ord[i]]=i==l?0:ord[i-1];
        suc[ord[i]]=i==mid?n+1:ord[i+1];
        mx[ord[i]]=0;
        while(c<=r&&ord[c]<suc[ord[i]])
            mx[ord[i]]=max(mx[ord[i]],n+1-p[ord[c++]]);
    }
    pre[n+1]=ord[mid];
    for(int i:vec3) q[ql[i]].push_back(i);
    auto upd2=[&res](int x,int f){
        int y=suc[x];
        if(x&&y<=n){
            res+=abs(p[x]-p[y])*f;
            modify(mx[x],(-p[x]-p[y]-abs(p[x]-p[y]))*f);
        }
        else modify(mx[x],(x?-p[x]:-p[y])*f);
    };
    upd2(0,1);
    for(int i=l;i<=mid;i++) upd2(ord[i],1);
    for(int i=l;i<=mid;i++){
        for(int j:q[i]) ans[j]+=res+query(n+1-qr[j]);
        upd2(pre[a[i]],-1);
        upd2(a[i],-1);
        pre[suc[a[i]]]=pre[a[i]];
        suc[pre[a[i]]]=suc[a[i]];
        mx[pre[a[i]]]=max(mx[pre[a[i]]],mx[a[i]]);
        if(i<mid) upd2(pre[a[i]],1);
    }
    for(int i=l;i<=mid;i++) vector<int>().swap(q[i]);
    vector<int> tmp;
    c=l;
    for(int i=mid+1;i<=r;i++){
        while(c<=mid&&ord[c]<ord[i]) tmp.push_back(ord[c++]);
        tmp.push_back(ord[i]);
    }
    while(c<=mid) tmp.push_back(ord[c++]);
    for(int i=l;i<=r;i++) ord[i]=tmp[i-l];
}
int main(){
#ifdef LOCAL
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
    n=read();
    m=read();
    for(int i=1;i<=n;i++) p[a[i]=read()]=i;
    for(int i=1;i<=m;i++){
        ql[i]=read();
        qr[i]=read();
    }
    vector<int> vec;
    for(int i=1;i<=m;i++) vec.push_back(i);
    solve(1,n,vec);
    for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);
#ifdef LOCAL
    fprintf(stderr,"%f\n",1.0*clock()/CLOCKS_PER_SEC);
#endif
    return 0;
}

不过我不会告诉你我最开始写了个 set 和线段树的卡了一万年常还 90。