# BZOJ3262: 陌上花开(cdq分治)

Time Limit: 20 Sec  Memory Limit: 256 MB

Submit: 3627  Solved: 1705

[Submit][Status][Discuss]

## Sample Input

10 3 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

3 1 3 0 1 0 1 0 0 1

## Source

#include<cstdio>
#include<algorithm>
#define lowbit(x) ((x) & (-x))
using namespace std;
const int MAXN = 200001;
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int N, Max;
struct Node {
int a, b, c, f, w;
bool operator < (const Node &rhs) const{
return (a == rhs.a && b == rhs.b) ? (c < rhs.c) : (a == rhs.a ? b < rhs.b : a < rhs.a);
}
}A[MAXN], tp[MAXN];
int num = 0, ans[MAXN];
int T[MAXN];
void Add(int pos, int val) {
for(int i = pos; i <= Max; i += lowbit(i)) T[i] += val;
}
int Query(int pos) {
int ans = 0;
for(int i = pos; i; i -= lowbit(i)) ans += T[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, P = l;
while(i <= mid || j <= r) {
if(j > r || (i <= mid && A[i].b <= A[j].b)) Add(A[i].c, A[i].w), tp[P++] = A[i++];
else A[j].f += Query(A[j].c), tp[P++] = A[j++];
}
for(int i = l; i <= mid; i++) Add(A[i].c, -A[i].w);
for(int i = l; i <= r; i++) A[i] = tp[i];
}
int main() {
#ifdef WIN32
freopen("a.in", "r", stdin);
#endif
for(int i = 1; i <= N; i++) A[i].a = read(), A[i].b = read(), A[i].c = read(), A[i].w = 1;
sort(A + 1, A + N + 1);
num = 1;
for(int i = 2; i <= N; i++)
if(A[i].a == A[num].a && A[i].b == A[num].b && A[i].c == A[num].c) A[num].w++;
else A[++num] = A[i];
CDQ(1, num);
for(int i = 1; i <= num; i++) ans[A[i].f + A[i].w - 1] += A[i].w;
for(int i = 0; i <= N - 1; i++)
printf("%d\n", ans[i]);
return 0;
}

0 条评论

• ### 洛谷P4424 [HNOI/AHOI2018]寻宝游戏(思维题)

那么我们把每一列上的数和他之前的操作符分别拿出来看成一些序列，显然这个序列要满足最后一个$$\mid 1$$要在$$\& 0$$之后

• ### BZOJ3453: tyvj 1858 XLkxc(拉格朗日插值)

$\sum_{i = 0} ^n \sum_{j = 1}^{a + id} \sum_{x =1}^j x^k \pmod P$

• ### 洛谷P4424 [HNOI/AHOI2018]寻宝游戏(思维题)

那么我们把每一列上的数和他之前的操作符分别拿出来看成一些序列，显然这个序列要满足最后一个$$\mid 1$$要在$$\& 0$$之后

• ### 1466: [蓝桥杯2019初赛]等差数列

数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一部分的数列，只记得其中N 个整数。现在给出这N 个整数，小明想知道包含这N 个整数的最短的等差数...

• ### BZOJ3453: tyvj 1858 XLkxc(拉格朗日插值)

$\sum_{i = 0} ^n \sum_{j = 1}^{a + id} \sum_{x =1}^j x^k \pmod P$

• ### 海量数据处理之bitmap

本文将讲述Bit-Map算法的相关原理,Bit-Map算法的一些利用场景，例如BitMap解决海量数据寻找重复、判断个别元素是否在海量数据当中等问题.最后说说B...