CDQ分治
cdq分治是一种分治思想,其实就是归并排序,,,。解决一个区间问题,分而治之,[l, r]->[l, mid] + [mid+1, r]。同时在解决完子问题后,还要考虑这两个子问题之间的相互影响,求一个子问题对另一个子问题的贡献。
P3810 三维偏序
在解决离线三维偏序问题时,我们可以先把原来的元素按第一关键词,第二关键词,第三关键词升序排序,这样可以保证一个元素后面的元素对它不会有贡献(注意先去重)。然后分而治之,在两个子问题都被解决之后,这两个子区间内的元素应已经按第二关键词排好序了,然后我们依照归并排序的方式一次拿下两子区间的元素,同时把元素的第三关键词的值加入树状数组。那么对于右区间的每一个元素,当轮到它被拿下时,在树状数组里寻找第三关键字值比它小的元素个数,加入到它的贡献里即可。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5, maxk = 2e5+5;
int n, k, m;
struct zyh{
int a, b, c;
int w, t;
}nums[maxn], tmp[maxn];
int c[maxk], ans[maxn];
inline int lowbit(int i){
return i & (-i);
}
void add(int i, int d){
while (i<=k){
c[i] += d;
i += lowbit(i);
}
return;
}
int sum(int i){
int ans = 0;
while (i){
ans += c[i];
i -= lowbit(i);
}
return ans;
}
void cdq(int l, int r){
if (l==r) return;
int mid = (l+r) >> 1;
cdq(l, mid); cdq(mid+1, r);
int i = l, j = mid+1, cnt = 0;
for ( ; j<=r; j++){
while (i<=mid && nums[i].b<=nums[j].b) add(nums[i++].c, nums[i].t);
nums[j].w += sum(nums[j].c);
//add(nums[j].c, 1);
}
//for (j=mid+1; j<=r; j++) add(nums[j].c, -1);
for (i--; i>=l; i--) add(nums[i].c, -nums[i].t);
i = mid;
//while (nums[i].a)
i = l, j = mid+1;
while (i<=mid && j<=r){
if (nums[i].b <= nums[j].b) tmp[++cnt] = nums[i++];
else tmp[++cnt] = nums[j++];
}
while (i<=mid) tmp[++cnt] = nums[i++];
while (j<=r) tmp[++cnt] = nums[j++];
for (i=l, j=1; i<=r; i++, j++) nums[i] = tmp[j];
return;
}
inline bool cmp(struct zyh x, struct zyh y){
if (x.a != y.a) return x.a < y.a;
if (x.b != y.b) return x.b < y.b;
return x.c < y.c;
}
inline bool equal(struct zyh x, struct zyh y){
if (x.a==y.a && x.b==y.b && x.c==y.c) return true;
return false;
}
int main(){
scanf ("%d %d", &n, &k);
for (int i=1; i<=n; i++){
scanf ("%d %d %d", &nums[i].a, &nums[i].b, &nums[i].c);
nums[i].w = 0, nums[i].t = 1;
}
sort (nums+1, nums+n+1, cmp);
int cnt = 1;
tmp[1] = nums[1];
for (int i=2; i<=n; i++){
if (!equal(nums[i], nums[i-1])) tmp[++cnt] = nums[i];
else tmp[cnt].t++;
}
m = n, n = cnt;
for (int i=1; i<=n; i++) nums[i] = tmp[i], nums[i].w = nums[i].t-1;
cdq(1, n);
for (int i=1; i<=n; i++) ans[nums[i].w] += nums[i].t;
for (int i=0; i<m; i++)
printf ("%d\n", ans[i]);
return 0;
}
0 条评论