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

· · 题解

为什么泥萌欺负cdq分治，呜呜呜

泥萌都不写cdq！

这么好的二维偏序模板题怎么能没有cdq呢，是时候来篇搞搞了

我们都知道，cdq分治在处理操作题（非模板偏序题）是基于时间的分治算法，换句话来说，我们的第一维--时间已经有序

那么合并的时候就只需要按照修改位置合并就好了

然后把询问操作拆成两个前缀查询，S[r] - S[l -1]

至于具体实现，我们可以这么搞

struct Node{
    int opt , id , v;
    Node(int opt = 0 , id = 0 , v = 0) {}
};
$opt = 2$时，$id$代表遇上了一个左端点，也就是$L - 1$，而$v$代表它是第几个询问 $opt = 3$时，$id$代表遇上了一个右端点，也就是$R$，而$v$代表它是第几个询问 --- 那么我们如果按照$id$合并，对于每个点，它前面的所有点都应当是满足时间轴上在它前面，操作的位置也在它前面。所以对于点$i$，如果它是$1$操作，那么它后面的所有操作的答案都应当加上$v$。$2$，$3$操作泥萌可以自己想想。因为是最重要的。 想完再看下去哦！ $2$操作的话，我们就把第$v$个询问的答案减去它前面的增加 $3$操作的话，我们就把第$v$个询问的答案加上他前面的增加 --- $Code 
#include<iostream>
#include<cstdio>
#define mid ((l + r) >> 1)
using namespace std;

const int MAXN = 5e5 + 5;

struct Node{
    int opt , id , v;
    Node(int opt = 0 , int id = 0 , int v = 0) : opt(opt) , id(id) , v(v) {}
    #define opt(i) A[i].opt
    #define id(i) A[i].id
    #define v(i) A[i].v
};

int n , m , cnt , qry , ans[MAXN];
Node A[MAXN << 1] , tmp[MAXN << 1];

inline void insert(int opt , int id , int v) {A[++cnt] = Node(opt , id , v);}

void cdq(int l , int r) {
    if(l >= r) return ;
    cdq(l , mid); cdq(mid + 1 , r);
    int pos1 = l , pos2 = mid + 1 , sum = 0;
    for(int tot = l ; tot <= r ; ++tot) {
        //pos1 入队 
        if((id(pos1) <= id(pos2) && pos1 <= mid) || pos2 > r) {
            if(opt(pos1) == 1) //那么后面的所有询问操作都应该受到它的影响 
                sum += v(pos1);
            //至于其它的opt，证明它是询问，一个询问对后面应该没有任何影响 
            tmp[tot] = A[pos1++];
        }
        //pos2 入队  
        else {
            if(opt(pos2) == 2)//它入队了，证明后面的无论所有东西都对我没有任何关系了，因为id一定比我小，时间轴也在我后面，我肯定不会被那些修改而影响 
                ans[v(pos2)] -= sum;
            else if(opt(pos2) == 3)//同上
                ans[v(pos2)] += sum; 
            //至于其它的opt，证明它是修改，那么修改对它前面 
            tmp[tot] = A[pos2++];
        }
    }
    for(int i = l ; i <= r ; ++i) A[i] = tmp[i];
}

int main() {
    scanf("%d %d" , &n , &m);
    for(int i = 1 , x ; i <= n ; ++i) {
        scanf("%d" , &x);
        insert(1 , i , x);
    }
    for(int i = 1 , opt , x , k ; i <= m ; ++i) {
        scanf("%d %d %d" , &opt , &x , &k);
        if(opt == 1) insert(1 , x , k);
        else {
            insert(2 , x - 1 , ++qry);
            insert(3 , k , qry);
        }   
    }
    cdq(1 , cnt);
    for(int i = 1 ; i <= qry ; ++i) printf("%d\n" , ans[i]);
    return 0;
}

最后说一句，左闭右闭大法好！