题解：P3374 【模板】树状数组 1

二维偏序大意

给定一个序列

a, b

，对每个

i

，求出所有

j

，使得

a _ {i}

\leq

a _ {j}

，

b _ {i}

\leq

b _ {j}

。

如何做哪？

排序预处理
序列的顺序不会影响答案，所以先排序（以 $a$ 作为第一关键字， $b$ 作为第二关键字）。
归并框架
所有符合条件的 $j$ $j$ 一定在 $i$ $i$ 之前（因为只有 $i$ $i$ 前的 $j$ $j$ 才满足 $a _ {i}$ $a_{i}$ $\leq$ $\leq$ $a _ {j}$ $a_{j}$ ，并在 $a _ {i}$ $a_{i}$ $=$ $=$ $a _ {i}$ $a_{i}$ 时 $b _ {i}$ $b_{i}$ $\leq$ $\leq$ $b _ {j}$ $b_{j}$ ）。
对序列进行归并排序，分治时存在三种情况：
- 情况 1： $i, j$ 都在左边 → 递归左半部分。
- 情况 2： $i, j$ 都在右边 → 递归右半部分。
- 情况 3： $j$ 在左， $i$ 在右 → 左半部分对右半部分产生贡献（步骤与归并排序求逆序对类似）。

本题解法

将所有操作（包括初始序列）视为一个序列：
- 初始序列和添加操作 $\to$ 操作 1 。
- 查询操作拆分为两个子操作：
求 $[1, x-1]$ 的前缀和 $\to$ 操作 2 。
求 $[1, y]$ 的前缀和 $\to$ 操作 3 。
排序规则：
- 第一关键字： $pos$ （操作下标）。
- 第二关键字： $type$ （操作类型，操作 1 在前）。

代码实现

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;

struct GG{
    int type,pos,v; // type:1-修改 2-减查询 3-加查询
    bool operator <(const GG &t)const{
        if(pos==t.pos) return type<t.type;
        return pos<t.pos;
    }
}q[N],tmp[N];

int n,m,idx=0,qidx=0,ans[N];

void CDQ(int l,int r){
    if(l==r) return ;
    int mid=(l+r)>>1;
    CDQ(l,mid),CDQ(mid+1,r);
    int k=0,i=l,j=mid+1,sum=0;
    while(i<=mid&&j<=r){
        if(q[i]<q[j]){
            if(q[i].type==1) sum+=q[i].v;
            tmp[k++]=q[i++];
        }else{
            if(q[j].type==2) ans[q[j].v]-=sum;
            if(q[j].type==3) ans[q[j].v]+=sum;
            tmp[k++]=q[j++];
        }
    }
    while(i<=mid) tmp[k++]=q[i++];
    while(j<=r){
        if(q[j].type==2) ans[q[j].v]-=sum;
        if(q[j].type==3) ans[q[j].v]+=sum;
        tmp[k++]=q[j++];
    }
    for(int i=0,j=l;j<=r;i++,j++) q[j]=tmp[i];
    return ;
}

int main(){
    std::ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1,x;i<=n;i++){
        cin>>x;
        q[++idx]={1,i,x};
    }
    while(m--){
        int op,x,y;
        cin>>op>>x>>y;
        if(op==1){
            q[++idx]={1,x,y};
        }else{
            qidx++;
            q[++idx]={2,x-1,qidx}; // 前缀减查询
            q[++idx]={3,y,qidx}; // 前缀加查询
        }
    }
    CDQ(1,idx);
    for(int i=1;i<=qidx;i++) cout<<ans[i]<<endl;
    return 0;
}

题解：P3374 【模板】树状数组 1

文章操作

二维偏序大意

如何做哪？

本题解法

代码实现

相关推荐

评论

题解：P3374 【模板】树状数组 1