Codevs 1081 线段树练习2
2024-08-22 17:24:41
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 大师 Master
题目描述 Description
给你N个数,有两种操作
1:给区间[a,b]的所有数都增加X
2:询问第i个数是什么?
输入描述 Input Description
第一行一个正整数n,接下来n行n个整数,再接下来一个正整数Q,表示操作的个数. 接下来Q行每行若干个整数。如果第一个数是1,后接3个正整数a,b,X,表示在区间[a,b]内每个数增加X,如果是2,后面跟1个整数i, 表示询问第i个位置的数是多少。
输出描述 Output Description
对于每个询问输出一行一个答案
样例输入 Sample Input
3
1
2
3
2
1 2 3 2
2 3
样例输出 Sample Output
5
数据范围及提示 Data Size & Hint
数据范围
1<=n<=100000
1<=q<=100000
树状数组:(数据太弱,暴力都AC)
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,t[];
void add(int k,int z)
{
while(k<=n)
{
t[k]+=z;
k+=k&(-k);
}
}
int find(int x)
{
int ans=;
while(x)
{
ans+=t[x];
x-=x&(-x);
}
return ans;
}
int main()
{
cin>>n;
for(int i=;i<=n;i++)
{
int x;
cin>>x;
add(i,x);
}
cin>>m;
for(int i=;i<=m;i++)
{
int a,b,c,d,e,f;
cin>>a;
if(a==) {
cin>>d>>e>>f;
for(int j=d;j<=e;j++)
add(j,f);
}
if(a==)
{
cin>>b;
printf("%d\n",find(b)-find(b-));
}
} return ;
}
用的是练习1的代码,稍加修改,加上数据太弱~~~~~~就AC啦~~
正解:(区间修改+单点查询)
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 100010
using namespace std;
int n,m,a[maxn],t[maxn];
void add(int k,int z)
{
while(k<=n)
{
t[k]+=z;
k+=k&(-k);
}
}
int find(int k)
{
int ans=;
while(k)
{
ans+=t[k];
k-=k&(-k);
}
return ans;
}
int main()
{
int i,j,k;
scanf("%d",&n);
for(i=;i<=n;i++)
scanf("%d",&a[i]);
for(i=;i<=n;i++)
add(i,a[i]-a[i-]);
scanf("%d",&m);
for(i=;i<=m;i++)
{
int x,y,z,w;
scanf("%d",&w);
if(w==)
{
scanf("%d%d%d",&x,&y,&z);
add(x,z);
add(y+,-z);
}
else
if(w==)
{
scanf("%d",&x);
printf("%d\n",find(x));
}
}
return ;
}
思想 :t数组存放差分序列即a[i]-a[i-1],区间修改时 只需修改 两端点处的值即可【左端点加X,右端点减X】 单点查询时:输出从差分序列从1到i的和
图片有点烂,将就看吧
最新文章
- SQL Server 服务器磁盘测试之SQLIO篇(二)
- 【总结】JS里的数组排序
- 分布式服务框架 Zookeeper(转)
- Java script基础
- SQL2008-不同数据库之间的触发器
- Linux学习笔记17——输入输出重定向
- Android Listview异步动态加载网络图片
- 用Unicode迎接未来
- Vuejs环境安装与工程建立【小白Windows向】
- IntelliJ IDEA运行项目成功后,无法访问Tomcat主页
- layer.js 中弹框显示不全的问题
- MongoDB 常用的几大GUI工具
- Django学习---py3下的富文本编辑器的使用
- java从命令行接受多个数字求和输出
- Java读取修改Properties文件
- phpstorm设置断点过程
- struts2用到的jar有那些
- C指针和数组
- BrowserSync-多浏览器测试工具
- 2014小米,百度,pptv,去哪儿笔试题目回忆
热门文章
- 【Oracle】ORA-00600: [kfgFinalize_2]
- Foundation框架之NSString及其Mutable类型
- 关于JS加载的问题
- xcode中没有autoSizing的设置
- Windows内存管理和linux内存管理
- scala命令
- QStyle 新风格的实现
- 如何编写自己的Linux安全检查脚本?
- 如何让静态库中的可执行程序不调用的函数不链接进该可执行程序?(-ffunction-sections -Wl,--gc-sections)
- entity framework 连接 oracle 发布后出现的问题(Unable to find the requested .Net Framework Data Provider)