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

· · 题解

[IAMOI R1] 家庭矛盾

由于 c_i \ge 0 ，因此所有可能的 r 肯定构成了一个连续的区间。设这个区间是 (L,R] ，并设 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,R) = \sum\limits_{l \le i < j \le R} [a_i > a_j] (R-j+1) = (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 就行了。对于后半部分做法类似，只需要当莫队往右扩展时，将逆序对数乘上 r 。而当莫队往左扩展时，只需要新开一个 \rm BIT 和分块前缀和，其中每个数的权值是他的下标。

视 n,m 同阶，则复杂度为 O(n \sqrt{n}) 。

#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;
}