3262: 陌上花开
Description
Input
Output
Sample Input
3 3 3
2 3 3
2 3 1
3 1 1
3 1 2
1 3 1
1 1 2
1 2 2
1 3 2
1 2 1
Sample Output
1
3
0
1
0
1
0
0
1
HINT
1 <= N <= 100,000, 1 <= K <= 200,000
CDQ分治
先将花（下面说成点,三个属性分别看做a,b,c）
按a为第一关键字,b为第二关键字,c为第三关键字排序
那么对于每个点P,在P之前的点I都满足 I.a <= P.a
所以只需要求满足 I.b <= P.b 且 I.c <= P.c 的点I的个数
那么 每个满足条件的点I 对 点P答案的贡献为1
定义一个过程solve(L, R) 求出[L, R]中的点的相互贡献值
对于当前solve(L, R)
我们将点分成两堆，分别求[L, mid]和[mid + 1, R]中的点的相互贡献值
现在考虑求[L, mid]中的点对[mid + 1, R]中的点的贡献
将[L, R]中的点按b为第一关键字重新排序（建议用归并排序）
那么现在对于[mid + 1, R]中的点P,
若P前有一点Q满足 在点集[L, mid]中 且 Q.c<=P.c
则Q对P有贡献值1
然后采用一个数据结构（你可以用 线段树 或者 树状数组）
将排序后的点I按顺序 更新(在I.c位置加入) 或 询问（查询I.c位置的前缀和) 贡献值
（[L, mid]点集中的点用于更新某一位置的贡献值，
[mid+1, R]点集中的点用于询问贡献值并加入答案）
即solve(L, R)完成。。。
或许你看不懂上面的一小段（其实wy回头看时也是看不懂的T_T）
所以我们举一个例子
现在有点(1,3,2),(2,1,1),(2,2,3),(3,3,3)
下面是模拟过程。。。
solve(1,4)
solve(1,2)
solve(1,1) ----没有更新答案
solve(2,2) ----没有更新答案
(2,1,1) 在数据结构中查询1位置的贡献前缀和,没有更新答案
(1,3,2) 在2位置添加1个贡献值，不查询贡献
solve(3,4)
solve(3,3) ----没有更新答案
solve(4,4) ----没有更新答案
(2,2,3) 在新数据结构3位置添加1个贡献值,不查询贡献
(3,3,3) 查询3位置的贡献前缀和，点4 的答案 +1
(2,1,1) 在新数据结构中1位置添加1个贡献值，不查询贡献
(2,2,3) 查询3位置的贡献前缀和，点3 的答案 +1
(1,3,2) 在2位置添加1个贡献值，不查询贡献
(3,3,3) 查询3位置的贡献前缀和，点4 的答案 +2
以上就是模拟过程。。。
(⊙o⊙)…鉴于wy的语文水平较差T_T，还没有看懂的童鞋请看程序
#include <cstdio>
#include <algorithm>
using namespace std;
const int MaxN = 100010;
const int MaxM = 200010;
int N, S;
int sum[MaxN],L[MaxM];
struct point{
int a, b, c, key, s;
inline point (int x = 0, int y = 0, int z = 0, int w = 0, int cnt = 0){
a = x; b = y; c = z; key = w; s = cnt;
}
inline bool operator == (const point &Q){
return a == Q.a && b == Q.b && c == Q.c;
}
}p[MaxN], q[MaxN];
inline bool cmp(const point &a, const point &b){
return a.a < b.a || a.a == b.a && a.b < b.b || a.a == b.a && a.b == b.b && a.c < b.c;
}
inline int lowbit(int x){
return x & -x;
}
inline void New(int x){
for (int i = x; i <= S; i += lowbit(i))
if (sum[i]) sum[i]=0;
else break;
}
inline void Insert(int x, int k){
for (int i = x; i <= S; i += lowbit(i))
sum[i] += k;
}
inline int Query(int x){
int s=0;
for (int i = x; i>0 ; i -= lowbit(i))
s += sum[i];
return s;
}
inline void solve(int l, int r){
if (l == r) return;
int mid = l + r >> 1;
solve(l, mid), solve(mid + 1, r);
int t1 = l, t2 = mid + 1;
for (int i = l; i <= r; ++i)
if (t1 <= mid && p[t1].b <= p[t2].b || t2 > r){
q[i] = p[t1++];
Insert(q[i].c,q[i].s);
}
else {
q[i] = p[t2++];
q[i].key += Query(q[i].c);
}
for (int i = l; i <= r; ++i)
p[i] = q[i], New(p[i].c);
}
int main(){
scanf("%d%d", &N, &S);
for (int i = 1; i <= N; ++i)
scanf("%d%d%d", &p[i].a, &p[i].b, &p[i].c);
sort(p + 1, p + N + 1, cmp);
int m = 0;
for (int i = 1; i <= N; ++i){
if (!m || !(q[m] == p[i])) q[++m] = p[i];
++q[m].s;
}
for (int i =1; i <= m; ++i)
p[i] = q[i];
solve(1, m);
for (int i = 1; i <= m; ++i)
L[p[i].key + p[i].s - 1] += p[i].s;
for (int i = 0; i < N; ++i)
printf("%d\n",L[i]);
}
评论 (0)
