现在还不是很懂cdq分治是啥。
我对它的理解大概就是一种分治方法 / 思想。
这个方法有一些限制:[区间L] < [区间R](需要对整个数组sort一遍)
这个方法可以做到:用来解决各种区间段转移问题[x->y(x<y)]的,比如,求逆序对数。(本质上就是计算左区间对右区间的贡献)
拓展:将修改转化为左区间,将询问转化为右区间,从而离线求得一些数据结构的题目。
其核心代码就跟归并排序求逆序对差不多。
void CDQ(int L, int R) { //就是merge啦 if (L >= R) return ; int mid = (L+R) >> 1; CDQ(L, mid), CDQ(mid+1, R); int p1 = L, p2 = mid+1, pos = L; while (p1 <= mid && p2 <= R) { if (val[p1] <= val[p2]) temp[pos++] = val[p1++]; else temp[pos++] = val[p2++], ans += (mid-p1+1); //这一步计算贡献 } while (p1 <= mid) temp[pos++] = val[p1++]; while (p2 <= R) temp[pos++] = val[p2++]; for (int i = L; i <= R; ++ i) val[i] = temp[i]; }