hdu(1166)——敌兵布阵(更新节点,区间求和)
发布日期:2021-09-19 06:09:12 浏览次数:0 分类:技术文章

这是一道最简单的线段树的更新节点与区间查询。

当然practic makes perfect~ 现在我已经能够比较熟练地打出来了。

但是还有一些细节要注意就是对于父节点的更新。

#include<stdio.h>#include<string.h>#include<algorithm>#include<iostream>using namespace std;#define maxn 55555char a[55];struct node{    int l,r,sum;    int add;}tree[maxn*4];int ans=0;void pushup(int v){    int temp=v*2;    tree[v].sum=tree[temp].sum+tree[temp+1].sum;}void pushdown(int v){    int temp=v*2;    tree[temp].add+=tree[v].add;    tree[temp+1].add+=tree[v].add;    tree[temp].sum+=tree[v].add*(tree[temp].r-tree[temp].l+1);    tree[temp+1].sum+=tree[v].add*(tree[temp+1].r-tree[temp+1].l+1);    tree[v].add=0;}void build(int l,int r,int v){    tree[v].l=l;     tree[v].r=r;    tree[v].add=0;    if(l==r){        scanf("%d",&tree[v].sum);        return;    }    int temp=v*2;    int mid=(tree[v].l+tree[v].r)/2;    build(l,mid,temp);    build(mid+1,r,temp+1);    pushup(v);}void update(int pos,int v,int x){    if(pos==tree[v].l&&tree[v].r==pos){        tree[v].add+=x;        tree[v].sum+=x*(tree[v].r-tree[v].l+1);        return ;    }    if(tree[v].add) pushdown(v);    int mid=(tree[v].l+tree[v].r)/2;    int temp=v*2;    if(pos<=mid) update(pos,temp,x);    else update(pos,temp+1,x);    pushup(v);            //!!!}void query(int l,int r,int v){    if(r<tree[v].l||tree[v].r<l) return;    if(l<=tree[v].l&&tree[v].r<=r){        ans+=tree[v].sum;        return;    }    if(tree[v].add) pushdown(v);    int mid=(tree[v].l+tree[v].r)/2;    int temp=v*2;    if(r<=mid) query(l,r,temp);    else if(mid<l) query(l,r,temp+1);    else{        query(l,mid,temp);        query(mid+1,r,temp+1);    }}int main(){    int T,n;    int j=1;    scanf("%d",&T);    while(T--){        scanf("%d",&n);        ans=0;        bool ff=false;        build(1,n,1);        #if 1        while(1){            scanf("%s",a);            if(strcmp(a,"End")==0) break;            if(strcmp(a,"Add")==0){                int r,s;                scanf("%d%d",&r,&s);                update(r,1,s);            }            if(strcmp(a,"Sub")==0){                int r,s;                scanf("%d%d",&r,&s);                update(r,1,-s);            }            if(strcmp(a,"Query")==0){                ans=0;                int r,s;                scanf("%d%d",&r,&s);                query(r,s,1);                if(!ff) printf("Case %d:\n",j++),ff=true;                printf("%d\n",ans);            }        }        #endif    }}


上一篇:hdu(1754)——I hate it(更新节点,区间最值)
下一篇:Codeforces Round #306 (Div. 2)

关于作者

    白红宇是个全栈工程师,前端vue,小程序,app开发到后端框架设计,数据库设计,环境部署上线运维。

最新文章

被调用的对象已与其客户端断开连接_初学面向对象--大话设计模式一书读后感(各模式总结)... 2021-09-12
影子卫士和影子系统哪个好用_哪个重装系统软件好用,怎么用 2021-09-12
python中给csv替换数据_Python把csv数据写入list和字典类型的变量脚本方法 2021-09-12
python雪花_python实现的雪花算法一枚 2021-09-12
python sklearn_【Python】使用Python进行主成分分析,,使用sklearn库 2021-09-12
python格式规范的要求_Python程序格式规范 2021-09-12
电脑磁盘空间不足怎么办_笔记本电脑接口不足怎么办?这个物件全搞定 2021-09-12
vivo手机怎么投屏到电脑_电脑手机一键投屏 2021-09-12
电脑耳机声音小怎么调大_win764位系统电脑音箱耳机都无声音的问题 2021-09-12
java程序设计_Java面向对象程序设计教与学(耿祥义,教学大纲和教案) 2021-09-12
苹果手机显示iphone已停用连接itunes_实用技巧:iPhone 被锁了该怎么办? 2021-09-12
python多线程_备战Python面试(2) 多线程 2021-09-12
python黑色的界面-Pycharm设置界面全黑的方法 2021-09-12
pyqt5 html5兼容,PyQt5的QWebEngineView使用模板 2021-09-12
c语言如何标志置1与置0,c语言对于文本的基本操作 2021-09-12
c语言万年历一行打印两个月,c语言万年历同行输出两个月 2021-09-12
2009年C语言模拟题目2答案,计算机二级C语言模拟试题及答案解析 2021-09-12
c语言字符串倒序输出 指针,菜鸟求助-如何用指针法将一串字符按单词的倒序输出?如:i love yo... 2021-09-12
linux系统的终端窗口,在Linux系统桌面嵌入终端窗口 2021-09-12
linux脚本 X$ var,为什么Shell脚本比较经常使用x $ VAR = xyes? 2021-09-12