CDQ分治

cdq分治是一类用于离线解决分治区间前后互相影响的分治的技巧,来自于陈丹琦学姐的论文。

它有一个很常用的功能就是降维。经常用于解决偏序问题和dp时为转移提供条件(常用于斜率优化提供单调性)。

降维的方法有很多,例如在处理三维偏序的时候,可以一维排序,一维分治(归并排序),一维数据结构

void cdq(int l, int r) {
    if(l == r) { initialization(); return ; }
    int mid = r + l >> 1;
    workBlock();
}

对于workBlock的写法,大致分为三种,我个人更加倾向先cdq(l, mid),然后统计左边对右边的影响,再cdq右边。

虽然大多数情况先统计哪里无所谓,但是一些最优化dp的转移依赖于上一个状态的更新态,所以这种写法应该是更加普适一点的。

写的时候注意几点

  1. DEBUG时可以看看合并前是否前驱条件都满足了,例如单调性等等,是否已经提前合并好了。
  2. 如果在分治的时候对原数组的关键字相对位置进行了改动,记得下一次cdq的时候改回来。
  3. 如果在cdq内不选择归并而是选择sort(log方了),那重复元素要小心了,因为快排不是一个稳定的排序。2h惨案
  4. 对于重复元素的答案统计要慎重
  5. 为了使传递的参数更加简洁,尽量使分治的一维与数组下标的数据范围是同阶的,尽量选择归并排序,实在不行再sort
  6. dp的时候注意l==r的时候若无值再去赋值。
  7. 注意边界限制
inline void cdq(int l, int r, int op) {
    if(l == r) { init(); return ; }
    int mid = l + r >> 1;
    int l1 = l, l2 = mid + 1;
    REP(i, l, r) {
        if(a[i].id <= mid) tmp[l1 ++] = a[i];
        else tmp[l2 ++] = a[i];
    }
    REP(i, l, r) a[i] = tmp[i];
    cdq(l, mid);

    int j = l;
    ++ cur;
    REP(i, mid + 1, r) {
        while(a[j].x >= a[i].x && j <= mid) upd(a[j].y);
        rlx(f[a[i].id], a[i].y);
    }

    cdq(mid + 1, r);
    l1 = l, l2 = mid + 1;
    REP(i, l, r) {
        if(a[l1].x >= a[l2].x || l2 > r) tmp[i] = a[l1 ++];
        else tmp[i] = a[l2 ++];
    }
    REP(i, l, r) a[i] = tmp[i];

}

另外有一个小技巧,就是如果用的是树状数组处理第三维,那么没有必要再搞一个撤销操作,只需要打一个版本标记就行了:

int bit[N], cur, ver[N];
inline void inc(int x, int val) { 
    for(; x < N; x += x & -x) if(cur == ver[x]) bit[x] += val; 
        else ver[x] = cur, bit[x] = val;
}
inline int qry(int x) { 
    int ret = 0; 
    for(; x > 0; x -= x & -x) if(cur == ver[x]) ret += bit[x]; 
    return ret; 
} 

cdq分治的思想感觉有点妙。

题目

BZOJ 1176 Mokia

点修改,询问子矩阵之和。

考虑每个修改给询问所带来的贡献。

struct info { 
    int num, op, x, y, d, id; 
    info() {}
    info(int _num, int _op, int _x, int _y, int _d, int _id) 
        : num(_num), op(_op), x(_x), y(_y), d(_d), id(_id) {}
  
} que[N], t[N];
 
inline bool operator <(const info a, const info b) {
    return a.x == b.x ? a.y < b.y : a.x < b.x;
}
  
int bit[M], s, n, tot, qn, ans[N], ver, tim[M];
  
inline void add(int x, int val) { for(; x < M; x += x & -x) bit[x] = ver == tim[x] ? (bit[x] + val) : (tim[x] = ver, val); }
inline int qry(int x) { int ret = 0; for(; x; x -= x & -x) ret += (ver == tim[x]) * bit[x]; return ret; }
  
void cdq(int l, int r) {
    if(l == r) return ;
  
    int mid = l + r >> 1;
    int l1 = l, l2 = mid + 1, j;
    REP(i, l, r) { 
        if(que[i].num <= mid) t[l1 ++] = que[i]; 
        else t[l2 ++] = que[i];
    }
    REP(i, l, r) que[i] = t[i];
  
    cdq(l, mid);
    ++ ver;
    j = l;
    REP(i, mid + 1, r) if(que[i].op == 2) {
        for(; que[j].x <= que[i].x && j <= mid; ++ j) if(que[j].op == 1) add(que[j].y, que[j].d); // j <= mid 很重要!!!!
        ans[que[i].id] += que[i].d * qry(que[i].y);
    }
     
    cdq(mid + 1, r);
    l1 = l, l2 = mid + 1;
    REP(i, l, r) {
        if(((que[l1].x <= que[l2].x) || l2 > r) && l1 <= mid) t[i] = que[l1 ++];
        else t[i] = que[l2 ++];
    }
    REP(i, l, r) que[i] = t[i];
  
}
  
int main() {
    s = rd(), n = rd();
  
    for(int op, x, y, a, xx, yy; op != 3; ) {
        op = rd();
        if(op == 1) {
             x = rd(), y = rd(), a = rd();
             que[++ tot] = info(tot, 1, x, y, a, 0);    
        } 
        else if(op == 2) {
            ++ qn;
            x = rd(), y = rd(), xx = rd(), yy = rd();
              
            que[++ tot] = info(tot, 2, xx, yy, 1, qn);
            que[++ tot] = info(tot, 2, xx, y - 1, -1, qn);
            que[++ tot] = info(tot, 2, x - 1, yy, -1, qn);
            que[++ tot] = info(tot, 2, x - 1, y - 1, 1, qn);
        }
    } 
    sort(que + 1, que + tot + 1);
    cdq(1, tot);
  
    REP(i, 1, qn) printf("%d\n", ans[i]);
    return 0;
}

BZOJ 3263 陌上花开

三维偏序,求三个关键字小于某个元素的个数。

用sort偷懒了。

int bit[M], n;
struct info { int s, c, m, ans, id; } a[N], t1[N], t2[N];
bool operator<(const info x, const info y) { return x.s<y.s||(x.s==y.s&&x.m<y.m)||(x.s==y.s&&x.m==y.m&&x.c < y.c); }
bool operator==(const info x, const info y) { return x.s == y.s && x.c == y.c && x.m == y.m; }
int cnt[N], cur, ver[M];
 
inline void add(int x, int val) {
    if(!x) return ;
    for(; x < M; x += x & -x) {
        if(ver[x] == cur) bit[x] += val;
        else bit[x] = val, ver[x] = cur;
    }   
}
inline int qry(int x) {
    int ret = 0;
    for(; x; x -= x & -x) if(ver[x] == cur) ret += bit[x];
    return ret;
}
 
inline bool cmp(const info x, const info y) { return x.m < y.m;  }
void cdq(int l, int r) {
    if(l == r) return ; 
    int mid = l + r >> 1;
     
    cdq(l, mid);
    REP(i, l, mid) t1[i] = a[i];
    sort(t1 + l, t1 + mid + 1, cmp);
    REP(i, mid + 1, r) t2[i] = a[i];
    sort(t2 + mid + 1, t2 + r + 1, cmp);
    ++ cur;
    int j = l;
    REP(i, mid + 1, r) {
        while(j <= mid && (t1[j].m <= t2[i].m)) add(t1[j ++].c, 1);
        a[t2[i].id].ans += qry(t2[i].c);        
    }
    cdq(mid + 1, r);
}
int k;
int main() {
//  freopen("1.in", "r", stdin);
    n = rd(); k = rd();
    REP(i, 1, n) a[i] = (info) { rd(), rd(), rd(), 0, i };
    sort(a + 1, a + n + 1);
    REP(i, 1, n) a[i].id = i;
    cdq(1, n);
    REPD(i, n - 1, 1) 
        if (a[i] == a[i + 1])
            a[i].ans = max(a[i].ans, a[i + 1].ans);
     
    REP(i, 1, n) ++ cnt[a[i].ans];
    REP(i, 0, n - 1) printf("%d\n", cnt[i]); 
    return 0;
}

BZOJ 3295 动态逆序对

题目内容如标题。

三维偏序。考虑每个点加入时带来的贡献

代码可能有点问题。

int bit[N], cur, ver[N];
inline void inc(int x, int val, int op) { 
    for(; (op < 0 ? x > 0 : x < N); x = x + op * (x & -x)) if(cur == ver[x]) bit[x] += val; 
        else ver[x] = cur, bit[x] = val;
}
inline int qry(int x, int op) { 
    int ret = 0; 
    for(; (op < 0 ? x > 0 : x < N); x = x + op * (x & -x)) if(cur == ver[x]) ret += bit[x]; 
    return ret; 
} 
struct que {
    int pos, tim, x;
    que(){ pos = tim = x = 0; }
    que(int _pos, int _tim, int _x) : pos(_pos), tim(_tim), x(_x) {}
} q[N], tmp[N];
bool operator<(const que x, const que y) { return x.tim == y.tim ? x.pos < y.pos : x.tim > y.tim; }
inline int cmp(const que x, const que y) { return x.pos < y.pos; }

int n, Q, ans[N], id[N]; // ans_i 鍦ㄦ洿鏂板墠琛ㄧず鍦ㄥ姞鍏ョi涓厓绱犲緱鍒扮殑璐$尞

# define FUCK(x) cout << #x << ":" << x << endl
void cdq(int l, int r) {
    if(l == r) return;
    
    int mid = l + r >> 1;
    int l1 = l, l2 = mid + 1;
    cdq(l, mid);
    sort(q + l, q + mid + 1);     
    sort(q + mid + 1, q + r + 1);
    ++ cur;
    int j = l;
    REP(i, mid + 1, r) {
        while(q[i].tim <= q[j].tim && j <= mid) inc(q[j ++].x, 1, -1), print(q[j - 1]);
        ans[q[i].tim] += qry(q[i].x + 1, 1);
    }
    ++ cur;
    j = mid + 1;

    REP(i, l, mid) {
        while(q[i].tim <= q[j].tim && j <= r) inc(q[j ++].x, 1, 1), print(q[j - 1]);
        ans[q[i].tim] += qry(q[i].x - 1, -1);
    }
    sort(q + l, q + r + 1, cmp);
    cdq(mid + 1, r);
}

int main() {
    freopen("1.in", "r", stdin);
//  freopen("mine.out", "w", stdout);
    n = rd(), Q = rd();
    REP(i, 1, n) q[i] = que(i, Q + 1, rd()), id[q[i].x] = i;
    REP(i, 1, Q) q[id[rd()]].tim = i; 
    cdq(1, n);
    REPD(i, Q, 1) ans[i] += ans[i + 1];
    REP(i, 1, Q) printf("%d\n", ans[i]);
    return 0;
}

BZOJ 2244 拦截导弹

有两个关键字的最长不上升子序列.求:1.最长不上升子序列的长度 2.随机在最长不上升子序列中选取一个,问某个位置被选中的概率.

一边dp一边cdq,三维偏序。

先离散化。

但是方案数会巨大.....

正解应该是存对数,但是没有卡,double就可以水过。

这题调的我想骂人。

头一次知道有序列点这种东西,这两句话居然是有区别的:

  1. inc(a[j].y, f[a[j].id], 1), -- j;
  2. inc(a[j].y, f[a[j --].id], 1);

有时候Warning还是要看一眼的。

struct info {
    int id, x, y;
    info(){}
    info(int _id, int _x, int _y) : id(_id), x(_x), y(_y) {}
} a[N], tmp[N];
bool cmpup(const info x, const info y) { return x.x == y.x ? (x.y != y.y ? x.y > y.y : x.id < y.id) : x.x > y.x; } 
 
int cur, ver[N], n;
# define pii pair<double, double>
# define mp make_pair
# define fir first
# define sec second
pii f[2][N], bit[N];
# define g g[op]
# define f f[op]
inline void rlx(pii &x, pii y) {
    if(x.fir < y.fir) x = y;
    else if(x.fir == y.fir) x.sec += y.sec;
}
inline void inc(int x, pii val, int op) {
    for(; (op ? x < N : x > 0); x += (op ? 1 : -1) * (x & -x)) 
        if(cur == ver[x]) rlx(bit[x], val);
        else ver[x] = cur, bit[x] = val;
}
 
inline pii qry(int x, int op) {
    pii ret = mp(0, 0);
    for(; (op ? x > 0 : x < N); x += (op ? -1 : 1) * (x & -x)) { if(cur == ver[x]) rlx(ret, bit[x]); }
    return ret;
}
 
inline void cdq(int l, int r, int op, int ty) {
    if(l == r) { 
        rlx(f[a[l].id], mp(1, 1)); // !!!!!!!!!!!!
        return ; 
    }
    int mid = l + r >> 1;
    int l1 = l, l2 = mid + 1;
    REP(i, l, r) {
        if(a[i].id <= mid) tmp[l1 ++] = a[i];
        else tmp[l2 ++] = a[i];
    }
    REP(i, l, r) a[i] = tmp[i];
    if(ty) {
        cdq(mid + 1, r, op, ty);
        int j = r;
        ++ cur;
        REPD(i, mid, l) {
            while(a[j].x <= a[i].x && j >= mid + 1) inc(a[j].y, f[a[j].id], 1), -- j; 
            pii tmp = qry(a[i].y, 1);
            rlx(f[a[i].id], mp(tmp.fir + 1, tmp.sec));
        }
        cdq(l, mid, op, ty);
    }
    else {
        cdq(l, mid, op, ty);
        int j = l;
        ++ cur;
        REP(i, mid + 1, r) { 
            while(a[j].x >= a[i].x && j <= mid) inc(a[j].y, f[a[j].id], 0), ++ j; // !!!!!!!!!!!!!!!!!
            pii tmp = qry(a[i].y, 0);
            rlx(f[a[i].id], mp(tmp.fir + 1, tmp.sec));
        }
        cdq(mid + 1, r, op, ty);
    }
    l1 = l, l2 = mid + 1;
    REP(i, l, r) {
        if((a[l1].x >= a[l2].x || l2 > r) && l1 <= mid) tmp[i] = a[l1 ++];
        else tmp[i] = a[l2 ++];
    }
    REP(i, l, r) a[i] = tmp[i];
}
# undef f
# undef g
bool inn[N];
int lshx[N], lshy[N], tpx, tpy;
int main() {
    n = rd();
    REP(i, 1, n) { 
        a[i] = info(i, rd(), rd());
        lshx[i] = a[i].x, lshy[i] = a[i].y;
    }
    sort(lshx + 1, lshx + n + 1);
    sort(lshy + 1, lshy + n + 1);
    tpx = unique(lshx + 1, lshx + n + 1) - lshx;
    tpy = unique(lshy + 1, lshy + n + 1) - lshy;
    REP(i, 1, n) {
        a[i].x = lower_bound(lshx + 1, lshx + tpx + 1, a[i].x) - lshx;
        a[i].y = lower_bound(lshy + 1, lshy + tpy + 1, a[i].y) - lshy;
    }
    sort(a + 1, a + n + 1, cmpup);
    cdq(1, n, 0, 0);
    cdq(1, n, 1, 1);
    DB mx = 0, ans = 0;
    REP(i, 1, n) mx = max(mx, f[0][a[i].id].fir);//, cout<<"????"<<a[i].id<<" "<<g[0][a[i].id]<<endl; 
 
    printf("%d\n", (int)mx);
    REP(i, 1, n) { 
        if(f[0][i].fir + f[1][i].fir - 1 == mx) inn[i] = 1;
        if(f[0][i].fir == mx) ans += f[0][i].sec;
    }
    REP(i, 1, n) 
        if(inn[i]) printf("%.5lf ", 1.0 * f[0][i].sec * f[1][i].sec / ans);
        else printf("0.00000 ");
    return 0;
}

BZOJ 4025 二分图

每个边有一个出现时间,求时间区间内是否为二分图。

用栈维护并查集的操作,不用路径压缩,路径压缩的均摊分析在树状时间结构中不太起作用。

其实是个线段树分支......

int f[N], sz[N], n, m, T;
bool val[N], ans[N];
  
# define pb push_back
# define mp make_pair
# define fir first
# define sec second
# define pii pair<int, int>
  
# define u tr[x]
# define ls (x << 1)
# define rs (x << 1 | 1)
# define uls tr[ls]
# define urs tr[rs]
  
struct node {
    vector<pii > vec;
} tr[N << 2];
int tp;
pii stk[N];
int gf(int x) { return f[x] == x ? x : gf(f[x]); }
void rec(int pos) {
    while(tp != pos) {
        pii gg = stk[tp --];
        f[gg.fir] = gg.fir, val[gg.fir] = 0;
        sz[gg.sec] -= sz[gg.fir];
    }
}
bool dep(int x) {
    bool ret = 0;
    for(; f[x] != x; x = f[x]) ret ^= val[x];
    return ret;
}
bool merge(int x, int y) { // merge y into x
    int fx = gf(x), fy = gf(y); 
    if(fx != fy) {
        if(sz[fy] > sz[fx]) swap(x, y), swap(fx, fy);
        stk[++ tp] = mp(fy, fx);
        f[fy] = fx, sz[fx] += sz[fy];
        val[fy] = 1 ^ dep(x) ^ dep(y);
        return 1;
    }
    else return (dep(x) ^ dep(y)); //!!!!!!!!!!!!!!!!!!!由于不路径压缩了!!! 
}
//vector<pii > tmp;
void dfs(int x, int l, int r, bool flag) {
    int pos0 = tp;
    for(int i = 0; i < u.vec.size(); ++ i) flag &= merge(u.vec[i].fir, u.vec[i].sec);//, tmp.pb(v); 
    if(!flag) { REP(i, l, r) ans[i] = 0; rec(pos0); return ; }
    if(l == r) { ans[l] = flag; return ; }
    int mid = l + r >> 1;
    dfs(ls, l, mid, flag);
    dfs(rs, mid + 1, r, flag);//, rec(pos1);
    rec(pos0); //!!!!!!!!!!!!
//  for(auto v : u.vec) tmp.pop_back(); 
}
  
void modify(int x, int l, int r, int ql, int qr, pii c) {
    if(l >= ql && r <= qr) { u.vec.pb(c); return ; }
    int mid = l + r >> 1;
    if(ql <= mid) modify(ls, l, mid, ql, qr, c);
    if(qr > mid) modify(rs, mid + 1, r, ql, qr, c);
}
int t; 
int main() {
//  freopen("data1.in", "r", stdin);
//  freopen("mine.out", "w", stdout);
    scanf("%d%d%d", &n, &m, &t);
    REP(i, 1, n) f[i] = i, sz[i] = 1;
    REP(i, 1, m) {
        int a, b, l, r; scanf("%d%d%d%d", &a, &b, &l, &r);
        pii x = mp(a, b);
        if(l + 1 > r) continue; // !!!!!!!!!!!!! 
        modify(1, 1, t, l + 1, r, x);
    }
    dfs(1, 1, t, 1);
    REP(i, 1, t) puts(ans[i] ? "Yes" : "No");
  
    return 0;
}

XSY 忘了题号

以前三月份集训的一个题

求某种意义上的一个lis,发现是一个四维偏序+LIS。

但是实际上没有四维,最后一维的两个限制可以用线段树搞掉,那这题就没了。

代码是初二时候写的。。看起来码风和现在没啥区别(

我还清晰地记得我当时对两个函数取max,用的是宏定义的max,然后我就T飞了。。。卡了好长时间常发现原来是这个问题!!!!!!

struct qwq { int x, y, a, b, w; } p[NR];
int tr[NR << 2], n;
 
#define lson rt << 1
#define rson rt << 1 | 1
 
void modify(int rt, int l, int r, int ql, int qr, int x) {
    if(ql <= l && qr >= r) { tr[rt] = max(tr[rt], x); return ; }
    int mid = (l + r) / 2;
    if(ql <= mid) modify(lson, l, mid, ql, qr, x);
    if(qr > mid) modify(rson, mid + 1, r, ql, qr, x);
}
 
int query(int rt, int l, int r, int q) {
    if(!rt) return 0;
    if(l == r)  return tr[rt];
    int mid = (l + r) / 2;
    if(q <= mid) return max(tr[rt], query(lson, l, mid, q));
    else return max(tr[rt], query(rson, mid + 1, r, q));

}
void init(int rt, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) { tr[rt] = 0; return; }
    int mid = (l + r) / 2;
    if (ql <= mid) init(lson, l, mid, ql, qr);
    if (qr > mid) init(rson, mid + 1, r, ql, qr);
}

bool cmp1(const qwq &a, const qwq &b) { return a.x != b.x ? a.x < b.x : a.y < b.y;  }
bool cmp2(const qwq &a, const qwq &b) { return a.a < b.a;  }

# define REPD(i, a, b) for(int i = a; i >= b; -- i)

void solve(int l, int r) {
    if(l == r) return ;
    int mid = l + r >> 1;
    solve(l, mid);
    sort(p + l, p + mid + 1, cmp2); //-------------
    // i -> next, j -> pre
    int j = mid;
    REPD(i, r, mid + 1) {
        for(; j >= l && p[i].x <= p[j].a; -- j) modify(1, 1, R, p[j].y, p[j].b, p[j].w + 1);
        p[i].w = MAX(p[i].w, query(1, 1, R, p[i].y));
    }
    REP(i, l, mid) init(1, 1, R, p[i].y, p[i].b);
    solve(mid + 1, r);
} 

int main() {
    scanf("%d", &n);
    REP(i, 1, n) {
        int a, b, c, d;
        scanf("%d%d%d%d", &a, &b, &c, &d);
        p[i] = (qwq) { a + 1, b + 1, c + 1, d + 1, 0 }; 
    }
    sort(p + 1, p + n + 1, cmp1);
    solve(1, n);
    int ans = 0;
    REP(i, 1, n) ans = MAX(ans, p[i].w + 1);
    printf("%d\n", ans); 
    return 0;
}

· EOF ·

Comments
Write a Comment