博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
线段树模板
阅读量:6536 次
发布时间:2019-06-24

本文共 1519 字,大约阅读时间需要 5 分钟。

#include
using namespace std;const int maxn=10010;int s[maxn*4],col[maxn*4];//懒标记和线段树void down(int p,int l,int r){ if(col[p])//当前节点有懒标记 { int mid=(l+r)/2; s[p*2]+=col[p]*(mid-l+1);//左区间元素个数乘以加上的值 s[p*2+1]+=col[p]*(r-mid);//右区间元素个数乘以加上的值 col[p*2]+=col[p]; col[p*2+1]+=col[p]; col[p]=0;//取消当前懒标记 }}void up(int p){ s[p]=s[p*2]+s[p*2+1];} void modify(int p,int l,int r,int x,int y,int c){ if(l>=x&&r<=y)//找到了更新区间 { s[p]+=(r-l+1)*c;//闭区间所以+1 col[p]+=c;//打上懒标记 return; } down(p,l,r);//下放懒标记 int mid=(r+l)/2; if(x<=mid)//若目标在左区间 { modify(p*2,l,mid,x,y,c); } if(y>mid)//若目标在右区间 { modify(p*2+1,mid+1,r,x,y,c); } up(p);//回溯时向上更新 }int query(int p,int l,int r,int x,int y){ if(l>=x&&r<=y) { return s[p]; } down(p,l,r);//下放懒标记 int mid=(r+l)/2,res=0; if(x<=mid) { res+=query(p*2,l,mid,x,y); } if(y>mid) { res+=query(p*2+1,mid+1,r,x,y); }//答案有可能夹在两个区间之间 return res;//记得返回答案 }int main(){ memset(s,0,sizeof(s)); memset(col,0,sizeof(col)); int n,t; cin>>n>>t;//区间1~n和修改数据组数 for(int i=1;i<=n;i++) { modify(1,1,n,i,i,0); } for(int i=1;i<=t;i++) { int a,b,c; cin>>a>>b>>c; modify(1,1,n,a,b,c); } int m;//查找数据组数 cin>>m; for(int i=1;i<=m;i++) { int x,y; cin>>x>>y; cout<
<

 

转载于:https://www.cnblogs.com/KyleDeng/p/9294365.html

你可能感兴趣的文章
小P寻宝记——粗心的基友 背包
查看>>
进程基础复习01
查看>>
深圳富士康应聘者:我们就是想进这打工(组图)
查看>>
【2781】二分练习 sdutOJ
查看>>
Hadoop综合大作业
查看>>
android:exported 属性详解
查看>>
性能测试之三 如何计算评估用户数与压力
查看>>
Springboot 编码规范
查看>>
JOptionPane类提示框常用方法总结
查看>>
Solr简单测试
查看>>
Ubuntu Server对OpenStack的支持
查看>>
American Metric 电子产品调查表
查看>>
团队项目选题报告(I know)
查看>>
团队-象棋游戏-项目总结
查看>>
命令行打开各组件
查看>>
安装 SQL server 2008 R2
查看>>
03 - const static extern
查看>>
向studio项目中复制集成其他代码,项目R文件丢失
查看>>
查找最相近的字符串
查看>>
js刷新页面方法大全(转)
查看>>