codevs——1081 线段树练习 2
2024-08-30 06:53:07
题目描述 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
#include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define N 400010 using namespace std; int x,y,z,p,n,m,ans; int read() { ,f=; char ch=getchar(); ; ch=getchar();} +ch-'; ch=getchar();} return x*f; } struct noid { int l,r,w,f; }tree[N]; void build(int l,int r,int k) { tree[k].l=l,tree[k].r=r; if(l==r) { x=read(),tree[k].w=x; return ; } ; build(l,m,k<<),build(m+,r,(k<<)+); tree[k].w].w+tree[(k<<)+].w; } void down(int k) { tree[k<<].f+=tree[k].f; tree[(k<<)+].f+=tree[k].f; tree[k<<].w+=(tree[k<<].r-tree[k<<].l+)*tree[k].f; tree[(k<<)+].w)+].r-tree[(k<<)+].l+)*tree[k].f; tree[k].f=; } void add(int k) { if(tree[k].l>=x&&tree[k].r<=y) { tree[k].w+=(tree[k].r-tree[k].l+)*z; tree[k].f+=z; return ; } if(tree[k].f) down(k); ; ); )+); tree[k].w=tree[k<<].w+tree[(k<<)+].w; } void ask(int k) { if(tree[k].l==tree[k].r) { ans=tree[k].w; return ; } if(tree[k].f) down(k); ; ); )+); } int main() { n=read();build(,n,); m=read(); while(m--) { p=read(); ){x=read(),y=read(),z=read(),add();} ),printf("%d\n",ans);} } ; }
最新文章
- C#中获取当前时间:System.DateTime.Now.ToString()用法
- java java.lang.NoClassDefFoundError 的解决办法
- React(JSX语法)----动态UI
- Office Online简介
- [转载]Nginx如何处理一个请求
- 减肥App计划
- HTTP,HTTP2.0,SPDY,HTTPS你应该知道的一些事
- HTML_常见命令学习笔记
- [转]Linux下转换字符集(UTF8转换)
- Python学习笔记——基础篇【第七周】———进程、线程、协程篇(socket基础)
- Mysql group by,order by,dinstict优化
- jquery制作移动端菜单栏左右滑动
- python3用BeautifulSoup抓取id=&#39;xiaodeng&#39;,且正则包含‘elsie’的标签
- nodejs 负载均衡
- C#调用C++ DLL的方式
- WPF样式动画Trigger.EnterActions和Trigger.ExitActions(ExitActions其实可以不做任何事情)
- ubuntu16.04 安装opencv3
- hdu 1423(LCS+LIS)
- ORACL EXP导出数据说明
- UITableView分隔线
热门文章
- 安装JPype时出现的 Unable to find vcvarsall.bat
- CCF|碰撞的小球
- greenplum4.3.8.2安装
- Katalon Studio 安装 配置 简单使用
- 迅为iTOP-4418开发板串口虚拟控制台配置为普通串口
- 【转帖】迅为iTOP-iMX6开发板 Ubuntu系统下WiFi模块mt6620的移植
- jQuery 点击 星星评分
- Windows:32位程序运行在64位系统上注册表会重定向
- No-4.变量的基本使用
- ios中摄像头/相册获取图片压缩图片上传服务器方法总结