BZOJ3262: 陌上花开(cdq分治)
2018-07-09 13:25:14来源:博客园 阅读 ()
Submit: 3627 Solved: 1705
[Submit][Status][Discuss]
Description
Input
Output
包含N行,分别表示评级为0...N-1的每级花的数量。
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
Source
感觉cdq分治和归并排序很像qwq。
第一维可以用排序搞掉
这样我们用cdq分治统计$(l,r)$这段区间的时候只需要考虑$b$和$c$的贡献,而且只需要考虑区间$(l, mid)$对$mid + 1, r$的贡献
用树状数组维护第三维的贡献
#include<cstdio> #include<algorithm> #define lowbit(x) ((x) & (-x)) using namespace std; const int MAXN = 200001; inline int read() { 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 N = read(); Max = read(); 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; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- BZOJ3295: [Cqoi2011]动态逆序对(cdq分治) 2018-07-12
- BZOJ2683: 简单题(cdq分治 树状数组) 2018-07-09
- bzoj1492 [ NOI2007 ] --斜率优化DP+cdq分治 2018-06-17
- bzoj3963 [ WF2011 ] --cdq分治 2018-06-17
- 洛谷P3374 【模板】树状数组 1(CDQ分治) 2018-06-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash