HDU 4638 Group ★(树状数组)
题意
询问一段区间里的数能组成多少段连续的数。
思路
先考虑从左往右一个数一个数添加,考虑当前添加了i - 1个数的答案是x,那么可以看出添加完i个数后的答案是根据a[i]-1和a[i]+1是否已经添加而定的:如果a[i]-1或者a[i]+1已经添加一个,则段数不变,如果都没添加则段数加1,如果都添加了则段数减1。设v[i]为加入第i个数后的改变量,那么加到第x数时的段数就是sum{v[i]} (1<=i<=x}。当然,若删除某个数,那么这个数两端的数的改变量也会跟着改变,这样一段区间的数构成的段数就还是他们的v值的和。将询问离线处理,按左端点排序后扫描一遍,左边删除,右边插入,查询就是求区间和。
区间和用线段树或者树状数组维护都可以。当然本题自然是树状数组最好了~空间少,常数小,还好写。借此也学了一下树状数组。很赞啊!倍增、分割思想,不到十行的代码,啧啧~
代码
#include
#include
#include
#include
#include
#include
#include
#define MID(x,y) ((x+y)/2)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;const int MAXN = 100005;
struct BIT{
int t[MAXN= 1; i -= lowbit(i))
res += t[i];
return res;
}
}bit;
int a[MAXN], pos[MAXN];
struct ask{
int l, r, id;
}q[MAXN];
bool cmp(ask n1, ask n2){
if (n1.l == n2.l)
return n1.r st){
if (pos[a[st]-1] > st && a[st] > 1) bit.update(pos[a[st]-1], 1);
if (pos[a[st]+1] > st && a[st]最新文章
- Visual Studio 2013中因SignalR的Browser Link引起的Javascript错误一则
- Orchard源码分析(1):Orchard架构
- 【BZOJ】2172: Mario填格子
- HVTableView 分享组
- notepad++ tab键用空格缩进
- SL410K 在Ubuntu禁用触摸板
- iOS 对网络视频采集视频截图
- WCF中修改接口或步骤名称而不影响客户端程序
- Android源码编译过程之九鼎开发板
- PHP ajax实现数组返回
- Dialog( 对话框) 组件
- 移动前端不得不了解的HTML5 head 头标签(首篇)
- 关于table参数的一些问题
- hdu_5738_Eureka(脑洞)
- 把一个DIV放到另一个div右下角
- 调用sed命令的三种方式
- sqlmap Bool型&;延时型 检测策略分析
- Gruntfile.js模板
- requests库详解 --Python3
- 头像修改功能 包含ios旋转图片 但是旋转后没遮罩, 正常图片可以显示遮罩 宽高不规则图片没做控制 遮罩框可以拖动
热门文章
- 2013 Asia Hangzhou Regional Contest
- GridView 服务端控件添加 js
- 腾讯QQ企业邮箱在ruby on rails 框架中的mailer配置
- leetcode Largest Rectangle in Histogram 解法二
- POJ 2528 Mayor&#39;s posters (线段树,染色问题,离散化要注意)
- Struts2 常用的常量配置
- Android 监测手机联网状态 wifi、移动数据流量、无联网状态
- Oracle 学习笔记(二)
- struts2学习笔记(2)——简单的输入验证以及标签库的运用
- lintcode : 空格替换