AC. 梦想

frank_c1

[BZOJ 2683] 简单题

发布于2016年01月09日 | 暂无评论 | 709阅读 | CDQ分治,常用技巧

题目描述

你有一个N*N的棋盘,每个格子内有一个整数,初始时的时候全部为0,现在需要维护两种操作:
2016010701

输入格式

输入文件第一行一个正整数N;接下来每行一个操作。

输出格式

对于每个操作2,输出一个对应的答案。

数据范围

1<=N<=500000,操作数不超过200000个,内存限制20M。

对于100%的数据,操作1中的A不超过2000。

题目解析

标题是吸引你点进来。不过这题确实也说不上很难。

这道题本来以为二维树状数组什么的写一下就可以,然而突然发现棋盘大小如此不科学。以我目前所学,貌似在线有点难做(也是可以做的,详见[BZOJ 4066] 简单题,用的是KD-Tree)。考虑离线的做法,通过百度搜索算法得知本题竟是经典的CDQ分治。

CDQ分治主要是对操作进行二分。本题可以先把所有操作2拆分成四个子操作(方便计算),然后把所有操作按X-Y-K排序(K为操作类型)。用CDQ分治,每次把处理的区间按时间顺序分为左半区间和右半区间,按原来X-Y-K的顺序依次执行左半区间的修改操作,同时计算对右半区间询问操作的贡献(因为左半区间的修改一定对右半区间的询问有影响)。然后递归处理左半区间和右半区间。因为是按X-Y的顺序,所以我们可以用树状数组来支持修改和查询。记得每次处理完一个区间以后把树状数组清空。具体实现细节见代码。

本题双倍经验哦,还有一模一样的1176~~