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的转移依赖于上一个状态的更新态，所以这种写法应该是更加普适一点的。
写的时候注意几点
- DEBUG时可以看看合并前是否前驱条件都满足了，例如单调性等等，是否已经提前合并好了。
- 如果在分治的时候对原数组的关键字相对位置进行了改动，记得下一次cdq的时候改回来。
- 如果在cdq内不选择归并而是选择sort（log方了），那重复元素要小心了，因为快排不是一个稳定的排序。
2h惨案 - 对于重复元素的答案统计要慎重
- 为了使传递的参数更加简洁，尽量使分治的一维与数组下标的数据范围是同阶的，尽量选择归并排序，实在不行再sort
- dp的时候注意l==r的时候若无值再去赋值。
- 注意边界限制
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就可以水过。
这题调的我想骂人。
头一次知道有序列点这种东西，这两句话居然是有区别的：
inc(a[j].y, f[a[j].id], 1), -- j;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