[luogu P2184] 贪婪大陆 [树状数组][线段树]
2024-10-20 16:46:55
题目背景
面对蚂蚁们的疯狂进攻,小FF的Tower defence宣告失败……人类被蚂蚁们逼到了Greed Island上的一个海湾。现在,小FF的后方是一望无际的大海, 前方是变异了的超级蚂蚁。 小FF还有大好前程,他可不想命丧于此, 于是他派遣手下最后一批改造SCV布置地雷以阻挡蚂蚁们的进攻。
题目描述
小FF最后一道防线是一条长度为N的战壕, 小FF拥有无数多种地雷,而SCV每次可以在[ L , R ]区间埋放同一种不同于之前已经埋放的地雷。 由于情况已经十万火急,小FF在某些时候可能会询问你在[ L' , R'] 区间内有多少种不同的地雷, 他希望你能尽快的给予答复。
对于30%的数据: 0<=n, m<=1000;
对于100%的数据: 0<=n, m<=10^5.
输入输出格式
输入格式:
第一行为两个整数n和m; n表示防线长度, m表示SCV布雷次数及小FF询问的次数总和。
接下来有m行, 每行三个整数Q,L , R; 若Q=1 则表示SCV在[ L , R ]这段区间布上一种地雷, 若Q=2则表示小FF询问当前[ L , R ]区间总共有多少种地雷。
输出格式:
对于小FF的每次询问,输出一个答案(单独一行),表示当前区间地雷总数。
输入输出样例
输入样例#1:
5 4
1 1 3
2 2 5
1 2 4
2 3 5
输出样例#1:
1
2
思路题TAT 向思路题低头
开两个树状数组表示1...x放置的left数量和right数量
对于询问(l,r),要求的显然是1...r的left数量减去1...l的right数量
#include<cstdio>
using namespace std; inline int read(){
char ch;
int re=;
bool flag=;
while((ch=getchar())!='-'&&(ch<''||ch>''));
ch=='-'?flag=:re=ch-'';
while((ch=getchar())>=''&&ch<='') re=re*+ch-'';
return flag?-re:re;
} const int maxn=1e5+,maxm=1e5+; int n,m,bit[maxn],bitt[maxn]; void add(int *b,int x){ for(int i=x;i<=n;i+=i&-i) b[i]++; }
int gsum(int *b,int x){ int sum=; for(int i=x;i;i-=i&-i) sum+=b[i]; return sum; } int main(){
n=read(); m=read();
for(int i=;i<m;i++){
int op=read(),ll=read(),rr=read();
switch(op){
case : add(bit,ll); add(bitt,rr); break;
case : printf("%d\n",gsum(bit,rr)-gsum(bitt,ll-)); break;
}
}
return ;
}
任你去山高水远
你永远在我的心间
最新文章
- C++中 vector(容器)的用法
- sharepoint webpart
- 服务链(Service Chaining,or Service Function Chaining,SFC,功能服务链)
- &#39;<;&#39;, hexadecimal value 0x3C, is an invalid 问题解决
- 解决:HttpClient导致应用出现过多Close_Wait的问题
- thinkphp中模板继承
- jquery给height拼接动态变量
- 夺命雷公狗jquery---1选择元素的3种方法
- 【UEditor】远程上传图片到【七牛云存储】
- 关于帝国cms 列表页SEO优化的问题
- C++ 11 笔记 (四) : std::bind
- gvim生存配置
- 对着java并发包写.net并发包之原子类型实现
- 用JS编写个人所得税计算器
- _sntprintf_s 和 _sntprintf 区别
- CentOS 6.5 x64下安装VMware tools
- Unty中通过镜像优化HDRI全景图体积
- Rancher2.0中邮件通知的设置
- 微信小程序- 提示不在以下合法域名列表中
- 终端:Xcode模拟器上安装.app方法
热门文章
- 每天一个JS 小demo之新建文件夹。主要知识点:DOM方法的综合运用
- XML配置文件中写版本号.xsd和不写版本号的区别
- idea live template高级知识, 进阶(给方法,类,js方法添加注释)(二)
- php中引用&;的一个小实例
- Hadoop 笔记1 (原理和HDFS分布式搭建)
- jmeter3.2版本完美实现Load Test报表
- 在Cenos系统安装Python3.5版本,使P2和P3共存
- php产生随机字符串
- php5.6在yum下安装gd库
- SQLyog简介