专栏文章

题解：P11763 [IAMOI R1] 家庭矛盾

__abcd_
P11763题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miq6sy6o
此快照首次捕获于
2025/12/03 23:54
3 个月前
此快照最后确认于
2025/12/03 23:54
3 个月前
查看原文

[IAMOI R1] 家庭矛盾

由于 ci≥0c_i \ge 0，因此所有可能的 rr 肯定构成了一个连续的区间。设这个区间是 (L,R](L,R]，并设 f(l,R)=∑r=lR∑l≤i<j≤r[ai>aj]f(l,R) = \sum\limits_{r=l}^R \sum\limits_{l \le i < j \le r} [a_i > a_j]，那么答案就是 f(l,R)−f(l,L)f(l,R) - f(l,L)，因此可以拆成两个询问。
考虑如何处理 f(l,R)f(l,R)。显然 f(l,R)=∑l≤i<j≤R[ai>aj](R−j+1)f(l,R) = \sum\limits_{l \le i < j \le R} [a_i > a_j] (R-j+1) =(R+1)∑l≤i<j≤R[ai>aj]−∑l≤i<j≤R[ai>aj]j= (R+1) \sum\limits_{l \le i < j \le R} [a_i > a_j] - \sum\limits_{l \le i < j \le R} [a_i > a_j] j
前半部分直接上 Yuno loves sqrt technology II 就行了。对于后半部分做法类似，只需要当莫队往右扩展时，将逆序对数乘上 rr。而当莫队往左扩展时，只需要新开一个 BIT\rm BIT 和分块前缀和，其中每个数的权值是他的下标。
视 n,mn,m 同阶，则复杂度为 O(nn)O(n \sqrt{n})。
CPP
#include<bits/stdc++.h>
#define ll long long
#define pn putchar('\n')
#define mset(a,x) memset(a,x,sizeof a)
#define mcpy(a,b) memcpy(a,b,sizeof a)
#define all(a) a.begin(),a.end()
#define fls() fflush(stdout)
#define int ll
using namespace std;
int re()
{
    int x=0;
    bool t=1;
    char ch=getchar();
    while(ch>'9'||ch<'0')
        t=ch=='-'?0:t,ch=getchar();
    while(ch>='0'&&ch<='9')
        x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return t?x:-x;
}
const int maxn=1e5+5;
struct Qry
{
    int l,r,i,ad;
};
int n,Q,m,B;
int a[maxn],b[maxn];
int pf[maxn],pf2[maxn],sf[maxn];
int ans[maxn],ans1[maxn*4],ans2[maxn*4];
vector<Qry>qry;
vector<tuple<int,int,int>>qry1[maxn],qry2[maxn];
struct BIT
{
    int tree[maxn];
    void add(int x,int ad)
    {
        for(int i=x;i<=n;i+=i&-i)
            tree[i]+=ad;
    }
    int qry(int x)
    {
        int ret=0;
        for(int i=x;i;i-=i&-i)
            ret+=tree[i];
        return ret;
    }
}bit,bit2;
struct Block
{
    int n,B;
    int a[maxn],b[maxn];
    void clr()
    {
        mset(a,0);
        mset(b,0);
    }
    void add(int x,int ad)
    {
        int k=x/B;
        for(int i=x;i<k*B+B&&i<=n;i++)
            a[i]+=ad;
        for(int i=k+1;i*B<=n;i++)
            b[i]+=ad;
    }
    int qry(int x)
    {
        return a[x]+b[x/B];
    }
}blk,blk2;
void lsh()
{
    vector<int>b;
    for(int i=1;i<=n;i++)
        b.push_back(a[i]);
    sort(all(b));
    b.erase(unique(all(b)),b.end());
    for(int i=1;i<=n;i++)
        a[i]=lower_bound(all(b),a[i])-b.begin()+1;
    blk.n=blk2.n=b.size();
    blk.B=blk2.B=sqrt(b.size());
}
signed main()
{
    n=re();
    for(int i=1;i<=n;i++)
    {
        a[i]=re();
        b[i]=b[i-1]+re();
    }
    lsh();
    Q=re();
    for(int i=1;i<=Q;i++)
    {
        int l=re();
        int k=b[l-1]+re();
        int r=lower_bound(b+1,b+1+n,k)-b-1;
        if(r>=l)
            qry.push_back({l,r,i,-1});
        r=upper_bound(b+1,b+1+n,k)-b-1;
        if(r>=l)
            qry.push_back({l,r,i,1});
    }
    B=sqrt((double)n*n/Q)+1;
    sort(all(qry),[](Qry x,Qry y){return x.l/B==y.l/B?x.r<y.r:x.l<y.l;});
    int L=1,R=0;
    for(auto [l,r,i,ad]:qry)
    {
        if(l<L)
        {
            m++;
            qry1[R].push_back({l,L-1,m});
            L=l;
        }
        if(R<r)
        {
            m++;
            qry2[L].push_back({R+1,r,m});
            R=r;
        }
        if(L<l)
        {
            m++;
            qry1[R].push_back({L,l-1,m});
            L=l;
        }
        if(r<R)
        {
            m++;
            qry2[L].push_back({r+1,R,m});
            R=r;
        }
    }
    for(int i=1;i<=n;i++)
    {
        bit.add(a[i]+1,1);
        bit2.add(a[i]+1,i);
        pf[i]=bit.qry(a[i]);
        pf2[i]=bit2.qry(a[i]);
    }
    for(int i=1;i<=n;i++)
    {
        blk.add(a[i],1);
        blk2.add(a[i],i);
        for(auto [l,r,j]:qry1[i])
        {
            for(int k=l;k<=r;k++)
            {
                ans1[j]+=blk.qry(a[k]-1)-pf[k];
                ans2[j]+=blk2.qry(a[k]-1)-pf2[k];
            }
        }
    }
    mset(bit.tree,0);
    blk.clr();
    for(int i=n;i;i--)
    {
        bit.add(a[i],1);
        sf[i]=n-i+1-bit.qry(a[i]);
    }
    for(int i=n;i;i--)
    {
        blk.add(a[i],1);
        for(auto [l,r,j]:qry2[i])
        {
            for(int k=l;k<=r;k++)
            {
                int t=n-i+1-blk.qry(a[k])-sf[k];
                ans1[j]+=t;
                ans2[j]+=t*k;
            }
        }
    }
    L=1,R=0;
    m=0;
    int c1=0,c2=0;
    for(auto [l,r,i,ad]:qry)
    {
        if(l<L)
        {
            m++;
            c1+=ans1[m];
            c2+=ans2[m];
            L=l;
        }
        if(R<r)
        {
            m++;
            c1+=ans1[m];
            c2+=ans2[m];
            R=r;
        }
        if(L<l)
        {
            m++;
            c1-=ans1[m];
            c2-=ans2[m];
            L=l;
        }
        if(r<R)
        {
            m++;
            c1-=ans1[m];
            c2-=ans2[m];
            R=r;
        }
        ans[i]+=((r+1)*c1-c2)*ad;
    }
    for(int i=1;i<=Q;i++)
        printf("%lld\n",ans[i]);
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...