两篇讲解线段树的文章 链接1 链接2
目录
POJ - 3468
简单线段树。
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<string>
using namespace std;
const int maxn=100010;
int arr[maxn];
long long ans=0;
struct node
{
int l,r;
long long w;
long long add;
};
node t[maxn*4];
long long up(int k)
{
t[k].w=t[2*k].w+t[2*k+1].w;
return t[k].w;
}
void down(int k)
{
if(t[k].add!=0)
{
t[2*k].add+=t[k].add;
t[2*k+1].add+=t[k].add;
t[2*k].w+=(t[2*k].r-t[2*k].l+1)*t[k].add;
t[2*k+1].w+=(t[2*k+1].r-t[2*k+1].l+1)*t[k].add;
t[k].add=0;
}
}
void build(int l,int r,int k)
{
t[k].l=l;t[k].r=r;t[k].add=0;
if(l==r)
{
return;
}
int mid=(l+r)/2;
build(l,mid,2*k);
build(mid+1,r,2*k+1);
up(k);
}
void update(int l,int r,int add,int k)
{
if(t[k].l>=l&&t[k].r<=r)
{
t[k].w+=(t[k].r-t[k].l+1)*add;
t[k].add+=add;
return;
}
down(k);
int mid=(t[k].l+t[k].r)/2;
if(l<=mid) update(l,r,add,2*k);
if(r>mid) update(l,r,add,2*k+1);
up(k);
}
void query(int l,int r,int k)
{
if(t[k].l>=l&&t[k].r<=r)
{
ans+=t[k].w;
return;
}
down(k);
int mid=(t[k].l+t[k].r)/2;
if(l<=mid) query(l,r,2*k);
if(r>mid) query(l,r,2*k+1);
}
int main()
{
ios::sync_with_stdio(false);
long long a,b,c;
long long n,q;
cin>>n>>q;
for(int i=1;i<=n;i++)
cin>>arr[i];
build(1,n,1);
for(int i=1;i<=n;i++)
update(i,i,arr[i],1);
while(q--)
{
ans=0;
char ch;
cin>>ch;
if(ch=='C')
{
cin>>a>>b>>c;
update(a,b,c,1);
}
if(ch=='Q')
{
cin>>a>>b;
query(a,b,1);
cout<<ans<<endl;
}
}
return 0;
}HDU - 1698
简单线段树。
这题检查了很久才检查出错误！！服了我，因为自己的不细心光顾着套模板，检查的时候还照着别人的代码对了半天也没找出错误，最后才知道是自己的mid写错了！！！ 以后检查的时候一定要自己理解代码，不能照着别人的代码对。
#include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;
const int maxn=100010;
struct node
{
int l,r;
long long w,add;
};
node t[maxn*4];
void down(int k)
{
if(t[k].add!=0)
{
t[2*k].add=t[k].add;
t[2*k+1].add=t[k].add;
t[2*k].w=(t[2*k].r-t[2*k].l+1)*t[k].add;
t[2*k+1].w=(t[2*k+1].r-t[2*k+1].l+1)*t[k].add;
t[k].add=0;
}
}
void up(int k)
{
t[k].w=t[2*k].w+t[2*k+1].w;
}
void build(int l,int r,int k)
{
t[k].l=l;
t[k].r=r;
t[k].add=0;
if(l==r)
{
t[k].w=1;
return;
}
int mid=(l+r)/2;
build(l,mid,2*k);
build(mid+1,r,2*k+1);
up(k);
}
void update(int l,int r,int add,int k)
{
if(t[k].l>=l&&t[k].r<=r)
{
t[k].w=(t[k].r-t[k].l+1)*add;
t[k].add=add;
return;
}
down(k);
int mid=(t[k].r+t[k].l)/2; ///!!!!!!!!!!!!!!!!!
if(l<=mid) update(l,r,add,2*k);
if(r>mid) update(l,r,add,2*k+1);
up(k);
}
int main()
{
// freopen("in.txt","r",stdin);
ios::sync_with_stdio(false);
int T;
cin>>T;
for(int i=1;i<=T;i++)
{
int n,q;
cin>>n>>q;
build(1,n,1);
while(q--)
{
int x,y,z;
cin>>x>>y>>z;
update(x,y,z,1);
}
cout<<"Case "<<i<<": The total value of the hook is "<<t[1].w<<"."<<endl;
}
return 0;
}
HDU - 1542 线段树+扫描线+离散化
这是第一道接触扫描线和离散化的题目 看了别人的代码照猫画虎写的。
关于本题的题解：题解1 题解2和题解3
（题解1讲的比较清楚，题解2和3一样。刚开始先看的题解3看懂个大概但是没看太明白，后来看的题解1 懂了大部分）
关于离散化的知识点：链接1
关于扫描线的知识点上面题解中也有讲。这里还看到了一篇关于扫描线的链接2
关于这个题比较重要的一点是：
实际上这个线段树的叶子节点保存的是这个点x坐标到下一个x坐标（排序后的）的区间长度。
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=210;
struct edge//边
{
double l,r,h;
int f;
bool operator <(const edge &t1) const{
return h<t1.h;
}
};
struct node
{
int l,r;
double len;
int d;///线段树的懒惰标记
};
double x[maxn];//横坐标
edge e[maxn];//边
node t[maxn*4];//线段树
void build(int l,int r,int k)
{
t[k].l=l;t[k].r=r;
t[k].len=0;t[k].d=0;
if(l==r)
return;
int mid=(l+r)/2;
build(l,mid,2*k);
build(mid+1,r,2*k+1);
}
void pushup(int k)
{
if(t[k].d)//说明这条线段完整覆盖
t[k].len=x[t[k].r+1]-x[t[k].l];
else if(t[k].l==t[k].r)//说明这条线段是一个点
t[k].len=0;
else//说明这条线段部分覆盖
t[k].len=t[2*k].len+t[2*k+1].len;
}
void update(int l,int r,int k,int ff)//ff相当于线段树的懒惰标记
{
if(t[k].l>=l&&t[k].r<=r)
{
t[k].d+=ff;
pushup(k);
return;
}
///一定是当前节点线段的终点，不是l,r的中点！这个地方老是写错
int mid=(t[k].l+t[k].r)/2;///!!!
if(l<=mid) update(l,r,2*k,ff);
if(r>mid) update(l,r,2*k+1,ff);
pushup(k);
}
int main()
{
// freopen("in.txt","r",stdin);
int n;
int Case=0;
while(scanf("%d",&n)&&n)
{
Case++;
memset(x,0,sizeof(x));
memset(e,0,sizeof(struct edge)*maxn);
memset(t,0,sizeof(struct node)*maxn*4);
double x1,y1,x2,y2;
int kase=0;
for(int i=0;i<n;i++)
{
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
e[kase].l=x1;
e[kase].r=x2;
e[kase].h=y1;
e[kase].f=1;//上边
e[kase+1].l=x1;
e[kase+1].r=x2;
e[kase+1].h=y2;
e[kase+1].f=-1;//下边
x[kase]=x1;
x[kase+1]=x2;
kase+=2;//每一个i都对应两条边
}
sort(x,x+kase);
sort(e,e+kase);
int m=unique(x,x+kase)-x;//m为去重后x[]数组的长度
build(0,m-1,1);
double ans=0;
for(int i=0;i<kase;i++)//一共kase-1条边
{
int l=lower_bound(x,x+m,e[i].l)-x;
int r=lower_bound(x,x+m,e[i].r)-x-1;
update(l,r,1,e[i].f);
ans+=t[1].len*(e[i+1].h-e[i].h);
}
printf("Test case #%d\n",Case);
printf("Total explored area: %.2f\n\n",ans);
}
return 0;
}
版权声明：本文为an94460061原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。