什么是CDQ分治？
一个最简单的cdq分治的例子就是归并排序求逆序对。
简单的说，cdq分治就是有一系列关于区间$[L,R]$的问题。
1.递归处理$[L,M]$和$[M+1,R]$。
2.计算$[L,M]$对$[M+1,R]$的影响。
按时间$T$排序，在$solve$中再按$x$排序，然后用数据结构维护$y$即可。
1 #include2 #include 3 using namespace std; 4 inline char nc() { 5 static char b[1<<16],*s=b,*t=b; 6 return s==t&&(t=(s=b)+fread(b,1,1<<16,stdin),s==t)?-1:*s++; 7 } 8 inline void read(int &x) { 9 char b = nc(); x = 0;10 for (; !isdigit(b); b = nc());11 for (; isdigit(b); b = nc()) x = x * 10 + b - '0';12 }13 int s, n, ans[10010], m, c[2000005];14 inline int lowbit(int x) {15 return x & -x; 16 }17 inline void add(int p, int x) {18 for (; p <= n; p += lowbit(p)) c[p] += x; 19 }20 inline int sum(int p) {21 int res = 0;22 for (; p; p -= lowbit(p)) res += c[p];23 return res;24 }25 struct Q {26 int x, y, v, T, a;27 inline bool operator<(const Q &q) const {28 return x != q.x ? x < q.x : T < q.T;29 }30 } q[200005], tq[200005];31 inline void add(int x, int y, int v, int a) {32 q[++m] = (Q){x, y, v, m, a};33 }34 void solve(int l, int r) {35 if (l == r) return;36 int m = (l + r) >> 1, h1 = l, h2 = m + 1, h = l;37 solve(l, m); solve(m + 1, r);38 while (h1 <= m && h2 <= r) tq[h++] = q[h1] < q[h2] ? q[h1++] : q[h2++];39 while (h1 <= m) tq[h++] = q[h1++]; while (h2 <= r) tq[h++] = q[h2++];40 for (int i = l; i <= r; ++i) q[i] = tq[i];41 for (int i = l; i <= r; ++i) {42 if (!q[i].a && q[i].T <= m) add(q[i].y, q[i].v);43 if (q[i].a && q[i].T > m) ans[q[i].a] += q[i].v * sum(q[i].y);44 }45 for (int i = l; i <= r; ++i)46 if (!q[i].a && q[i].T <= m) add(q[i].y, -q[i].v);47 }48 int main() {49 read(s); read(n); ++n;50 for (int op, a, b, c, d;;) {51 read(op); if (op == 3) break;52 read(a), read(b), read(c);53 if (op == 1) add(a + 1, b + 1, c, 0);54 else if (op == 2) {55 read(d); ++a; ++b; ++c; ++d; ++ans[0];56 add(c, d, 1, ans[0]);57 add(a - 1, b - 1, 1, ans[0]);58 add(a - 1, d, -1, ans[0]);59 add(c, b - 1, -1, ans[0]);60 }61 }62 solve(1, m);63 for (int i = 1; i <= ans[0]; ++i) printf("%d\n", ans[i]);64 return 0;65 }
每次买入卖出都用完钱或者券是最吼的。
记$dp_i$，$f_i$，$g_i$为第$i$天最多的钱，A券，B券。
由题意可知，$f_i=dp_i\frac{R_i}{A_iR_i+B_i}$，$g_i=\frac{R_i}{A_iR_i+B_i}$。
$dp$方程很显然，$dp_i=\max\{A_if_j + B_ig_j\}(j < i)$
这样我们就得到了一个$O(N^2)$的算法，但是还不行。
若对于$i$，决策$j$比$k$更优，则，
$A_if_j+B_ig_j>A_if_k+B_ig_k$
$A_i(f_j-f_k)+B_i(g_j-g_k)>0$
为了处理符号，咱不妨设$f_j<f_k$，
$\frac{g_j-g_k}{f_j-f_k}<-\frac{A_i}{B_i}$
这就是一个斜率优化的式子了，但是左右两边都没有单调性。
这时候就是cdq分治出场的时候了。
咱先将每一天按照$-\frac{A_i}{B_i}$排序，然后再在递归处理时按$i$排序，并维护一个斜率单调递减的下凸壳。
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 const int N = 100010; 7 typedef double db; 8 inline char nc() { 9 static char b[1<<16],*s=b,*t=b; 10 return s==t&&(t=(s=b)+fread(b,1,1<<16,stdin),s==t)?-1:*s++; 11 } 12 inline void read(int &x) { 13 char b = nc(); x = 0; 14 for (; !isdigit(b); b = nc()); 15 for (; isdigit(b); b = nc()) x = x * 10 + b - '0'; 16 } 17 inline void read(db &x) { 18 char b = nc(); x = 0; 19 for (; !isdigit(b); b = nc()); 20 for (; isdigit(b); b = nc()) x = x * 10 + b - '0'; 21 if (b == '.') { 22 db t = 0.1; 23 for (b = nc(); isdigit(b); b = nc()) 24 x += t * (b - '0'), t /= 10; 25 } 26 } 27 int n, top, stk[N]; 28 db dp[N]; 29 struct Q { 30 db a, b, r, s; 31 int id; 32 inline void init(int i) { 33 read(a); read(b); read(r); 34 s = -a / b; id = i; 35 } 36 inline bool operator<(const Q &q) const { 37 return s < q.s; 38 } 39 } q[N], tq[N]; 40 struct Pt { 41 db x, y; 42 inline bool operator<(const Pt &p) const { 43 return x != p.x ? x < p.x : y < p.y; 44 } 45 } p[N], tp[N]; 46 bool check(const Pt &a, const Pt &b, const Pt &c) { 47 return (b.y - a.y) * (c.x - b.x) > (b.x - a.x) * (c.y - b.y); 48 } 49 bool check(int a, int b, int c) { 50 return check(p[a], p[b], p[c]); 51 } 52 inline void gmax(db &x, db y) { 53 if (x < y) x = y; 54 } 55 db slope(const Pt &a, const Pt &b) { 56 if (a.x == b.x) return a.y < b.y ? 1e10 : -1e10; 57 return (a.y - b.y) / (a.x - b.x); 58 } 59 db slope(int a, int b) { 60 return slope(p[a], p[b]); 61 } 62 void solve(int l, int r) { 63 if (l == r) { 64 gmax(dp[l], dp[l-1]); 65 p[l].x = dp[l] * q[l].r / (q[l].a * q[l].r + q[l].b); 66 p[l].y = dp[l] / (q[l].a * q[l].r + q[l].b); 67 return; 68 } 69 int m = (l + r) >> 1, h1 = l, h2 = m + 1; 70 for (int i = l; i <= r; ++i) 71 if (q[i].id <= m) tq[h1++] = q[i]; 72 else tq[h2++] = q[i]; 73 for (int i = l; i <= r; ++i) q[i] = tq[i]; 74 solve(l, m); top = 0; 75 for (int i = l; i <= m; ++i) { 76 while (top > 1 && !check(stk[top-1], stk[top], i)) --top; 77 stk[++top] = i; 78 } 79 for (int i = m + 1; i <= r; ++i) { 80 while (top > 1 && slope(stk[top-1], stk[top]) < q[i].s) --top; 81 gmax(dp[q[i].id], q[i].a * p[stk[top]].x + q[i].b * p[stk[top]].y); 82 } 83 solve(m + 1, r); 84 h1 = l, h2 = m + 1; 85 for (int i = l; i <= r; ++i) 86 if (h1 <= m && (p[h1] < p[h2] || h2 > r)) tp[i] = p[h1++]; 87 else tp[i] = p[h2++]; 88 for (int i = l; i <= r; ++i) p[i] = tp[i]; 89 } 90 inline void foo() { 91 freopen("cash.in", "r", stdin); 92 freopen("cash.out", "w", stdout); 93 } 94 int main() { 95 read(n); read(dp[0]); 96 for (int i = 1; i <= n; ++i) q[i].init(i); 97 sort(q + 1, q + 1 + n); 98 solve(1, n); printf("%.3lf\n", dp[n]); 99 return 0;100 }
一道三维偏序问题。
都是套路。先在外面按$s$排序，递归时按$c$排序，树状数组维护$m$。
由于这题是$\leqslant$，所以还有一些额外的操作！
1 #include2 #include 3 #include 4 using namespace std; 5 inline char nc() { 6 static char b[1<<16],*s=b,*t=b; 7 return s==t&&(t=(s=b)+fread(b,1,1<<16,stdin),s==t)?-1:*s++; 8 } 9 inline void read(int &x) {10 char b = nc(); x = 0;11 for (; !isdigit(b); b = nc());12 for (; isdigit(b); b = nc()) x = x * 10 + b - '0';13 }14 struct Node {15 int a, b, c, T, ans;16 inline void init() {17 read(a), read(b), read(c);18 }19 inline bool operator<(const Node &o) const {20 if (a != o.a) return a < o.a;21 if (b != o.b) return b < o.b;22 return c < o.c;23 }24 inline bool operator==(const Node &o) const {25 return a == o.a && b == o.b && c == o.c;26 }27 } p[100005], tp[100005];28 int n, H, c[200005], ans[100005];29 inline int lowbit(int x) {30 return x & -x;31 }32 inline void add(int p, int x) {33 for (; p <= H; p += lowbit(p)) c[p] += x; 34 }35 inline int sum(int p) {36 int res = 0;37 for (; p; p -= lowbit(p)) res += c[p];38 return res;39 }40 void solve(int l, int r) {41 if (l == r) return;42 int m = (l + r) >> 1, h1 = l, h2 = m + 1, h = l;43 solve(l, m); solve(m + 1, r);44 for (int i = l; i <= m; ++i) p[i].T = 1;45 for (int i = m + 1; i <= r; ++i) p[i].T = 0;46 while (h1 <= m && h2 <= r) tp[h++] = p[h1].b <= p[h2].b ? p[h1++] : p[h2++];47 while (h1 <= m) tp[h++] = p[h1++]; while (h2 <= r) tp[h++] = p[h2++];48 for (int i = l; i <= r; ++i) p[i] = tp[i];49 for (int i = l; i <= r; ++i) {50 if (p[i].T) add(p[i].c, 1);51 else p[i].ans += sum(p[i].c);52 }53 for (int i = l; i <= r; ++i) if (p[i].T) add(p[i].c, -1);54 }55 56 int main() {57 read(n); read(H);58 for (int i = 1; i <= n; ++i) p[i].init();59 sort(p + 1, p + 1 + n); solve(1, n);60 for (int i = n - 1; i; --i) if (p[i] == p[i+1]) 61 p[i].ans = max(p[i].ans, p[i+1].ans);62 for (int i = 1; i <= n; ++i) ++ans[p[i].ans];63 for (int i = 0; i < n; ++i) printf("%d\n", ans[i]);64 return 0; 65 }
一道四维偏序题。记四元组$(a,b,c,d)$。跟三维偏序的套路一样。我们先按$a$排序，第一层$cdq$分治按$b$排序，得到一些四元组$(L,b,c,d)$和$(R,b,c,d)$。虽然这样排序之后$a$是无序的，但是$(L,b,c,d)$的$a$与$(R,b,c,d)$的$a$的大小关系是可以确定的。第二层$cdq$分治中，咱再按$c$排序，得到一些四元组$(L/R,L/R,c,d)$，再用树状数组维护$d$。
回忆三维偏序，咱只更新$(L,b,c)$的$c$的个数，只更新$(R,b,c)$的答案。在四维偏序里也是类似的。咱只更新$(L,L,c,d)$的$d$的个数，只更新$(R,R,c,d)$的答案。
如果还没看明白，这里安利一发。
1 #include2 #include 3 #define setO(p, l, r, o, v) for (int i = l; i <= r; ++i) p[i].o = v 4 using namespace std; 5 inline char nc() { 6 static char b[1<<16],*s=b,*t=b; 7 return s==t&&(t=(s=b)+fread(b,1,1<<16,stdin),s==t)?-1:*s++; 8 } 9 inline void read(int &x) {10 char b = nc(); x = 0;11 for (; !isdigit(b); b = nc());12 for (; isdigit(b); b = nc()) x = x * 10 + b - '0';13 }14 const int N = 50005;15 int n, c[N];16 unsigned int ans;17 inline int lowbit(int x) { return x & -x;}18 inline void add(int p, int x) { for (; p <= n; p += lowbit(p)) c[p] += x;}19 inline int sum(int p) {20 int res = 0;21 for (; p; p -= lowbit(p)) res += c[p];22 return res;23 }24 struct P {25 int b, c, d; bool o1, o2;26 inline bool L() { return o1 && o2;}27 inline bool R() { return !o1 && !o2;}28 } p[N], p1[N], p2[N];29 void solve2(int l, int r) {30 if (l == r) return;31 int m = (l + r) >> 1, h1 = l, h2 = m + 1, h = l;32 solve2(l, m); solve2(m + 1, r);33 setO(p1, l, m, o2, 1); setO(p1, m + 1, r, o2, 0);34 while (h1 <= m && h2 <= r) p2[h++] = p1[h1].c < p1[h2].c ? p1[h1++] : p1[h2++];35 while (h1 <= m) p2[h++] = p1[h1++]; while (h2 <= r) p2[h++] = p1[h2++];36 for (int i = l; i <= r; ++i) p1[i] = p2[i];37 for (int i = l; i <= r; ++i) {38 if (p1[i].L()) add(p1[i].d, 1);39 else if (p1[i].R()) ans += sum(p1[i].d);40 }41 for (int i = l; i <= r; ++i) if (p1[i].L()) add(p1[i].d, -1);42 }43 void solve1(int l, int r) {44 if (l == r) return;45 int m = (l + r) >> 1, h1 = l, h2 = m + 1, h = l;46 solve1(l, m); solve1(m + 1, r);47 setO(p, l, m, o1, 1); setO(p, m + 1, r, o1, 0);48 while (h1 <= m && h2 <= r) p1[h++] = p[h1].b < p[h2].b ? p[h1++] : p[h2++];49 while (h1 <= m) p1[h++] = p[h1++]; while (h2 <= r) p1[h++] = p[h2++];50 for (int i = l; i <= r; ++i) p[i] = p1[i]; solve2(l, r);51 }52 int main() {53 freopen("partial_order.in", "r", stdin);54 freopen("partial_order.out", "w", stdout);55 read(n);56 for (int i = 1; i <= n; ++i) read(p[i].b);57 for (int i = 1; i <= n; ++i) read(p[i].c);58 for (int i = 1; i <= n; ++i) read(p[i].d);59 solve1(1, n); printf("%u\n", ans);60 return 0; 61 }
绝对值很麻烦，所以我们每次只更新在左下方的点。旋转坐标系，一共做四次就可以得到答案了。cdq分治并维护前缀最大值即可。
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 inline char nc() { 7 static char b[1<<16],*s=b,*t=b; 8 return s==t&&(t=(s=b)+fread(b,1,1<<16,stdin),s==t)?-1:*s++; 9 }10 inline void read(int &x) {11 char b = nc(); x = 0;12 for (; !isdigit(b); b = nc());13 for (; isdigit(b); b = nc()) x = x * 10 + b - '0';14 }15 struct P {16 int x, y, o, T;17 inline bool operator<(const P &p) const {18 return x != p.x ? x < p.x : T < p.T; 19 }20 } p[1000005], tp[1000005], op[1000005];21 int n, m, mx[1000010], xmax, ymax, A, ans[500005];22 const int inf = 0x3f3f3f3f;23 inline void gmax(int &x, int y) { if (x < y) x = y;}24 inline void gmin(int &x, int y) { if (x > y) x = y;}25 inline int lowbit(int x) { return x & -x;}26 inline void add(int p, int x) {27 for (; p <= ymax; p += lowbit(p)) gmax(mx[p], x); 28 }29 inline int getmx(int p) {30 int res = 0;31 for (; p; p -= lowbit(p)) gmax(res, mx[p]);32 return res == 0 ? -inf : res;33 }34 inline void clrmx(int p) {35 for (; p <= ymax; p += lowbit(p)) mx[p] = 0; 36 }37 void solve(int l, int r) {38 if (l == r) return ;39 int m = (l + r) >> 1, h1 = l, h2 = m + 1, h = l;40 solve(l, m); solve(m + 1, r);41 while (h1 <= m && h2 <= r) tp[h++] = p[h1] < p[h2] ? p[h1++] : p[h2++];42 while (h1 <= m) tp[h++] = p[h1++]; while (h2 <= r) tp[h++] = p[h2++];43 for (int i = l; i <= r; ++i) p[i] = tp[i];44 for (int i = l; i <= r; ++i) {45 if (p[i].T <= m && !p[i].o) add(p[i].y, p[i].x + p[i].y);46 else if (p[i].T > m && p[i].o) gmin(ans[p[i].o], p[i].x + p[i].y - getmx(p[i].y));47 }48 for (int i = l; i <= r; ++i)49 if (p[i].T <= m && !p[i].o) clrmx(p[i].y);50 }51 void cpy() {52 for (int i = 1; i <= n + m; ++i) p[i] = op[i];53 }54 int main() {55 read(n); read(m);56 for (int x, y, i = 1; i <= n; ++i)57 read(x), read(y), op[i] = (P){x + 1, y + 1, 0, i};58 for (int x, y, o, i = n + 1; i <= n + m; ++i)59 read(o), read(x), read(y), op[i] = (P){x + 1, y + 1, o == 1 ? 0 : ++A, i};60 for (int i = 1; i <= A; ++i) ans[i] = inf;61 for (int i = 1; i <= n + m; ++i) gmax(xmax, op[i].x), gmax(ymax, op[i].y);62 ++xmax, ++ymax; cpy(); solve(1, n + m);63 cpy(); for (int i = 1; i <= n + m; ++i) p[i].x = -p[i].x + xmax; solve(1, n + m);64 cpy(); for (int i = 1; i <= n + m; ++i) p[i].y = -p[i].y + ymax; solve(1, n + m);65 cpy(); for (int i = 1; i <= n + m; ++i) p[i].x = -p[i].x + xmax, p[i].y = -p[i].y + ymax; solve(1, n + m);66 for (int i = 1; i <= A; ++i) printf("%d\n", ans[i]);67 return 0;68 }
把数列看成一个个点$(x, a[x])$，再把坐标系转$\pi/4$，问题转化成询问矩形内点的个数。
TBD:
http://www.lydsy.com/JudgeOnline/problem.php?id=2001