A simple Blog for wyx I've been down the bottle hoping.
CDQ分治总结和习题
发表于: | 分类: Oi | 评论:0 | 阅读:45

翻以前的课件,发现了宋爷的 $CDQ$ 课件,想到过两天 $Infinity37$ 要讲树套树,决定先写点这玩意……省着以后彻底忘了

先说一下 $CDQ$ 是干啥的吧,这算法是用来处理一系列离线问题的……可以省下来一层树形结构
这玩意常数小还好写,经常处理一堆三维偏序的问题,说白了就是两个东西有三个不一样的地方都要求按照特定的顺序
核心思想应该时(按时间)排序
具体做法通常是先拿第一个关系排个序,然后把它分成两部分,再分别按照第二个关系排个序,然后拿个数据结构维护一下第三维…………

###二维Lis
给定一个长度为$N$的序列$S$,$S$的每个元素$p_i$是一个二元组$(x_i,y_i)$
定义$p_i<p_j$当且仅当$x_i<x_j$并且$y_i<y_j$
求S的最长上升子序列长度

先按照x排个序,再按照y排个序,然后树状数组维护一下$pos$就行了

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int N = 20000+5;
#define lowbit(x) ((x)&(-x))
using namespace std;
 
int F[N],tr[N];
 
struct data
{
    int x,y,pos;
    bool operator<(const data &z)const
    {
        return y < z.y;
    }
}a[N];
 
bool cmp1(const data &a,const data &b)
{
    return a.x < b.x;
}
 
inline int read()
{
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}
 
void change(int x,int tt)
{
    while(x < N)
    {
        tr[x] = max(tr[x],tt);
        x += lowbit(x);
    }
}
 
int ask(int x)
{
    int ans = 0;
    while(x){
        ans = max(ans,tr[x]);
        x -= lowbit(x);
    }
    return ans;
}
 
void Tchange(int x)
{
    while(x < N)
    {
        tr[x] = 0;
        x  += lowbit(x);
    }
}
 
void solve(int L,int R)
{
    if(L==R) return;
    int mid = (L+R) >> 1;
    solve(L,mid);
    sort(a+L,a+mid+1);
    sort(a+mid+1,a+R+1);
    for(int i=L,j=mid+1;j<=R;++j)
    {
        while(a[i].y <= a[j].y && i <= mid)
        {
            change(a[i].pos,F[a[i].pos]);
            i ++;
        }
        F[a[j].pos] = max(F[a[j].pos],ask(a[j].pos)+1);
    }
    for(int i=L;i<=mid;++i) Tchange(a[i].pos);
    sort(a+L+1,a+R+1,cmp1);
    solve(mid+1,R);
}
 
int main()
{
    int n = read();
    for(int i=1;i<=n;++i) a[i].x = read(), a[i].y = read(), a[i].pos = i,F[i] = 1;
    sort(a+1,a+n+1,cmp1);
    solve(1,n);int ans = 0;
    for(int i=1;i<=n;++i) ans = max(ans,F[i]);
    cout << ans << endl;
}

###3295: [Cqoi2011]动态逆序对
对于序列$A$,它的逆序对数定义为满足$i<j$,且$A_i>A_j$的数对$(i,j)$的个数。给1到$n$的一个排列,按照某种顺序依次删除$m$个元素,你的任务是在每次删除一个元素之前统计整个序列的逆序对数。
基本一样吧
先按照$pos$排序,然后按照$x$排序,树状数组处理$y$
但是要注意,第二部在$y$相同的时候,要按照$pos$排一下,要不然会有更新不到的问题


树套树标准卡常


CDQ小常数代码短

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
typedef long long LL;
#define lowbit(x) ((x)&(-x))
const int N = 1e6;
using namespace std;
LL ans;
int tr[N+5];

void change(int x,int tt)
{
    while(x <= N)
    {
        tr[x] += tt;
        x += lowbit(x);
    }
}

int ask(int x)
{
    int ans = 0;
    while(x)
    {
        ans += tr[x];
        x -= lowbit(x);
    }
    return ans;
}

void Tchange(int x)
{
    while(x <= N)
    {
        tr[x] = 0 ;
        x += lowbit(x);
    }
}

struct data
{
    int x,times;
    int pos,tmp;
    bool operator < (const data &z)const
    {
        return pos < z.pos;
    }
}a[N+5];

bool cmp1(const data &a,const data &b)
{
    return a.times ^ b.times ? a.times > b.times : a.pos < b.pos;
}

bool cmp2(const data &a,const data &b)
{
    return a.times < b.times;
}

void solve(int L,int R)
{
    if(L==R) return;
    int mid = (L+R) >> 1;
    solve(L,mid);
    sort(a+L,a+mid+1);
    sort(a+mid+1,a+R+1);
    for(int i=L,j=mid+1;j<=R;++j)
    {
        while(a[i].pos < a[j].pos &&  i <= mid) 
        {
            change(a[i].x,1);
            i ++;
        }
        a[j].tmp += ask(N) - ask(a[j].x);
    }
    for(int i=L;i<=mid;++i) Tchange(a[i].x);
    for(int i=mid,j=R;j>=mid+1;--j)
    {
        while(a[i].pos > a[j].pos && i >= L)
        {
            change(a[i].x,1);
            i --;
        }
        a[j].tmp += ask(a[j].x);
    }
    for(int i=L;i<=mid;++i) Tchange(a[i].x);
    sort(a+L,a+R+1,cmp1);
    solve(mid+1,R);
}

int T[N+5];

inline int read()
{
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int main()
{
    int n = read(), m = read();
    for(int i=1;i<=n;++i) a[i].x = read(), a[i].times = m + 1, T[a[i].x] = a[i].pos = i;
    LL ans = 0;
    for(int i=1;i<=n;++i)
    {
        ans = ans + ask(N) - ask(a[i].x);
        change(a[i].x,1);
    }

    memset(tr,0,sizeof tr);
    for(int i=1;i<=m;++i)
    {
        int x = read();
        a[T[x]].times = i;
    }

    sort(a+1,a+n+1,cmp1);
    solve(1,n);
    sort(a+1,a+n+1,cmp2);
    for(int i=1;i<=m;++i)
    {
        printf("%lld\n",ans);
        ans -= a[i].tmp;
    }
}

###3262: 陌上花开
有n朵花,每朵花有三个属性:花形(s)、颜色(c)、气味(m),又三个整数表示。现要对每朵花评级,一朵花的级别是它拥有的美丽能超过的花的数量。定义一朵花A比另一朵花B要美丽,当且仅当$Sa>=Sb,Ca>=Cb,Ma>=Mb$。显然,两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。

直接三维偏序就行了
但是要注意相同元素可以直接化成一个,然后每次插入的时候直接插入$cnt$就行了


另附传说中树套树的大常数实践证明

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int N = 200000+5;
#define lowbit(x) ((x)&(-x))
using namespace std;

struct data
{
    int x,y,z,cnt;
    int ans;
    friend bool operator == (const data &a,const data &b)
    {
        return a.x == b.x && a.y == b.y && a.z == b.z;
    }
    bool operator < (const data &tmp)const
    {
        if(x != tmp.x) return x < tmp.x;
        else if(y != tmp.y) return y < tmp.y;
        else return z < tmp.z;
    }
    friend bool operator != (const data &a,const data &b)
    {
        return !(a==b);
    }
}a[N];

inline char getc()
{
    static const int LEN = 1<<15;
    static char buf[LEN],*S=buf,*T=buf;
    if(S == T)
    {
        T = (S=buf)+fread(buf,1,LEN,stdin);
        if(S == T)return EOF;
    }
    return *S++;
}
 
inline int read()
{
    static char ch;
    static int D;
    while(!isdigit(ch=getc()));
    for(D=ch-'0'; isdigit(ch=getc());)
        D=(D<<3)+(D<<1)+(ch-'0');
    return D;
}
 

bool cmp1(const data &a,const data &b)
{
    return a.y ^ b.y ? a.y < b.y : a.z < b.z;
}

int tr[N];

void change(int x,int tt)
{
    while(x < N)
    {
        tr[x] += tt;
        x += lowbit(x); 
    }
}

int ask(int x)
{
    int ans = 0;
    while(x)
    {
        ans += tr[x] ;
        x -= lowbit(x);
    }
    return ans;
}

void Tchange(int x)
{
    while(x < N)
    {
        tr[x] = 0;
        x += lowbit(x);
    }
}

void solve(int L,int R)
{
    if(L==R){
        a[L].ans += a[L].cnt - 1;
        return; 
    }
    int mid = (L+R) >> 1;
    solve(L,mid);
    solve(mid+1,R);
    sort(a+L,a+mid+1,cmp1);
    sort(a+mid+1,a+R+1,cmp1);
    for(int i=L,j=mid+1;j<=R;++j)
    {
        while(a[i].y <= a[j].y && i <= mid){
            change(a[i].z,a[i].cnt);
            i ++;
        }
        a[j].ans += ask(a[j].z);
    }
    for(int i=L;i<=mid;++i) Tchange(a[i].z);
}

int T[N];

int main()
{
    int n = read(), k = read();
    for(int i=1;i<=n;++i) a[i].x = read(), a[i].y = read(), a[i].z = read() ,a[i].cnt = 1;
    sort(a+1,a+n+1);
    int tt = 0;
    for(int i=1;i<=n;++i) 
        if(a[i] != a[i-1]) a[++tt] = a[i]; 
        else a[tt].cnt ++;
    solve(1,tt);
    for(int i=1;i<=tt;++i) T[a[i].ans] += a[i].cnt;
    for(int i=0;i<n;++i)
        printf("%d\n",T[i]);
}

###1176: [Balkan2007]Mokia
维护一个$W*W$的矩阵,初始值均为S.每次操作可以增加某格子的权值,或询问某子矩阵的总权值.修改操作数$M\le 160000$,询问数$Q\le 10000,W\le 2000000$.
时间序显然把
把一个询问拆成四个
先按照时间序排一下,然后分成两坨,这两坨再按照$y$排一下,然后两个指针扫一下,如果左指针的纵坐标比他小或者纵坐标相同但是横坐标小于等于他,就处理左边的
然后查询一下
最后一起搞答案就行了

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#define lowbit(x) ((x)&(-x))
const int N = 2000000+5;
const int M = N;
using namespace std;

int tr[N];
int T[M];

void change(int x,int tt)
{
    while(x < N)
    {
        tr[x] += tt;
        x += lowbit(x);
    }
}

int ask(int x)
{
    int ans = 0;
    while(x)
    {
        ans += tr[x];
        x -= lowbit(x);
    }
    return ans;
}

void Tchange(int x)
{
    while(x < N)
    {
        tr[x] = 0;
        x += lowbit(x);
    }
}

struct data
{
    int x,y,times,ans,opt,tmp;
    bool operator < (const data &z)const
    {
        if(times != z.times) return times < z.times;
        if(y != z.y) return y < z.y;
        return x < z.x;
    }
}a[N];

bool cmp1(const data &a,const data &b)
{
    if(a.y != b.y) return a.y < b.y;
    else if(a.x != b.x) return a.x < b.x;
    else return a.times < b.times;
}

void solve(int L,int R)
{
    if(L==R) return;
    int mid = (L+R) >> 1;
    solve(L,mid);
    sort(a+L,a+mid+1,cmp1);
    sort(a+mid+1,a+R+1,cmp1);
    for(int i=L,j=mid+1;j<=R;++j)
    {
        while((a[i].y < a[j].y || ((a[i].y == a[j].y) && (a[i].x <= a[j].x))) && (i <= mid))
        {
            change(a[i].x,a[i].tmp);
            i ++;
        }
        if(a[j].opt != 1)
            a[j].ans += ask(a[j].x);
    }
    for(int i=L;i<=mid;++i) Tchange(a[i].x);
    sort(a+L,a+R+1);
    solve(mid+1,R);
}


inline char getc()
{
    static const int LEN = 1<<15;
    static char buf[LEN],*S=buf,*T=buf;
    if(S == T)
    {
        T = (S=buf)+fread(buf,1,LEN,stdin);
        if(S == T)return EOF;
    }
    return *S++;
}
 
inline int read()
{
    static char ch;
    static int D;
    while(!isdigit(ch=getc()));
    for(D=ch-'0'; isdigit(ch=getc());)
        D=(D<<3)+(D<<1)+(ch-'0');
    return D;
}
 

bool F[N];

int main()
{
    read(),read();
    int cnt = 0,tt=0;
    while(1)
    {
        cnt ++;
        int opt = read();
        if(opt == 3) break;
        else if(opt == 1)
        {
            int x = read()+1, y = read()+1, A = read();
            ++tt; a[tt].x = x , a[tt].y = y, a[tt].times = cnt;
            a[tt].opt = 1, a[tt].tmp = A;
        }
        else
        {
            F[cnt] = 1;
            int x1 = read()+1, y1 = read()+1, x2 = read()+1, y2 = read()+1;
            ++tt ; a[tt].x = x1-1 , a[tt].y = y1-1 , a[tt].times = cnt,a[tt].opt =2;
            ++tt ; a[tt].x = x2 , a[tt].y = y2 , a[tt].times = cnt,a[tt].opt =2;
            ++tt ; a[tt].x = x1-1 , a[tt].y = y2 , a[tt].times = cnt,a[tt].opt =3;
            ++tt ; a[tt].x = x2 , a[tt].y = y1-1 , a[tt].times = cnt,a[tt].opt =3;
        }
    }
    sort(a+1,a+tt+1);
    solve(1,tt);

    for(int i=1;i<=tt;++i)
    {
        if(a[i].opt == 2) T[a[i].times] += a[i].ans;
        else T[a[i].times] -= a[i].ans;
    }
    for(int i=1;i<=cnt;++i)
        if(F[i])
            printf("%d\n",T[i]);
}

总之需要注意的细节就是排序……排序……排序……
四维偏序的里面来树套树
还可以树链剖分+cdq+线段树
先这样吧 ,剩下的没写完呢 ,随时更新吧QAQ

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP