BZOJ2683: 简单题(cdq分治 树状数组)
2018-07-09 13:25:17来源:博客园 阅读 ()
Submit: 2142 Solved: 874
[Submit][Status][Discuss]
Description
命令 |
参数限制 |
内容 |
1 x y A |
1<=x,y<=N,A是正整数 |
将格子x,y里的数字加上A |
2 x1 y1 x2 y2 |
1<=x1<= x2<=N 1<=y1<= y2<=N |
输出x1 y1 x2 y2这个矩形内的数字和 |
3 |
无 |
终止程序 |
Input
Output
Sample Input
1 2 3 3
2 1 1 3 3
1 2 2 2
2 2 2 3 4
3
Sample Output
5
HINT
Source
cdq分治裸题。
首先我们对询问点拆为$4$个前缀和查询
再把所有的询问/修改离线,按照$x$轴排序
直接上cdq分治,用树状数组为护$y$轴的贡献
归并排序版太难写了直接上sort
#include<cstdio> #include<algorithm> #define lowbit(x) ((x) & (-x)) using namespace std; const int MAXN = 5 * 1e5 + 10; 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, Qnum; struct Query { int opt, x, y, v, ans, xxx; bool operator < (const Query &rhs) const { return x == rhs.x ? y < rhs.y : x < rhs.x; } }Q[MAXN], Tp[MAXN]; int T[MAXN]; void Add(int pos, int val) { for(int i = pos; i <= N; i += lowbit(i)) T[i] += val; } int Sum(int pos) { int ans = 0; for(int i = pos; i; i -= lowbit(i)) ans += T[i]; return ans; } int num = 0, out[MAXN]; 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, last = 0; sort(Q + l, Q + mid + 1); sort(Q + mid + 1, Q + r + 1); while(j <= r) { while(Q[i].opt == 2 && i <= mid) i++; while(Q[j].opt == 1 && j <= r) j++; if(i <= mid && Q[i].x <= Q[j].x) Add(Q[i].y, Q[i].v), last = i++; else if(j <= r) Q[j].ans += Sum(Q[j].y), j++; } for(int i = l; i <= last; i++) if(Q[i].opt == 1) Add(Q[i].y, -Q[i].v); } int main() { N = read(); for(;;) { int op = read(); if(op == 3) break; if(op == 1) {Q[++num].opt = op; Q[num].x = read(), Q[num].y = read(), Q[num].v = read();} else { int xx1 = read(), yy1 = read(), xx2 = read(), yy2 = read(); Qnum++; Q[++num] = (Query) {op, xx2, yy2, 1, 0, Qnum}; Q[++num] = (Query) {op, xx1 - 1, yy1 - 1, 2, 0, Qnum}; Q[++num] = (Query) {op, xx1 - 1, yy2, 3, 0, Qnum}; Q[++num] = (Query) {op, xx2, yy1 - 1, 4, 0, Qnum}; } } CDQ(1, num); for(int i = 1; i <= num; i++) { if(Q[i].opt == 2) { if(Q[i].v == 1 || Q[i].v == 2) out[Q[i].xxx] += Q[i].ans; else out[Q[i].xxx] -= Q[i].ans; } } for(int i = 1; i <= Qnum; i++) printf("%d\n", out[i]); return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 加边的无向图--并查集 2020-04-10
- 排兵布阵 2020-02-21
- 二叉树(四)二叉堆 2020-02-03
- 一款简单的C++猜数字游戏(新手必学) 2019-12-10
- 《大话设计模式》之简单工厂模式 2019-11-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