Differencia (归并树)

归并树，与我们原学过的归并排序是一样的原理，但是在那个的基础上进行扩展应用。首先每个节点储存了它每个节点所代表的点的有序序列，还有就是每个点里面包含的所有的b[i]在左右子树的排名辅助更新数据，还有一个用来记录当前节点a[] >b[] 的数量的num。这时候查询的话就是线段树查询了，然后更新，首先求出要更新进去的点在原本数组的排名，然后就可以将该数据更新进去范围里面的lazy数组了，那么这时候lazy数组怎么使用？其实你这个lazy数组就是你更新进来的数据在确定范围内的一个排名，那么你这个排名就是a[] > b[] 的数量了。当然不可能更新所有的节点，所以需要使用lazydown的方法优化时间。

#include<bits/stdc++.h>

#define debug 0

#define Lson (rt << 1)

#define Rson ((rt << 1) | 1)

#define M ((l + r) / 2)

using namespace std;

const long long mod  = 1e9 + ;

const int maxn = ;

int T, n, m, ans, last, cnt, L, R, X;

int a[maxn], b[maxn], st[maxn * ], en[maxn * ], lazy[maxn * ], num[maxn * ];

int pl[maxn * ], pr[maxn * ], pool[maxn * ];

void Build(int l, int r, int rt){

    lazy[rt] = -;

    if(l == r){

        st[rt] = ++cnt;en[rt] = cnt;

        pool[cnt] = b[l];

        num[rt] = (a[l] >= b[l]);

        return ;

    }

    Build(l, M, Lson);Build(M + , r, Rson);

    num[rt] = num[Lson] + num[Rson];

    int leftL = st[Lson], leftR = en[Lson];

    int rightL = st[Rson], rightR = en[Rson];

    st[rt] = cnt + ;

    while(leftL <= leftR && rightL <= rightR)pool[++cnt] = ((pool[leftL] <= pool[rightL]) ? pool[leftL ++] : pool[rightL ++]);

    while(leftL <= leftR)pool[++cnt] = pool[leftL ++];

    while(rightL <= rightR)pool[++cnt] = pool[rightL ++];

    en[rt] = cnt;

    leftL = st[Lson], rightL = st[Rson];

    for(int i = st[rt]; i <= en[rt]; i ++){

        while(leftL <= leftR && pool[leftL] <= pool[i]) leftL ++;

        while(rightL <= rightR && pool[rightL] <= pool[i]) rightL ++;

        pl[i] = leftL - ; pr[i] = rightL - ;

        if(pl[i] < st[Lson]) pl[i] = ;

        if(pr[i] < st[Rson]) pr[i] = ;

    }

}

void Lazy(int rt, int pos){

    num[rt] = pos ? pos - st[rt] +  : ;

    lazy[rt] = pos;

}

void Pushdown(int rt){

    if(lazy[rt] == -) return ;

    int pos = lazy[rt];

    Lazy(Lson, pl[pos]);

    Lazy(Rson, pr[pos]);

    lazy[rt] = -;

}

int erfen(int x){

    int l = st[], r = en[], ans = ;

    while(l <= r){

        if(pool[M] <= x){ ans = M; l = M + ;}

        else r = M - ;

    }

    return ans;

}

void query(int l, int r, int rt){

    if(L <= l && r <= R){

        last += num[rt];

        return ;

    }

    Pushdown(rt);

    if(L <= M) query(l, M, Lson);

    if(R > M) query(M + , r, Rson);

    num[rt] = num[Lson] + num[Rson];

}

void Update(int l, int r, int pos, int rt){

    if(L <= l && r <= R){

        Lazy(rt, pos);return ;

    }

    Pushdown(rt);

    if(L <= M) Update(l, M, pl[pos], Lson);

    if(R >  M) Update(M + z1, r, pr[pos], Rson);

    num[rt] = num[Lson] + num[Rson];

}

int AA,BB,CC = ~(<<),MM = (<<) - ;

int rnd(){

    AA = ( + (last >> )) * (AA&MM) + (AA >> );

    BB = ( + (last >> )) * (BB&MM) + (BB >> );

    return (CC & ((AA << ) + BB)) % ;

}

int main(){

    int n,m;

    scanf("%d", &T);while(T --){

        ans = last = cnt = ;

        scanf("%d%d%d%d", &n, &m, &AA, &BB);

        for(int i = ; i <= n; i ++) scanf("%d",&a[i]);

        for(int i = ; i <= n; i ++) scanf("%d",&b[i]);

        Build(, n, );

        for(int i = ; i <= m; i ++){

            L = rnd()%n + ; R = rnd()%n + ; X = rnd() + ;

            if(L > R)swap(L, R);

            if((L + R + X) & )

                Update(, n, erfen(X), );

            else{

                last = ;

                query(, n, );

                ans = (1LL * i * last % mod + ans) % mod;

            }

        }

        printf("%d\n",ans);

    }

    return ;

}

巴特西

Differencia (归并树)

最新文章

热门文章