/*CDQ分治的对象是时间。即对于一个时间段[L, R]，我们取mid = (L + R) / 2。分治的每层只考虑mid之前的修改对mid之后的查询的贡献，然后递归到[L,mid]，(mid,R]。显然，CDQ分治是一种离线算法，我们需要将所有的修改/查询存下来，一起进行操作。同时，CDQ分治还需要满足：操作之间相互独立，即一个操作的存在不会影响到另一个操作的存在。经典入门题 单点修改 矩形查询如果此题矩形小一点的话 可以使用树状数组套线段树但是矩形过大时就不适用了这里可以将一个询问拆成四个前缀和查询，然后和修改操作一起 做cdq分治*/#include #define LL long longusing namespace std;const int N = 2e6 + 1;int tr[N],W;int lowbit(int x){return x & (-x);}void up(int pos,int v){ for(;pos <= W;pos += lowbit(pos)) tr[pos] += v;}int getsum(int pos){ int ans = 0; for(;pos;pos -= lowbit(pos)) ans += tr[pos]; return ans;}struct Q{ int x, y, type, q, v, order; Q(){}; Q(int x,int y,int type, int q,int v,int order):x(x),y(y),type(type),q(q),v(v),order(order){}; bool operator<(const Q&rhs)const{ return x < rhs.x; }}qr[N],tmp[N];int ans[N];void cdq(int l,int r){ if(l == r) return ; int mid = l + r >> 1; int p1 = l,p2 = mid + 1; /// 首先将mid之前的操作 全部放到mid左边 mid之后的操作全部放到右边，保证了按时间分治，并且左右都是x递增的 for(int i = l;i <= r;i++){ if(qr[i].order <= mid) tmp[p1++] = qr[i]; else tmp[p2++] = qr[i]; } for(int i = l;i <= r;i++) qr[i] = tmp[i]; int j = l; ///计算完mid时间轴左边的修改对右边查询的贡献，恢复修改 for(int i = mid + 1;i <= r;i++){ if(qr[i].type == 2) { for(; j <= mid && qr[j].x <= qr[i].x; j++){ if(qr[j].type == 1) up(qr[j].y,qr[j].v); } ans[qr[i].q] += qr[i].v * getsum(qr[i].y); } } for(int i = l;i < j;i++) if(qr[i].type == 1) up(qr[i].y, -qr[i].v); ///进行递归分治 cdq(l, mid);cdq(mid + 1, r);}int main(){ int op, a, b, c, d, id = 0, tot = 0; while(scanf("%d", &op) && op != 3){ if(op == 0) scanf("%d", &W); else if(op == 1){ scanf("%d%d%d", &a, &b, &c); qr[++id] = Q(a, b, 1, 0, c, id); } else{ ++tot; scanf("%d%d%d%d", &a, &b, &c, &d); qr[++id] = Q(a - 1, b - 1, 2, tot, 1, id); qr[++id] = Q(c, d, 2, tot, 1, id); qr[++id] = Q(a - 1, d, 2, tot, -1, id); qr[++id] = Q(c, b - 1, 2, tot, -1, id); } } sort(qr + 1, qr + id + 1); cdq(1, id); for(int i = 1; i <= tot; i++) printf("%d\n", ans[i]); return 0;}
http://codeforces.com/gym/101485/attachments求出多少对(i,j) 满足i < j 且a[j] < a[i] 且 b[j] < b[i]做法 第一维分治 第二维树状数组 时间复杂度为O(nlognlogn) 空间复杂度O(n)解决二维偏序问题 其他做法可能空间复杂度为过高#include #include #include #include #include #include