【算法】cdq分治&整体二分

这两天学了学cdq分治和整体二分,感觉世界真奇妙
这两个东西用处就是在离线的时候代替恶心的树套树(然而有的时候还不如树套树好调emmmm),通过分治将询问修改按照一定顺序进行并且求出答案
cdq分治是一种用来解决偏序问题的好办法,归并排序就是一个cdq分治的个例,所以学过归并排序理解这里就会强很多。所谓偏序就是形如a.x < b.x a.y < b.y这种关系。当然小于号可以换成大于号,也可以不止两个不等式,有多个维度多个不等式。最多的一般是三维偏序。对于三维偏序,我们一般先会按照关键字顺序排个序(首先保证第一关键字有序),之后剩下两个维度,我们再像归并排序进行,不过一般不能直接归并,需要其他的数据结构来去维护。但是这样我们就将一些本来只有二维数据结构才能解决的问题通过cdq分治强行压掉一维,代码上要好写很多,而且常数也小了
放例题
luogu P3157[CQOI2011]动态逆序对
这个题就是一个典型的cdq分治,我们现在考虑原来的逆序对,实际上就是一个a.x < b.x a.y > b.y的二维偏序,支持删除操作后,我们又多了个新的关键字——被修改时间。然后删除挺烦人的,我们将删除变为插入,将操作倒过来,这样我们每次新插入一个值,三个关键字(被修改时间t,原序列位置pos,数字大小num)他们的关系就是a.t < b.t a.pos < b.pos a.num > b.num
那么这就是一个典型的三维偏序,预处理t,排序,然后按照归并做后面两个维度,用线段树/树状数组维护

// luogu-judger-enable-o2
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define ri register int

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = (x << 1) + (x << 3) + a - '0', a = getchar();
    if(b == 1)
        x *= -1;
}

const int ms = 100010;

int n, m, lx, ta, tail, sta[ms], a[ms], pos[ms];

lo ans[ms];

bool flag[ms];

struct in
{
    int t, pos, num; bool fl;//那么对于这个题目,我们设加入序列时间为t,位置为pos,数字大小为num,现在求a.t < b.t a.pos < b.pos a.num > b.num的个数 
}ter[ms], lin[ms];

struct es
{
    int l, r, v;
}ing[ms << 2];

inline bool cmpt(in a, in b)
{
    return a.t < b.t;//首先按照t排序,保证cdq分治中这一维度不会产生影响 
}

inline void up(int w)
{
    ing[w].v = ing[w << 1].v + ing[w << 1 | 1].v;
}

inline void insert(int w, int l, int v)//值域线段树,维护某段值域上的数的个数 
{
    if(ing[w].l == l && ing[w].r == l)
    {
        ing[w].v = (v == 0) ? 0 : (ing[w].v + v); return;
    }
    int mid = (ing[w].l + ing[w].r) >> 1;
    if(l <= mid)
        insert(w << 1, l, v);
    else
        insert(w << 1 | 1, l, v);
    up(w);
}

int ask(int w, int l, int r)//值域线段树查询 
{
    if(l > r)
        return 0;
    if(ing[w].l == l && ing[w].r == r)
        return ing[w].v;
    int mid = (ing[w].l + ing[w].r) >> 1;
    if(r <= mid)
        return ask(w << 1, l, r);
    else if(l > mid)
        return ask(w << 1 | 1, l, r);
    else
        return ask(w << 1, l, mid) + ask(w << 1 | 1, mid + 1, r);
}

void merge(int l, int r)//cdq分治具体过程 
{
    if(l == r)
        return;
    int mid = (l + r) >> 1, ll = l, rr = mid + 1, ta = l; lo d;
    merge(l, mid), merge(mid + 1, r);//先处理好两侧 
    while(ll <= mid && rr <= r)//对于t我们事先排序了,并不影响答案 
    {
        if(ter[ll].pos < ter[rr].pos)//然后我们就把它转化成一个二维的偏序问题了,这个时候和归并差不多,只是需要线段树维护 
            lin[ta ++] = ter[ll ++], insert(1, ter[ll - 1].num, 1);//每次先去pos小的,这是第二维 
        else//否则把答案处理下 
            ans[ter[rr].t] += (d = ask(1, ter[rr].num + 1, n)), lin[ta ++] = ter[rr ++];//要记住按哪维度记录答案!! 
    }
    while(ll <= mid)//把没进行完的操作进行完 
        lin[ta ++] = ter[ll ++], insert(1, ter[ll - 1].num, 1);
    while(rr <= r)
        ans[ter[rr].t] += (d = ask(1, ter[rr].num + 1, n)), lin[ta ++] = ter[rr ++];
    for(ri i = l; i <= mid; i ++)//删除每个点对线段树的影响 
        insert(1, ter[i].num, 0);
    for(ri i = l; i <= r; i ++)//把改好的序列放回去 
        ter[i] = lin[i];
    for(ri i = r; i >= l; i --)//我们不仅要正向考虑,还要反向考虑,即a.t > b.t a.pos > b.pos a.num < b.num 
    {
        if(ter[i].t <= mid)
            insert(1, ter[i].num, 1);
        else
            ans[ter[i].t] += (d = ask(1, 1, ter[i].num));
    }
    for(ri i = l; i <= r; i ++)//依然记得清空 
        insert(1, ter[i].num, 0);
}

inline void build(int w, int l, int r)//线段树建树 
{
    ing[w] = (es){l, r, 0};
    if(l == r)
        return;
    int mid = (l + r) >> 1;
    build(w << 1, l, mid), build(w << 1 | 1, mid + 1, r);
}

int main()
{
    re(n), re(m); int ci = n; ta = m;
    for(ri i = 1; i <= n; i ++)
        re(a[i]), pos[a[i]] = i;
    for(ri i = 1; i <= m; i ++)//首先我们逆向考虑,倒序看删除,即为插入 
        re(lx), flag[lx] = 1, ter[i] = (in){ci --, pos[lx], lx}, sta[++ tail] = lx;
    for(ri i = 1; i <= n; i ++)
        if(flag[a[i]] == 0)//这些一开始就插入的肯定时间要早 
            ter[++ ta] = (in){ci -- , i, a[i]};//对于答案,现在有3个因素影响,加入序列的时间,在序列中的位置,数字大小 
    sort(ter + 1, ter + 1 + n, cmpt), build(1, 1, n);
    merge(1, n);
    lo pri = 0;
    for(ri i = 1; i <= n; i ++)
        pri += ans[i];
    for(ri i = n; i >= n - m + 1; i --)
        printf("%lld\n", pri), pri -= ans[i];
}

luogu P3810【模板】三维偏序(陌上花开)
这个题和刚才那个题目基本一样,就是需要去个重这样的,但是我的代码只能在luogu拿到90分,因为剩下一个点mle,但是我在本机测那个点,只用了17m空间,bzoj上也通过了……所以我就精神ac了233333333333

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define ri register long long

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

inline void re(lo &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = (x << 1) + (x << 3) + a - '0', a = getchar();
    if(b == 1)
        x *= -1;
}

const int ms = 200010;

lo n, k, tre[ms], a[ms], lx, ly, lz, tot;

lo f[ms];

struct in
{
    lo a, b, c, cnt, ans;
}ter[ms], lin[ms];

inline bool cmpa(in a, in b)//这个题和刚才那个一样,只不过求的是顺序对 
{
    if(a.a != b.a)//依然要分关键字 
        return a.a < b.a;
    if(a.b != b.b)
        return a.b < b.b;
    if(a.c != b.c)
        return a.c < b.c;
}

inline lo lowbit(lo x)
{
    return x & (-x);
}

inline void add(lo x, lo v)
{
    while(x <= k)
        tre[x] += v, x += lowbit(x);
}

inline lo ask(lo x)
{
    lo rt = 0;
    while(x > 0)
        rt += tre[x], x -= lowbit(x);
    return rt;
}

inline void merge(lo l, lo r)
{
    if(l == r)//这个地方因为对于相同的操作来说,答案增加了cnt-1,一共会有cnt个cnt-1的答案 
    {
        ter[l].ans += ter[l].cnt - 1; return;
    }
    lo mid = (l + r) >> 1, ta = l;
    merge(l, mid), merge(mid + 1, r);
    for(ri i = l, j = mid + 1; i <= mid ||j <= r;)//压缩了下合并方式 
    {
        if(j > r || (i <= mid && ter[i].b <= ter[j].b))
            add(ter[i].c, ter[i].cnt), lin[ta ++] = ter[i ++];
        else
            ter[j].ans += ask(ter[j].c), lin[ta ++] = ter[j ++];
    }
    for(ri i = l; i <= mid; i ++)//删除…… 
        add(ter[i].c, -ter[i].cnt);
    for(ri i = l; i <= r; i ++)
        ter[i] = lin[i];
}

int main()
{
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
    re(n), re(k);
    for(ri i = 1; i <= n; i ++)
        re(lx), re(ly), re(lz), ter[i] = (in){lx, ly, lz, 1, 0};
    sort(ter + 1, ter + 1 + n, cmpa); 
    for(ri i = 1; i <= n; i ++)//因为存在重复的情况,所以要去重 
    {
        if(ter[i].a != ter[i - 1].a || ter[i].b != ter[i - 1].b || ter[i].c != ter[i - 1].c)
            lin[++ tot] = ter[i], lin[tot].cnt = 1;
        else
            lin[tot].cnt ++;
    }
    for(ri i = 1; i <= tot; i ++)
        ter[i] = lin[i];
    merge(1, tot);
    for(ri i = 1; i <= tot; i +P3332 [ZJOI2013]K大数查询+)
        f[ter[i].ans] += ter[i].cnt;
    for(ri i = 0; i < n; i ++)
        printf("%lld\n", f[i]);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

cdq分治就是这两道题了,有空再做……
整体二分,这个东西和cdq分治的思想也是类似的,我每次对询问二分答案,对于大于这个答案的我就丢到右区间,反之左区间,直到最后答案边界相同为止
至于中间怎么维护……还是要用线段树之类的数据结构了23333333
luogu P3332[ZJOI2013]K大数查询

// luogu-judger-enable-o2
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<map>
#define ri register int
#define debug(x) cout<<#x<<":"<<x<<endl
using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

inline void re(lo &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = gch()))
        b = a == '-';
    while(isdigit(a))
        x = (x << 1) + (x << 3) + a - '0', a = gch();
    if(b == 1)
        x = -x;
}

const lo ms = 100010;

lo la, lb, lc, ld, n, m, pri[ms];

struct in
{
    lo type, a, b, c, ans, pos;
}ter[ms], lx[ms << 1], ly[ms << 1];

struct es
{
    lo l, r, add, s;
}ing[400040];

inline void down(lo w)//下放标记 
{
    lo f = ing[w].add; ing[w].add = 0;
    ing[w << 1].add += f, ing[w << 1 | 1].add += f;
    ing[w << 1].s += (ing[w << 1].r - ing[w << 1].l + 1) * f;
    ing[w << 1 | 1].s += (ing[w << 1 | 1].r - ing[w << 1 | 1].l + 1) * f;
}

inline void up(lo w)//更新 
{
    ing[w].s = ing[w << 1].s + ing[w << 1 | 1].s;
}

void change(lo w, lo l, lo r, lo v)//维护一个区间线段树,记录区间内出现多少数 
{
    if(ing[w].l == l && ing[w].r == r)
    {
        ing[w].s += (ing[w].r - ing[w].l + 1) * v, ing[w].add += v; return;
    }
    lo mid = (ing[w].l + ing[w].r) >> 1; down(w);
    if(r <= mid)
        change(w << 1, l, r, v);
    else if(l > mid)
        change(w << 1 | 1, l, r, v);
    else
        change(w << 1, l, mid, v), change(w << 1 | 1, mid + 1, r, v);
    up(w);
}

inline void build(lo w, lo l, lo r)//建树 
{
    ing[w] = (es){l, r, 0, 0};
    if(l == r)
        return;
    lo mid = (l + r) >> 1;
    build(w << 1, l, mid), build(w << 1 | 1, mid + 1, r);
}

lo ask(lo w, lo l, lo r)//线段树查询 
{
    if(ing[w].l == l && ing[w].r == r)
        return ing[w].s;
    lo mid = (ing[w].l + ing[w].r) >> 1, rt = 0;
    down(w);
    if(r <= mid)
        rt = ask(w << 1, l, r);
    else if(l > mid)
        rt = ask(w << 1 | 1, l, r);
    else
        rt = ask(w << 1, l, mid) + ask(w << 1 | 1, mid + 1, r);
    up(w); return rt;
} 

void merge(lo s, lo t, lo l, lo r)//s t二分值域,l r二分询问 
{
    if(s == t)//如果值域答案确定,相应询问也确定了 
    {
        for(ri i = l; i <= r; i ++)
            if(ter[i].type == 2)
                ter[i].ans = s;
        return;
    }
    lo mid = (s + t) >> 1, ll = 0, rr = 0, lin;
    for(ri i = l; i <= r; i ++)
    {
        if(ter[i].type == 1)
        {
            if(ter[i].c <= mid)//对于插入的数比二分的答案较小的,这对于答案为mid以上的没有贡献,放左边 
                lx[++ ll] = ter[i];
            else//否则放在右边 
                change(1, ter[i].a, ter[i].b, 1), ly[++ rr] = ter[i];
        }
        if(ter[i].type == 2)
        {
            lin = ask(1, ter[i].a, ter[i].b);
            if(lin < ter[i].c)//同理,当查询的数排名靠后,我们就把它放在左区间 
                ter[i].c -= lin, lx[++ ll] = ter[i];
            else//否则放在右区间 
                ly[++ rr] = ter[i];
        }
    }
    for(ri i = l; i <= r; i ++)//清空线段树 
        if(ter[i].c > mid && ter[i].type == 1)
            change(1, ter[i].a, ter[i].b, -1);
    bool fa = 0, fb = 0;
    for(ri i = 1; i <= ll; i ++)//重新丢回原来数组 
        ter[i + l - 1] = lx[i], fa = 1;
    for(ri i = 1; i <= rr; i ++)
        ter[i + ll + l - 1] = ly[i], fb = 1;
    if(fa)//剪枝 
        merge(s, mid, l, l + ll - 1);
    if(fb)
        merge(mid + 1, t, l + ll, r);
}

int main()
{
    re(n), re(m); build(1, 1, n);
    for(ri i = 1; i <= m; i ++)
        re(la), re(lb), re(lc), re(ld), ter[i] = (in){la, lb, lc, ld, 0, i};
    merge(-n, n, 1, m);
    for(ri i = 1; i <= m; i ++)
        pri[ter[i].pos] = ter[i].ans;
    for(ri i = 1; i <= m; i ++)
        if(pri[i] != 0)
            printf("%d\n", pri[i]);
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注