[IAMOI R1] 家庭矛盾题解

wangshulin · 2024-12-14 17:34:32 · 题解

暴力

合法区间的右端点是连续的，暴力树状数组递推求逆序对即可。
特殊性质 A：

若存在合法区间，区间左端点固定为 l_{k}，区间右端点必定是 [l_{k},n] 种任意一个数，所以从后往前递推树状数组求每种可能的 l_{k} 对应的答案即可。

后面所有讲解都要用的前置性质

设右端点的取值范围为 [L,R]，显然 c_{L}=1，\forall i \in [L+1,R],c_{i}=0，又显然 [L,R] 的取值最多只有 n 种，因为整个 [1,n] 的区间是由若干个不重合的 [L,R] 区间拼成的，所以我们将询问按其对应的 [L,R] 分类。

设 f(l,r) 为区间 [l,r] 的逆序对个数，贡献可以分为了三部分：

左部分区间：f(l,L-1)。
右部分区间：\sum_{i=L}^{R} f(L,i)。
两区间之间：\sum_{i=L}^{R} \sum_{j=l}^{L-1} \sum_{k=L}^{i}[a_{j}>a_{k}]。

两区间之间的贡献的求法
对序列进行分块，对于每一个块用树状数组预处理其和每个区间 [L,R] 之间的贡献，是 O(n \sqrt n \log n) 的，查询时先遍历整块求所有整块的贡献和，剩下残块的贡献用类似的方法用树状数组求，是 O(n \sqrt n \log n) 的。
特殊性质 C：

每个区间 [L,R] 的长度都为 1，所以直接比较，不需要树状数组维护。
发现如上算法中，一共有 O(n) 次加入，和 O(n \sqrt n) 次查询，这显然可以用根号平衡——使用 O(\sqrt n) 加入，O(1) 查询的分块数据结构即可。

左区间贡献的求法
特殊性质 B：

左区间的 c_{i} 是全 0 段，且右端点为 n 或右边一位的 c_{i} 为 1，性质和右区间的出现相似，所以可以参考下文右区间贡献的求法。
左区间是固定区间，相当于求区间逆序对，可以用莫队暴力 O(n\sqrt m \log n) 做，可跑过 n \le 5 \times 10^{4} 的点。
特殊性质 D：

这个特殊性质下的左区间的左端点和右端点都是递增的，意味着不需要做 O(n \sqrt m) 次莫队更新，只需要 O(m) 递推，时间复杂度降到 O(n \log n)。
## 右区间贡献的求法
特殊性质 C:

右区间长度为 1，不需要处理其贡献。
所有右区间拥有共同的左端点，参考性质 A 的方法。

最终时间复杂度即优化为 O(n\sqrt m+n\sqrt n)。

上述题解中存在两种贡献的求解需要从带 \log 优化到不带 \log，但是根据测试数据的强度看选手只需要会其中一个就足以通过了（我们又不是 Ynoi，真的卡不掉啊！）

code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=200010,B=500,CB=(N+B-1)/B;
int n,m,cq,clis,a[N],c[N],sc[N],lis[N],bel[N],lef[CB],rig[CB];
ll g[N],ans[N],fl[N],fr[N],sfl[N],sfr[N],Id[N<<2],cnt[CB][N];
vector<int> gId[N];
vector<ll> ansl[N],ansr[N];
vector<pair<int,int>> gl[N],gr[N];
int qbel(int x){
    return (x+B-1)/B;
}
int qlef(int x){
    return max(0,B*(x-1)+1);
}
int qrig(int x){
    return min(n,B*x);
}
namespace DS{
    struct BIT{
        ll t[N];
        void clear(){
            memset(t,0,sizeof(t));
        }
        int lowbit(int x){
            return x&-x;
        }
        void add(int k,ll x){
            for(int i=k;i<=n;i+=lowbit(i)) t[i]+=x;
        }
        ll query(int k){
            ll s=0;
            for(int i=k;i;i-=lowbit(i)) s+=t[i];
            return s;
        }
        ll query(int l,int r){
            if(l>r) return 0;
            else return query(r)-query(l-1);
        }
    }tr;
    struct BLC{
        ll val[N],tag[CB];
        void clear(){
            memset(val,0,sizeof(val));
            memset(tag,0,sizeof(tag));
        }
        void add(int k,ll x){//单点加——O(\sqrt n)
            for(int i=k;i<=rig[bel[k]];i++) val[i]+=x;
            for(int i=bel[k]+1;i<=bel[n];i++) tag[i]+=x;
        }
        ll query(int l){//前缀查询——O(1)
            return val[l]+tag[bel[l]];
        }
        ll query(int l,int r){
            if(l>r) return 0;
            else return query(r)-query(l-1);
        }
    }blc;
};
struct query{
    int x,d,l,r;
}p[N];
struct MO_query{
    int l,r,Id;
    bool operator<(const MO_query &o)const{
        if(bel[l]!=bel[o.l]) return bel[l]<bel[o.l];
        else{
            if(bel[l]&1) return r<o.r;
            else return r>o.r;
        }
    }
}q[N];
void PART_1(){
    DS::tr.clear();
    DS::blc.clear();
    int L,R,cnt;
    ll res;
    sort(q+1,q+cq+1);
    L=1,R=0,cnt=0;
    for(int i=1;i<=cq;i++){
        if(R<q[i].r) gr[L-1].push_back({R+1,q[i].r}),ansr[L-1].push_back(0),Id[++cnt]=ansr[L-1].size()-1,R=q[i].r;
        if(L>q[i].l) gl[R].push_back({q[i].l,L-1}),ansl[R].push_back(0),Id[++cnt]=ansl[R].size()-1,L=q[i].l;
        if(R>q[i].r) gr[L-1].push_back({q[i].r+1,R}),ansr[L-1].push_back(0),Id[++cnt]=ansr[L-1].size()-1,R=q[i].r;
        if(L<q[i].l) gl[R].push_back({L,q[i].l-1}),ansl[R].push_back(0),Id[++cnt]=ansl[R].size()-1,L=q[i].l;
    }
    for(int i=0;i<=n;i++){
        if(i){
            fr[i]=DS::blc.query(a[i]+1,n);
            DS::blc.add(a[i],1);
            fl[i]=DS::blc.query(a[i]-1);
            sfl[i]=sfl[i-1]+fl[i];
            sfr[i]=sfr[i-1]+fr[i];
        }
        for(int j=0;j<gl[i].size();j++){
            for(int k=gl[i][j].first;k<=gl[i][j].second;k++) ansl[i][j]+=DS::blc.query(a[k]-1);
        }
        for(int j=0;j<gr[i].size();j++){
            for(int k=gr[i][j].first;k<=gr[i][j].second;k++) ansr[i][j]+=DS::blc.query(a[k]+1,n);
        }
    }
    L=1,R=0,cnt=0,res=0;
    for(int i=1;i<=cq;i++){
        if(R<q[i].r) res+=(sfr[q[i].r]-sfr[R])-ansr[L-1][Id[++cnt]],R=q[i].r;
        if(L>q[i].l) res+=ansl[R][Id[++cnt]]-(sfl[L-1]-sfl[q[i].l-1]),L=q[i].l;
        if(R>q[i].r) res-=(sfr[R]-sfr[q[i].r])-ansr[L-1][Id[++cnt]],R=q[i].r;
        if(L<q[i].l) res-=ansl[R][Id[++cnt]]-(sfl[q[i].l-1]-sfl[L-1]),L=q[i].l;
        ans[q[i].Id]+=res*(p[q[i].Id].r-p[q[i].Id].l+1);
    }
}
void PART_2(){
    DS::tr.clear();
    DS::blc.clear();
    for(int l=1,r;l<=n;l=r+1){//预处理计算块完整/不完整时的贡献——O(n\log n)
        for(r=l;r<=n&&sc[r]==sc[l];r++) ;
        r--;
        ll t=0;
        for(int j=r;j>=l;j--){
            t+=DS::tr.query(a[j]-1);
            DS::tr.add(a[j],r-j+1);
        }
        g[l]=t;
        for(int j=l;j<=r;j++){//从 l 到 r 删除
            t-=DS::tr.query(a[j]-1);//去除 a_{j} 往后贡献的逆序对
            if(j<r) g[j+1]=t;
            DS::tr.add(a[j],-(r-j+1));
        }
    }
    for(int i=1;i<=bel[n];i++){//开始计算 [1,l-1] 和 [l,r] 之间的贡
        for(int j=lef[i];j<=rig[i];j++) DS::blc.add(a[j],1);
        for(int l=1,r;l<=n;l=r+1){
            for(r=l;r<=n&&sc[r]==sc[l];r++) ;
            r--;
            if(rig[i]>=l) continue;
            for(int j=l;j<=r;j++) cnt[i][l]+=DS::blc.query(a[j]+1,n)*(r-j+1);
        }
        for(int j=lef[i];j<=rig[i];j++) DS::blc.add(a[j],-1);
    }
    for(int l=1,r;l<=n;l=r+1){//开始计算 [1,l-1] 和 [l,r] 之间的贡献
        for(r=l;r<=n&&sc[r]==sc[l];r++) ;
        r--;
        for(int i=l;i<=r;i++) DS::blc.add(a[i],r-i+1);
        for(auto i:gId[l]){
            if(p[i].x>=p[i].l){
                ans[i]=g[p[i].x];
                continue;
            }
            ans[i]+=g[p[i].l];
            if(bel[p[i].x]==bel[p[i].l-1]){
                for(int j=p[i].x;j<=p[i].l-1;j++) ans[i]+=DS::blc.query(a[j]-1);
            }else{
                for(int j=p[i].x;j<=rig[bel[p[i].x]];j++) ans[i]+=DS::blc.query(a[j]-1);
                for(int j=bel[p[i].x]+1;j<bel[p[i].l-1];j++) ans[i]+=cnt[j][l];
                for(int j=lef[bel[p[i].l-1]];j<=p[i].l-1;j++) ans[i]+=DS::blc.query(a[j]-1);
            }
        }
        for(int i=l;i<=r;i++) DS::blc.add(a[i],-(r-i+1));
    }
}
int main(){
//  freopen("data.in","r",stdin);
//  freopen("data.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++) bel[i]=qbel(i);
    for(int i=1;i<=bel[n];i++) lef[i]=qlef(i),rig[i]=qrig(i); 
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a[i],&c[i]);
        lis[i]=a[i];
        sc[i]=sc[i-1]+c[i];
    }
    sort(lis+1,lis+n+1);
    clis=unique(lis+1,lis+n+1)-lis-1;
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(lis+1,lis+clis+1,a[i])-lis;
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&p[i].x,&p[i].d);
        p[i].l=lower_bound(sc+1,sc+n+1,sc[p[i].x-1]+p[i].d)-sc;
        p[i].r=upper_bound(sc+1,sc+n+1,sc[p[i].x-1]+p[i].d)-sc-1;
//      printf("%lld %lld\n",p[i].l,p[i].r);
        if(p[i].r<=p[i].x) continue;
        if(p[i].x<=p[i].l-1&&p[i].l<=p[i].r) q[++cq].l=p[i].x,q[cq].r=p[i].l-1,q[cq].Id=i;
        if(p[i].l<=p[i].r) gId[p[i].l].push_back(i);
    }
    PART_1();
    PART_2();
    for(int i=1;i<=m;i++){
        printf("%lld\n",ans[i]);
    }
    return 0;
}

[IAMOI R1] 家庭矛盾 题解

暴力

后面所有讲解都要用的前置性质

两区间之间的贡献的求法

左区间贡献的求法

上述题解中存在两种贡献的求解需要从带 \log 优化到不带 \log，但是根据测试数据的强度看选手只需要会其中一个就足以通过了（我们又不是 Ynoi，真的卡不掉啊！）

code

[IAMOI R1] 家庭矛盾题解