P2184 贪婪大陆 树状数组
2024-08-30 05:01:08
树状数组帅炸了。。。。又被一道水题轻虐,又被学长指出了一个错误。。。。我太菜了QAQ
开两个树状数组,一个记录左端点,一个记录右端点;
共有cnt(总数) - (<l的右端点数目) - (>r的右端点数目) 种地雷
#include<cstdio>
#include<iostream>
#define R register int
inline int g() {
R ret=,fix=; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-:fix;
do ret=ret*+(ch^); while(isdigit(ch=getchar())); return ret*fix;
}
int n,c[][],m,cnt;
inline int max(int a,int b) {return a>b?a:b;}
inline int lbt(int x) {return x&(-x);}
inline void add(int k,int pos) {for(;pos<=n;pos+=lbt(pos)) ++c[k][pos];}
inline int query(int k,int pos) { R ret=;
for(;pos;pos-=lbt(pos)) ret+=c[k][pos]; return ret;
}
signed main() {
n=g(),m=g();
for(R i=;i<=m;++i) {
R k=g(),l=g(),r=g();
if(k&) add(,l),add(,r),++cnt;
else printf("%d\n",cnt-query(,l-)-query(,n)+query(,r));
}
}
2019.04.07
最新文章
- 微信开发中遇到“当前页面的url未注册”问题
- Android学习笔记02-Mac下编译java代码
- erlang 查看进程相关信息
- 从 ALAsset 中取出属性
- Android自由行之走进zxing,轻松实现二维码扫描
- EF 4.1 学习资源汇总
- url特殊字符转义及解决方法
- Spring中的@scope注解
- Linux initramfs说明
- JavaScript开发者应懂的33个概念
- Codeforces 584E - Anton and Ira - [贪心]
- 使用rsync实现客户端与服务器端的文件同步与传送,重点是原理和参数解释
- Android Bitmap 缩放 旋转 水印 裁剪操作
- sdut2165 Crack Mathmen (山东省第二届ACM省赛)
- leetcode118
- 客户端与服务器端同步Evernote
- USACO 1.2.2 Transformations 方块转换
- python文件和目录操作方法
- MVC项目不同域之间的UrlRouting
- DB DBS 和DBMS区别