NYOJ116 士兵杀敌(二)(线段树区单点更新,区间求和,zkw线段树)

2023-10-06 00:19

本文主要是介绍NYOJ116 士兵杀敌(二)(线段树区单点更新,区间求和,zkw线段树),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目:

士兵杀敌(二)

时间限制: 1000 ms  |  内存限制: 65535 KB
难度: 5
描述

南将军手下有N个士兵,分别编号1到N,这些士兵的杀敌数都是已知的。

小工是南将军手下的军师,南将军经常想知道第m号到第n号士兵的总杀敌数,请你帮助小工来回答南将军吧。

南将军的某次询问之后士兵i可能又杀敌q人,之后南将军再询问的时候,需要考虑到新增的杀敌数。

输入
只有一组测试数据
第一行是两个整数N,M,其中N表示士兵的个数(1<N<1000000),M表示指令的条数。(1<M<100000)
随后的一行是N个整数,ai表示第i号士兵杀敌数目。(0<=ai<=100)
随后的M行每行是一条指令,这条指令包含了一个字符串和两个整数,首先是一个字符串,如果是字符串QUERY则表示南将军进行了查询操作,后面的两个整数m,n,表示查询的起始与终止士兵编号;如果是字符串ADD则后面跟的两个整数I,A(1<=I<=N,1<=A<=100),表示第I个士兵新增杀敌数为A.
输出
对于每次查询,输出一个整数R表示第m号士兵到第n号士兵的总杀敌数,每组输出占一行
样例输入
5 6
1 2 3 4 5
QUERY 1 3
ADD 1 2
QUERY 1 3
ADD 2 3
QUERY 1 2
QUERY 1 5
样例输出
6
8
8
20
来源
[张云聪]原创
上传者
张云聪
思路:

最基础的线段树裸题,当然树状数组也能做。和hdu那个排兵布阵一模一样,就不说了

代码:

#include <cstdio>
#include <cstring>
#include <cctype>
#include <string>
#include <set>
#include <iostream>
#include <stack>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>
#define mem(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
#define mod 10000007
#define debug() puts("what the fuck!!!")
#define N 1000020
#define M 1000000
#define ll long long
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1 //位运算,|可以理解为+
int sum[4*N];
void pushup(int rt)//更新该节点维护的值,求和
{sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void build(int l,int r,int rt)//建立线段树
{if(l==r){scanf("%d",&sum[rt]);return;}int m=(l+r)>>1;build(lson);build(rson);pushup(rt);
}
void update(int p,int add,int l,int r,int rt)//单点更新
{if(l==r){sum[rt]+=add;return;}int m=(l+r)>>1;if(p<=m)update(p,add,lson);elseupdate(p,add,rson);pushup(rt);
}
int query(int L,int R,int l,int r,int rt)//要查询的区间和当前的左右节点和根节点
{if(L<=l&&r<=R)//[l,r]∈[L,R]{return sum[rt];}int m=(l+r)>>1;//找中间点int ret=0;if(L<=m)  ret+=query(L,R,lson);if(R>m)   ret+=query(L,R,rson);return ret;
}
int main()
{int n,a,b,m;scanf("%d%d",&n,&m);build(1,n,1);//建立线段树char s[15];while(m--){scanf("%s",s);scanf("%d%d",&a,&b);if(s[0]=='Q')//queryprintf("%d\n",query(a,b,1,n,1));if(s[0]=='A')//addupdate(a,b,1,n,1);}return 0;
}


代码2(zkw线段树,206ms):

#include<cstdio>
#include<cstring>
#include<string>
#include<set>
#include<iostream>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
#define mem(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
#define mod 10000007
#define debug() puts("what the fuck!!!")
#define ll long long
using namespace std;
const int N=1000000+20;
int M,n,m,tree[N<<2];
void pushup(int i)//向上更新
{tree[i]=tree[i<<1]+tree[i<<1|1];
}
void update(int x,int v)//单点修改,把x的值增加v
{for(tree[x+=M]+=v,x>>=1; x; x>>=1)pushup(x);
}
int query(int l,int r)//求[l~r]的区间和
{int ans=0;//l^r^1判断是否是兄弟节点,>0时是兄弟节点//是兄弟是退出循环for(l=l+M-1,r=r+M+1; l^r^1; l>>=1,r>>=1){//l&1^1,r&1分别判断偶数和奇数if(l&1^1) ans+=tree[l^1];//l+1if(r&1)   ans+=tree[r^1];//r-1}return ans;
}
void build()
{for(M=1; M<n; M<<=1);for(int i=M+1; i<=M+n; i++)scanf("%d",&tree[i]);for(int i=M; i>=1; i--)pushup(i);
}
int main()
{char op[10];int a,b;scanf("%d%d",&n,&m);build();while(m--){scanf("%s%d%d",op,&a,&b);if(op[0]=='Q')printf("%d\n",query(a,b));elseupdate(a,b);}return 0;
}


这篇关于NYOJ116 士兵杀敌(二)(线段树区单点更新,区间求和,zkw线段树)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/152374

相关文章

Security OAuth2 单点登录流程

单点登录(英语:Single sign-on,缩写为 SSO),又译为单一签入,一种对于许多相互关连,但是又是各自独立的软件系统,提供访问控制的属性。当拥有这项属性时,当用户登录时,就可以获取所有系统的访问权限,不用对每个单一系统都逐一登录。这项功能通常是以轻型目录访问协议(LDAP)来实现,在服务器上会将用户信息存储到LDAP数据库中。相同的,单一注销(single sign-off)就是指

poj3468(线段树成段更新模板题)

题意:包括两个操作:1、将[a.b]上的数字加上v;2、查询区间[a,b]上的和 下面的介绍是下解题思路: 首先介绍  lazy-tag思想:用一个变量记录每一个线段树节点的变化值,当这部分线段的一致性被破坏我们就将这个变化值传递给子区间,大大增加了线段树的效率。 比如现在需要对[a,b]区间值进行加c操作,那么就从根节点[1,n]开始调用update函数进行操作,如果刚好执行到一个子节点,

hdu1394(线段树点更新的应用)

题意:求一个序列经过一定的操作得到的序列的最小逆序数 这题会用到逆序数的一个性质,在0到n-1这些数字组成的乱序排列,将第一个数字A移到最后一位,得到的逆序数为res-a+(n-a-1) 知道上面的知识点后,可以用暴力来解 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#in

hdu1689(线段树成段更新)

两种操作:1、set区间[a,b]上数字为v;2、查询[ 1 , n ]上的sum 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdl

hdu 1754 I Hate It(线段树,单点更新,区间最值)

题意是求一个线段中的最大数。 线段树的模板题,试用了一下交大的模板。效率有点略低。 代码: #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while

AI行业应用(不定期更新)

ChatPDF 可以让你上传一个 PDF 文件,然后针对这个 PDF 进行小结和提问。你可以把各种各样你要研究的分析报告交给它,快速获取到想要知道的信息。https://www.chatpdf.com/

GIS图形库更新2024.8.4-9.9

更多精彩内容请访问 dt.sim3d.cn ,关注公众号【sky的数孪技术】,技术交流、源码下载请添加微信:digital_twin123 Cesium 本期发布了1.121 版本。重大新闻,Cesium被Bentley收购。 ✨ 功能和改进 默认启用 MSAA,采样 4 次。若要关闭 MSAA,则可以设置scene.msaaSamples = 1。但是通过比较,发现并没有多大改善。

poj 1127 线段相交的判定

题意: 有n根木棍,每根的端点坐标分别是 px, py, qx, qy。 判断每对木棍是否相连,当他们之间有公共点时,就认为他们相连。 并且通过相连的木棍相连的木棍也是相连的。 解析: 线段相交的判定。 首先,模板中的线段相交是不判端点的,所以要加一个端点在直线上的判定; 然后,端点在直线上的判定这个函数是不判定两个端点是同一个端点的情况的,所以要加是否端点相等的判断。 最后

HDU4737线段树

题目大意:给定一系列数,F(i,j)表示对从ai到aj连续求或运算,(i<=j)求F(i,j)<=m的总数。 const int Max_N = 100008 ;int sum[Max_N<<2] , x[Max_N] ;int n , m ;void push_up(int t){sum[t] = sum[t<<1] | sum[t<<1|1] ;}void upd