题目链接:洛谷P3810-陌上花开
题意:
有n个物品,每个物品有三个参数,设F(i)表示满足a(j)<=a(i),b(j)<=b(i),c(j)<=c(i)的数量。对于0<=d<n,求f(i)=d的数量。
题解:
三维偏序。
第一维对a排序;第二维归并排序,因为已经按a排过序,在左边和右边对b排序时仍保证左边的a小于右边;第三维树状数组,查询满足前两位偏序关系,且c小于当前数的个数。
注意一点,因为我们把完全相同的物品进行了缩点,计算贡献时需要减1.
参考代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 5;
const int MAXK = 2e5 + 5;
int n, k;
int tot = 0;
unordered_map<ll, int> mp;
ll getid(ll x, ll y, ll z) { return 1ll * x * MAXK * MAXK + 1ll * y * MAXK + 1ll * z; }
struct NODE
{
int x, y, z, v, ans;
NODE() {}
NODE(int x, int y, int z, int v, int ans)
{
this->x = x, this->y = y, this->z = z, this->v = v, this->ans = ans;
}
} a[MAXN];
bool cmp1(NODE x, NODE y) { return (x.x == y.x) ? ((x.y == y.y) ? x.z < y.z : x.y < y.y) : x.x < y.x; }
struct BIT
{
int c[MAXK], _n;
void init(int _n)
{
for (int i = 1; i <= _n; i++)
c[i] = 0;
this->_n = _n;
}
int lowbit(int x)
{
return x & -x;
}
/* 单点修改 区间求和 */
void update(int x, int val)
{
while (x <= _n)
{
c[x] += val;
x += lowbit(x);
}
}
int getsum(int x)
{
int ret = 0;
while (x)
{
ret += c[x];
x -= lowbit(x);
}
return ret;
}
} bit;
bool cmp2(NODE x, NODE y) { return x.y == y.y ? x.z < y.z : x.y < y.y; }
void cdq(int l, int r)
{
if (l == r)
return;
int mid = (l + r) >> 1;
cdq(l, mid);
cdq(mid + 1, r);
sort(a + l, a + mid + 1, cmp2);
sort(a + mid + 1, a + r + 1, cmp2);
int p = l, q = mid + 1;
for (; q <= r; q++)
{
while (a[p].y <= a[q].y && p <= mid)
bit.update(a[p].z, a[p].v), p++;
a[q].ans += bit.getsum(a[q].z);
}
for (int i = l; i < p; i++)
bit.update(a[i].z, -a[i].v);
}
int cnt[MAXN];
int main()
{
scanf("%d%d", &n, &k);
mp.clear();
tot = 0;
for (int i = 1; i <= n; i++)
{
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
if (mp.count(getid(x, y, z)))
{
int pp = a[mp[getid(x, y, z)]].v + 1;
a[mp[getid(x, y, z)]] = NODE(x, y, z, pp, 0);
}
else
mp[getid(x, y, z)] = ++tot, a[tot] = NODE(x, y, z, 1, 0);
}
sort(a + 1, a + 1 + tot, cmp1);
bit.init(k);
cdq(1, tot);
for (int i = 1; i <= tot; i++)
cnt[a[i].ans + a[i].v - 1] += a[i].v;
for (int i = 0; i < n; i++)
printf("%d\n", cnt[i]);
return 0;
}