题解：P11625 [迷宫寻路 Round 3] 迷宫寻路大赛

· · 题解

吐槽：这个题目和题半毛钱关系都没有

思考一下逆序对的性质，不难发现，对于一个区间，固定右端点 r，然后对于左端点 l，不难发现随着 l 的增加，逆序对数量是单调不增的。

注意到这个条件和题目似乎和题目有点关联。

我们考虑对于每一个 i，将其看做右端点，然后我们考虑去维护其左端点的一个范围 l\in [L_i,R_i]，即在这个范围内的区间 [l,r] 都满足题目中的 c \le \text{INV} \le d 的条件。

基于逆序对的性质，我们可考虑使用双指针来完成这件事。

我们设当前双指针的两个端点为 l,r，设 sum_1 表示 [l,i] 的逆序对的数量，sum_2 表示 [r,j] 的逆序对的数量。

注意到我们应该让 sum_1 达到刚好满足 \le d 的条件，让 sum_2 达到刚好满足 \ge c 的条件。

逆序对数量可以用树状数组进行维护。

然后考虑如何求解答案。

注意到可以离线来做，类似于二维数点，用一个权值线段树维护即可。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=5e5+10;
int n,q,p=1,lim,a[MAXN],L[MAXN],R[MAXN];
int l=1,r=1;
ll sum1=0,sum2=0,c,d,ans[MAXN];
struct Bit_Tree{ll c[MAXN],siz;}B1,B2;
namespace BIT{
    inline void update(Bit_Tree &tree,int pos,int x){
        if (x==1)tree.siz++;else tree.siz--;
        for (int i=pos;i<=lim;i+=(i&(-i)))tree.c[i]+=x;
    }
    inline ll query(Bit_Tree &tree,int pos){
        ll res=0;
        for (int i=pos;i;i-=(i&(-i)))res+=tree.c[i];
        return res;
    }
}
struct Seg_Tree{ll sum,tag;}tree[MAXN<<2];
namespace SEG{
    inline void push_up(int rt){tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;}
    inline void push_down(int rt,int l_len,int r_len){
        if (tree[rt].tag){
            tree[rt<<1].tag+=tree[rt].tag,tree[rt<<1|1].tag+=tree[rt].tag;
            tree[rt<<1].sum+=l_len*tree[rt].tag,tree[rt<<1|1].sum+=r_len*tree[rt].tag;
            tree[rt].tag=0;
        }
    }
    inline void update(int rt,int l,int r,int L,int R,ll x){
        if (L<=l&&r<=R)return tree[rt].sum+=(r-l+1)*x,tree[rt].tag+=x,void();
        int mid=(l+r)>>1;
        push_down(rt,mid-l+1,r-mid);
        if (L<=mid)update(rt<<1,l,mid,L,R,x);
        if (R>mid)update(rt<<1|1,mid+1,r,L,R,x);
        push_up(rt);
    }
    inline ll query(int rt,int l,int r,int L,int R){
        if (L<=l&&r<=R)return tree[rt].sum;
        int mid=(l+r)>>1;ll res=0;
        push_down(rt,mid-l+1,r-mid);
        if (L<=mid)res+=query(rt<<1,l,mid,L,R);
        if (R>mid)res+=query(rt<<1|1,mid+1,r,L,R);
        return res;
    }
}
struct Node{int l,r,id;}po[MAXN];
namespace yixing{
    inline bool cmp(const Node a1,const Node a2){return a1.r<a2.r;}
    inline void Main(){
        cin>>n>>c>>d;
        for (int i=1;i<=n;i++)cin>>a[i],lim=max(lim,a[i]);
        for (int i=1;i<=n;i++){
            sum1+=B1.siz-BIT::query(B1,a[i]),sum2+=B2.siz-BIT::query(B2,a[i]);
            BIT::update(B1,a[i],1),BIT::update(B2,a[i],1);
            while (sum1>d){
                BIT::update(B1,a[l],-1);
                sum1-=BIT::query(B1,a[l]-1);
                l++;
            }
            while (sum2>=c){
                BIT::update(B2,a[r],-1);
                sum2-=BIT::query(B2,a[r]-1);
                r++;
            }
            L[i]=l,R[i]=r-1;
        }
        cin>>q;
        for (int i=1;i<=q;i++)cin>>po[i].l>>po[i].r,po[i].id=i;
        sort(po+1,po+1+q,cmp);
        for (int i=1;i<=n;i++){
            if (L[i]<=R[i])SEG::update(1,1,lim,L[i],R[i],1);
            while (p<=q&&po[p].r<=i){
                ans[po[p].id]=SEG::query(1,1,lim,po[p].l,po[p].r);
                p++;
            }
        }
        for (int i=1;i<=q;i++)cout<<ans[i]<<"\n";
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    yixing::Main();
    return 0;
}