感觉我整理数据结构的速度永远跟不上考试的速度啊…
那么！撰写日期是在7.17，在这一天的模拟赛的T2用到了线段树。虽然打出来了板子但是忘掉了一些东西。
就趁着这个机会AK线段树吧！！
----补于8.6
因为知识体系的庞大，所以这篇博文里包含了朴素线段树、Lazy标记、区间修改、扫描线、动态开点与线段树合并。
但动态开点于线段树合并由于彻底抛弃了某些常用概念。
------于 2019 11/11
猛然发现挂出来的线段树板子是个挂了的板子…原因是一个区间符号打错了。现已修正。
理论概念
线段树是基于分治思想的二叉树结构。树上的每一个节点都代表一个区间，其根节点就是整个统计范围（1-N），每一个叶节点就是长度为1的区间（也就是一个元素）。对于每个内部节点[l-r]，它的左节点是[l,mid]，右节点是[mid+1,r]，其中mid=(l+r)/2（向下取整）。
根据这些定义，我们大概也能判断他常用的题型了。什么区间最值啊之类的涉及区间的东西。因为他大多情况下是一颗比较完整的完全二叉树（我的意思是不会浪费特别大的空间…），所以我们一般用“父子二倍”的编号方法。即根节点编号为1。对于任意一个节点x，它的左节点为2x，右节点为2x+1。为了保证不会越界，对于N个叶节点的线段树，我们将数组的长度开到4N
搭建
线段树的基本用途就是对序列的维护，支持查询与修改指令。线段树可以非常方便的从下向上传递信息。我们举个区间最小值的例子（诶嘿就是要跟小蓝书反着走！），对于一个节点Data(l,r)，显然Data(l,r)=min(Data(l,mid),Data(mid+1,r))。所以啊，我们用一个结构体保存每个节点。每个节点就包括三个信息。区间左端点L，区间右端点R，和这个节点存放的值Data
那么接下来上一手区间最小值的代码233
struct S{ int l,r; int dat; }T[4*MAXN]; void build(int p,int l,int r){ T[p].l=l;//别问我P是什么东西，你用数组的时候总要有个下标的吧= = T[p].r=r; if(l==r){//叶子节点！！ T[p].dat=R[l]; return; } int mid=(T[p].l+T[p].r)/2; build(p*2,l,mid);//左节点 build(p*2+1,mid+1,r);//右节点 T[p].dat=min(T[p*2].dat,T[p*2+1].dat);//如果你想改成区间最大值，就把这个min函数改动一下好了。 } build(1,1,n);//入口
单点修改
这里支持的修改是单点，也就是一次只更改一个节点的值。你可以指定他改成某个元素或者令他进行计算以改变值。
在线段树中，根节点是各种指令的入口。我们需要从根节点出发，层层递归来找代表着所需区间的节点。然后从下往上更新。
下面上的是复杂度为O(log N)的单点修改
void change(int p,int x,int v){ //v是要减小的值，p是入口，x是所需更该节点的位置 if(T[p].l==T[p].r){ T[p].dat-=v; return; } int mid=(T[p].l+T[p].r)/2; if(x<=mid){ change(p*2,x,v); } else{ change(p*2+1,x,v); } T[p].dat=min(T[p*2].dat,T[p*2+1].dat); } change(1,x,v);//入口
区间修改
注意：为了把功能放在一起，所以我把这个知识点放在了单点修改下面。但这个知识点更接近于压轴难度。所以可以先看下面的查询功能，再来看这个区间修改。
（小声）怎么办小蓝书上并没有纯粹的区间修改…给了个例题还加持了数论的buff
啊数论啊！我数学蒟蒻啊兄Dei！！
好的我们换一个质朴的例题来打板子吧。
（说着他翻开了小蓝书的下一页，并发现了藏在延迟标记里的区间修改）
如果我们要修改区间，那么想想看，如何实现？
众所周知，OI的本质就是倒水（雾）。我们最轻松可以想到的是，直接循环调用单点修改。
那么我们本来高效的O(log N)就这么变成了O(N)！！！！这不能忍。可怎么想，这也没什么可优化的余地啊。那怎么办？
偷懒啊！
什么意思？我们仔细思考一下，这就和我们做作业是一个道理。最恐怖的不是你没做作业，最恐怖的是你废了一大堆时间做作业，老！师！不！检！查！(大雾！！！）
所以，我们就在他每次要求我们修改的时候，只要他不问，我就不修改！
那我怎么要在他问的时候还能让程序记着这个点要修改了再用呢？
这就是延迟标记（也有人叫懒惰/Lazy标记）的作用咯。
那也就是说，我们要在执行修改指令时，发现P点所在区间被完全覆盖时，可以立即返回，不过我们要留一个延迟标记再走。
在后续的指令中，往下递归的时候，如果发现了这里存在一个延迟标记，那么就根据这个标记的内容来更新下方的节点，同时清除这个标记，为下方的子节点打上标记。
故，这个标记的真正定义是：
这个节点曾经被修改，但其子节点尚未被更新。
请留意这个概念，因为犯错概率有点大…
下面放出代码，有些长。
#include<iostream> using namespace std; const int MAXN=100010; struct SegmentTree{ int l,r; long long sum,add;//这个add就是所谓的延迟标记！ }tree[MAXN*4]; int a[MAXN],n,m; void build(int p,int l,int r){ tree[p].l=l; tree[p].r=r;
tree[p].add=0; if(l==r){ tree[p].sum=a[l]; return ; } int mid=(l+r)/2; build(p*2,l,mid); build(p*2+1,mid+1,r); tree[p].sum=tree[p*2].sum+tree[p*2+1].sum; } void spread(int p){ if(tree[p].add){ //如果这个节点被标记了延迟标记 /* ----------Warning-------- 延迟标记的意义，是“这个节点曾经被修改，但其子节点尚未被更新。”也就是说，他自己已经更新过了 但他下面的子节点都没有更新。这就意味着我们遇到这个标记的时候，要对他的子节点进行更新。 */ tree[p*2].sum+=tree[p].add*(tree[p*2].r-tree[p*2].l+1);//更新左节点 tree[p*2+1].sum+=tree[p].add*(tree[p*2+1].r-tree[p*2+1].l+1);//更新右节点 tree[p*2].add+=tree[p].add;//给左节点打标 tree[p*2+1].add+=tree[p].add;//给右节点打标 tree[p].add=0;//清除p的标记 } } void change(int p,int l,int r,int d){ if(l<=tree[p].l&&r>=tree[p].r){ tree[p].sum+=(long long)d*(tree[p].r-tree[p].l+1);//更新该节点 tree[p].add+=d;//打上延迟标记 return ; } spread(p);//传播延迟标记 int mid=(tree[p].l+tree[p].r)/2; if(l<=mid){ change(p*2,l,r,d); } if(r>mid){ change(p*2+1,l,r,d); } tree[p].sum=tree[p*2].sum+tree[p*2+1].sum; } long long ask(int p,int l,int r){ if(l<=tree[p].l&&r>=tree[p].r){ return tree[p].sum; } spread(p); int mid=(tree[p].l+tree[p].r)/2; long long val=0; if(l<=mid){ val+=ask(p*2,l,r); } if(r>mid){ val+=ask(p*2+1,l,r); } return val; } int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i]; } build(1,1,n); while(m--){ char op[2];int l,r,d; cin>>op>>l>>r; if(op[0]=='C'){ cin>>d; change(1,l,r,d); } else{ cout<<ask(1,l,r)<<endl; } } }
区间查询
想查询某个区间的最值等等？就在这个功能里实现啦！
我们只需要从根节点开始，递归执行这样的操作：
//注：下面的l,r代表的是你需要查询的区间左端点、右端点。
1.若[l,r]完全覆盖了当前节点代表的区间，那么立即回溯，并将该节点的Data值作为候选答案
2.若左子节点和[l,r]有重叠部分，则递归访问左子节点
3.若右子节点与[l,r]有重叠，则递归访问右子节点
那么附上查询的代码
int ask(int p,int l,int r){ if(l<=T[p].l&&r>=T[p].r){ return T[p].dat; } int mid=(T[p].l+T[p].r)/2; int val=1<<30;//如果你要查询区间最大值，那么把这个值加个负号就好了。 if(l<=mid){ val=min(val,ask(p*2,l,r)); } if(r>mid){ val=min(val,ask(p*2+1,l,r)); } return val; }
合并
这个操作是在动态开点的线段树上进行的。
什么是动态开点？详见下文在对 A simple Problem with Integers 中的题解。
如果若干个线段树，他们都维护相同的区间[1,n]，那么它们对于各个子区间的划分是一致的。假设有m次单点修改的操作，每次在某一棵线段树上进行。所有操作完成，我们要把对应位置上的值想加，同时得到区间最大值。
对于这个问题，我们就可以用线段树合并来实现。我们依次合并这些线段树。在合并时，用两个指针p,q从两个根节点出发，以递归的方式同步遍历两棵树。确保他们总是代表相同的子区间。
1.若两者有一为空，则以非空者为合并后节点
2.若均不为空，则递归合并两颗左子树和右子树，然后删除q，以p为合并后的节点。自底部向上更新最值信息。
3.如果到达叶子节点，则直接把两个的最值相加
时间复杂度大约在O（m log n）
代码实现如下：
int merge(int p,int q,int l ,int r){ if(!p){ return q; } if(!q){ return p; } //如果有任意一边树为空，你不用进行合并 if(l==r){ //到达叶子 tr[p].dat+=tr[q].dat; return p; } int mid=(l+r)>>1; tr[p].lc=merge(tr[p].lc,tr[q].lc,l,mid);//递归合并左子树 tr[q].rc=merge(tr[p].rc,tr[q].lc,mid+1,r);//递归合并右子树 tr[p].dat=max(tr[tr[p].lc].dat,tr[tr[p].rc].dat);//更新 return p;//以p为合并后的节点，相当于删除了q }
题目中的Show Time
子题型—扫描线
-------补充于8月6日。不得不说线段树这个知识点是真的庞大…
什么是扫描线？既然是题型，那么就在题目里诠释掉吧。
Atlantis POJ1151
翻译的事情我就不去管了。相信各位都是英文鬼才，精通21国语言那种。
那说一下题目大意，给你N个矩形，矩形可能有重叠。求他们的面积并（也就是重叠部分只算一次）。
第一个数据给测试样例的个数…第二个数据给你个数，下面的数据给你他的顶点坐标………（这是为知识点服务的例题，所以我拒绝花大量功夫在诠释题意上）
那么扫描线是针对这种题型的经典做法。设想有一根线，从下向上抑或从左向右扫过去。那么只有两条矩形临界边会对覆盖面积的大小产生影响。
也就是说，我们从左向右（这里仅以从左向右举例）扫过去，记录下每个矩形的左边和右边。那么他在直线上留下的高度一定是固定的，假定为L。那么其面积一定为L*该段的宽度。
那么这条直线就是扫描线。我们需要取出N个矩形的左右边界，也就是有2N段边线，划分出了2N-1个区间。
我们可以把两个对角顶点坐标暂记为(x1,y1) (x2,y2)并假定x1<x2 , y1<y2
那么就将左边界标记为四元组(x1,y1,y2,1)
右边界标记为(x2,y1,y2,-1)
然后将这2N个四元组间按x进行排序。
但在本题中，y的数据范围不仅很大，而且甚至连整数都不是，所以我们不妨做一下离散化。这里用到一个离散化利器。为了让博文井然有序，我们选择引个超链。
利用sort unique 和Map可以简单的实现离散化。这里设raw(i)表示不同的y值
开一个数组c[i]来表示第i个区间的覆盖次数。c[i]的初始值为0
扫描一遍四元组。对于每一个四元组，我们将其raw(y1)到raw(y2)区间的每个raw[i]加上第四元值（1或者-1），表示覆盖或者结束覆盖。
既然我们要求面积，那如何求呢？长度乘以宽度。宽度一定为x2-x1，那么长度（即在扫描线的高度）是什么呢？
只要c[i]数组不为0，就意味着第i段依然有覆盖。那么局部覆盖长度就是固定的raw(i+1)-raw(i)。我们将长度累加，就可以得到这一条线上被覆盖的总长度。
由此我们得到了长度和宽度，相乘便可以得到局部面积。我们将由此计算来的所有局部面积累加，就得到了最终的面积。
如下是朴素方法的代码实现，其复杂度在O（N2）
#include<iostream> #include<map> #include<algorithm> using namespace std; const int MAXN=150; int n,cnt; double x[MAXN*2],y[MAXN*2]; int c[MAXN*2]; map<double,int> val; struct Line{ double x1,y1,y2; int p; }Lines[MAXN*2]; bool Ruler(const Line &a,const Line &b){ return a.x1<b.x1; } double solve(){ sort(y+1,y+1+2*n);//使用STL中函数的离散化时，必须先进行排序操作 sort(Lines+1,Lines+1+2*n,Ruler);//为了从左到右依次处理扫描线，我们需要将Lines进行排序 int y_count=unique(y+1,y+1+2*n)-y-1;//unique完成去重，并且返回去重后数组长度 for(int i=1;i<=y_count;i++){ val[y[i]]=i; //使用Map实现简单的离散化对应 } double ans=0; for(int i=1;i<=2*n;i++){ double y1=Lines[i].y1,y2=Lines[i].y2; for(int j=val[y1];j<val[y2];j++){ c[j]+=Lines[i].p; } double len=0; for(int j=1;j<y_count;j++){ if(c[j]){ len+=y[j+1]-y[j]; } } ans+=(Lines[i+1].x1-Lines[i].x1)*len; } return ans; } int main(){ while(scanf("%d",&n) && n != 0){ for(int i = 1;i <= n;i++){ scanf("%lf%lf%lf%lf",&x[i],&y[i],&x[i+n],&y[i+n]); //将一个矩形分为两条竖线，存放在lines内 Lines[i].x1=x[i]; Lines[i].y1=y[i]; Lines[i].y2=y[i+n]; Lines[i].p=1; Lines[i+n].x1=x[i+n]; Lines[i+n].y1=y[i]; Lines[i+n].y2=y[i+n]; Lines[i+n].p=-1; } double ans = solve(); printf("%.2f ",ans); } return 0; }
所以说，这和线段树有什么关系呢？
当然是没关系哒！
将扫描线的覆盖次数统计c[i]、覆盖长度y2-y1查询改成对线段树的区间修改、区间查询操作。
那么就可以将计算扫描线的覆盖长度所付出的代价由O(N)降低为O(logN)
Starts in Your Window/窗口的星星 POJ2482/P1502
耗时一夜…补档于8.14 凌晨2:13…
这里我只写了一遍LuoGu的，我没仔细看，好像两题差不多。如果有差距，下文是LuoGu版本的解法。
首先抛出算法标签，这是一道扫描线的题。首先这道题，可以抽象成我们在拿一个矩形框架框星星，而每个数据的框架大小是固定的。
由于框架大小的固定，我们可以用任何一个顶点来代表这个矩形。我们假定是右上角这格点。这也就是说，对于每一个星星，能框柱它的矩形的右上角会有一个范围。那么对于每个星星的不同范围，产生重叠的区域会同时框住。也就是说，在所有带权的点中，我们需要找到一个权值和最大的重叠区域。
那么问题就向扫描线抽象了。我们只需要界定这个每个区域的边界，也就是矩形的左右两边界。我们可以依然沿用四元组的思维来表示扫描线。
即四元组 (x,y1,y2,id) 其中，x表示横坐标，y1表示矩形下边高，y2表示矩形上边高，id来判断他是左边界还是右边界。
这里由于题目忽略了边框，所以我们对于每个矩形的左下角看做（x,y），右上角看做(x+w-1,y+h-1)，就可以处理掉边框问题。
那么还是使用Map+sort+unique的离散化（我认为比较简洁，是否高效我不做保证），沿用上文经典扫描线的思路进行处理。
这题绝对接受不了O(N2)，所以我们要引入线段树进行处理。
我们关于Y坐标建立一个线段树，维护区间最大值。初始均为0。我们依次处理每个扫描线，让其进行区间修改，并时刻更新最大值。扫描结束时，得到的最大值就是我们需要的答案。
完成一组测试样例后，切记要进行数据清零，否则会影响后续测试。（我测试了一下，不清零是40分哟）
以下完整代码
#include<iostream> #include<cstdio> #include<algorithm> #include<map> #include<cstring> using namespace std; const int Maxn=10010; int T; int n,w,h; map< double , int > Val; struct node{ double x,y1,y2; int Id; node(){} node(double x1,double a1,double a2,int iid){ x=x1;y1=a1;y2=a2;Id=iid; } }Lines[2002000]; int lazy[4004000]; int Maxer[4004000]; int count_y; int y[2002000];//离散过后的y bool Ruler(const node &a,const node &b){ if(a.x==b.x){ return a.Id>b.Id; } return a.x<b.x; } void Down(int p,int l,int r){ if(lazy[p]==0){ return ; } Maxer[p]+=lazy[p]; if(l!=r){ lazy[p<<1]+=lazy[p]; lazy[p<<1|1]+=lazy[p]; } lazy[p]=0; } void Change(int p,int l,int r,int x,int y,int z){ if(x<=l&&y>=r){ lazy[p]+=z; return; } int mid=(l+r)>>1; if(x<=mid){ Change(p<<1,l,mid,x,y,z); } if(y>mid){ Change(p<<1|1,mid+1,r,x,y,z); } Down(p<<1,l,mid); Down(p<<1|1,mid+1,r); Maxer[p]=max(Maxer[p<<1],Maxer[p<<1|1]); } int slove(){ int res=0; sort(y+1,y+1+n*2); sort(Lines+1,Lines+1+n*2,Ruler); count_y=unique(y+1,y+1+2*n)-y-1; for(int i=1;i<=count_y;i++){ Val[y[i]]=i; } //完成离散化 //Build(1,1,count_y); for(int i=1;i<=2*n;i++){ int l=Val[Lines[i].y1]; int r=Val[Lines[i].y2]; Change(1,1,count_y,l,r,Lines[i].Id); res=max(res,Maxer[1]); } return res; } void clean(){ memset(Maxer,0,sizeof(Maxer)); memset(lazy,0,sizeof(lazy)); } int main(){ scanf("%d",&T); while(T--){ scanf("%d%d%d",&n,&w,&h); for(int i=1;i<=n;i++){ int xi,yi,li; scanf("%d%d%d",&xi,&yi,&li); Lines[i]=node(xi,yi,yi+h-1,li);//可以容纳此星星的矩形范围的左边界 Lines[i+n]=node(xi+w-1,yi,yi+h-1,-li);//右边界 y[i]=yi; y[i+n]=yi+h-1; } int ans=slove(); printf("%d ",ans); clean(); } }
A simple Problem with Integers POJ3468
经典解法被我当例题开了。详见上文区间修改讲解。
但是。他还有可以利用的价值。
线段树变形—动态开点
众所周知，当水平恒定在某一个阶段的时候，空间和时间就可以进行相互转换，达到某种平衡就可以AC！我们称其为AC秘法
为了降低空间复杂度，我们可以去尝试不构造出整棵树结构，而是只在建立之初留下一个根节点，代表整个区间。当需要访问线段树的某个子树即某个子区间的时候，再建立这个子区间的节点。这和lazy标记有异曲同工之妙，他们都是有用时再做的优化思想。采用这种方法的线段树，它抛弃了父子2倍编号规则，改为使用变量记录左右子节点的编号。同时，他不保存每个节点代表的区间，而是在每次递归访问的时候作为参数传递。
对于这种变形知识点，我们就直接上演示代码，以获得更直观的理解。
#include<iostream> using namespace std; struct SegmentTree{ int lc,rc;//左右子节点的编号 int dat;//区间最大值 }tr[SIZE*2]; int root,tot; int build(){ tot++; tr[tot].lc=tr[tot].rc=tr[tot].dat=0; return tot; } void instert(int p,int l,int r,int val,int delta){ if(l==r){ tr[p].dat+=delta; return ; } int mid=(l+r)>>1; if(val<=mid){ if(!tr[p].lc){ tr[p].lc=build();//动态开点 } insert(tr[p].lc,l,mid,val,delta); } else{ if(!tr[p].rc){ tr[p].rc=build(); } insert(tr[p].rc,mid+1,r,val,delta); } tr[p].dat=max(tr[tr[p].lc].dat,tr[tr[p].rc].dat); } int main(){ tot=0; root=build(); insert(root,1,n,val,delta);//调用 }
借教室 NOIP2012提高组Day2真题
----7.18补档
啊，丢死人了。昨天写了一天的线段树，被来打算顺手改好AC这个题做完美谢幕，结果愣是找了一个晚自习的Bug没改出来。
今天仔细看了看，发觉到了一些问题。
最主要的就是，在建树的时候！不！要！忘！记！把！标！记！赋！值！成！0！
其次就是要搞清楚所求范围和节点范围，因为都是r l，所以是相当容易混乱。
我自己试了一下，下面的代码在LuoGu上跑起来确实会有一个点TLE，但这个代码为了可读性（我觉得是），少做了很多优化。比如说把“/2”的操作更改成位运算，加个快读等等。这都能大幅提高速度，所以理论上来说是不会被卡点的。
#include<iostream> #include<cstdio> using namespace std; const long long MAXN=1000010; long long n,m; long long R[MAXN]; long long d[MAXN],s[MAXN],t[MAXN]; struct S{ long long l,r; long long dat; long long lazy; }T[4900010]; void build(long long p,long long l,long long r){ //cout<<p<<" "<<l<<" "<<r<<endl; T[p].l=l; T[p].r=r; T[p].lazy=0; if(l==r){ T[p].dat=R[l]; return; } long long mid=(l+r)/2; //cout<<mid<<endl; build(p*2,l,mid); build(p*2+1,mid+1,r); T[p].dat=min(T[p*2].dat,T[p*2+1].dat); } void spread(long long x){ if(T[x].lazy!=0){ //T[x*2].dat-=T[x].lazy*(T[x*2].r-T[x*2].l+1); // T[x*2+1].dat-=T[x].lazy*(T[x*2+1].r-T[x*2+1].l+1); T[x*2].dat-=T[x].lazy; T[x*2+1].dat-=T[x].lazy; T[x*2].lazy+=T[x].lazy; T[x*2+1].lazy+=T[x].lazy; T[x].lazy=0; } } long long ask(long long p,long long l,long long r){ if(l<=T[p].l&&r>=T[p].r){ //spread(p); return T[p].dat; } spread(p); long long mid=(T[p].l+T[p].r)/2; long long val=1<<30; if(l<=mid){ val=min(val,ask(p*2,l,r)); } if(r>mid){ val=min(val,ask(p*2+1,l,r)); } // for(long long i=1;i<=n;i++){ // cout<<T[i].dat<<" "; // } // cout<<endl; return val; } //ask 1 l r void change(long long p,long long l,long long r,long long d){ if(l<=T[p].l&&r>=T[p].r){ //T[p].dat-=d*(T[p].r-T[p].l+1);//更新该节点 //spread(p); T[p].dat-=d; T[p].lazy+=d;//打上延迟标记 return ; } spread(p);//传播延迟标记 long long mid=(T[p].l+T[p].r)/2; if(l<=mid){ change(p*2,l,r,d); } if(r>mid){ change(p*2+1,l,r,d); } T[p].dat=min(T[p*2].dat,T[p*2+1].dat); } //change 1 x, v int main(){ //freopen("classroom.in","r",stdin); //freopen("classroom.out","w",stdout); scanf("%d%d",&n,&m); //cin>>n>>m; //cout<<n<<m<<endl; for(long long i=1;i<=n;i++){ scanf("%d",&R[i]); //cin>>R[i]; } for(long long i=1;i<=m;i++){ //cin>>d[i]>>s[i]>>t[i]; scanf("%d%d%d",&d[i],&s[i],&t[i]); } //感觉上，线段树会很好用 //维护一个区间最小值。如果在这个区间中最小值小于询问时的所需量，则返回订单编号并输出-1 build(1,1,n); for(long long i=1;i<=m;i++){ //cout<<abc<<endl; if(ask(1,s[i],t[i])<d[i]){ //printf("-1 "); //printf("%d",i); //puts(-1); printf("%d %d",-1,i); //cout<<-1<<endl<<i; //cout<<-1<<endl<<i; return 0; } else{ change(1,s[i],t[i],d[i]); } } printf("%d",0); //cout<<0; return 0; }
代码是考场写的代码修改得来的，考试的时候没写区间修改，复杂度太高所以死的很惨。现在加上这个区间修改，至少在自己学校的OJ上是AC了的。
疯狂的馒头
Input 第一行四个正整数N，M，p，q Output 一共输出N行，第i行表示第i个馒头的最终颜色（如果最终颜色是白色就输出0）。 Sample Input 4 3 2 4 Sample Output 2 2 3 0
这个题其实也可以用个线段树。十分有趣，要稍微做点变形。把染色的步骤倒过来。这样，只要这个节点已经有颜色了，那么他就不能再次被染色。
#include<iostream> #include<cstdio> using namespace std; const int MAXN=1e7+10; int n,m,p,q; int Left; int Right; struct chui{ int l; int r; int color; }Tree[MAXN*4]; void Build(int p,int l,int r,int colo,int L,int R){ if(Tree[p].color){ return; } //Tree[p].l=l; //Tree[p].r=r; if(l==r){ Tree[p].color=colo; //ans[l]=Tree[p].color; return; } int mid=(l+r)/2; if(L<=mid){ Build(p*2,l,mid,colo,L,R); } if(R>mid){ Build(p*2+1,mid+1,r,colo,L,R); } Tree[p].color=Tree[p*2].color&&Tree[p*2+1].color; } void Print(int p,int l,int r){ if(l==r){ printf("%d ",Tree[p].color); //cout<<Tree[p].color<<endl; return; } int mid=(l+r)/2; Print(p*2,l,mid); Print(p*2+1,mid+1,r); } int main(){ cin>>n>>m>>p>>q; for(int i=m;i>=1;i--){ Left=(1ll*i*p+q)%n+1; Right=(1ll*i*q+p)%n+1; if(Left>Right){ swap(Left,Right); } Build(1,1,n,i,Left,Right); } Print(1,1,n); }
小白逛公园 P4513
这题比较容易看出来是个区间和的最大值问题。一个区间的最大值会如何产生呢？
1.从区间左端点l开始，向右得到
2.从区间又端点r开始，向左得到
3.跨过中间点Mid，从左半边的右端点向左，从右半边的左端点向右得到。
那么，我们就需要维护四个数据：
从左开始得到的最大子段和值
从右开始得到的最大子段和值
整个区间的最大子段和值
整个区间段和
这么一寻思，满足向上传递的性质，自然就会想到线段树来维护这个操作。那么如何来维护这几个个数据呢？
void Update(int p) { int left=p<<1; int right=p<<1|1; Tree[p].sum=Tree[left].sum+Tree[right].sum; Tree[p].lmax=max(Tree[left].lmax,Tree[left].sum+Tree[right].lmax); Tree[p].rmax=max(Tree[right].rmax,Tree[right].sum+Tree[left].rmax); Tree[p].Max=max(max(Tree[left].Max,Tree[right].Max),Tree[left].rmax+Tree[right].lmax); }
因为用不着什么下放，故不需要搞Lazy标记
那么完整AC代码：
#include<iostream> #include<cstdio> using namespace std; const int MAXN=500010; int n,m; int Read_in[MAXN]; struct node { int sum; int lmax; int rmax; int Max; int l; int r; } Tree[MAXN*4]; void Update(int p) { int left=p<<1; int right=p<<1|1; Tree[p].sum=Tree[left].sum+Tree[right].sum; Tree[p].lmax=max(Tree[left].lmax,Tree[left].sum+Tree[right].lmax); Tree[p].rmax=max(Tree[right].rmax,Tree[right].sum+Tree[left].rmax); Tree[p].Max=max(max(Tree[left].Max,Tree[right].Max),Tree[left].rmax+Tree[right].lmax); } void Build(int P,int l,int r) { Tree[P].l=l; Tree[P].r=r; if(l==r) { Tree[P].lmax=Tree[P].rmax=Tree[P].Max=Tree[P].sum=Read_in[l]; return ; } int mid=(l+r)>>1; Build(P<<1,l,mid); Build(P<<1|1,mid+1,r); Update(P); } void change(int p,int pos,int num) { if(Tree[p].l==Tree[p].r) { Tree[p].sum=Tree[p].lmax=Tree[p].rmax=Tree[p].Max=num; return ; } int mid=(Tree[p].l+Tree[p].r)>>1; if(mid>=pos) { change(p<<1,pos,num); } else { change(p<<1|1,pos,num); } Update(p); } node Ask(int p,int l,int r) { if(l<=Tree[p].l&&Tree[p].r<=r) { return Tree[p]; } int mid=(Tree[p].l+Tree[p].r)>>1; if(r<=mid) { return Ask(p<<1,l,r); } else if(l>mid) { return Ask(p<<1|1,l,r); } else { node x=Ask(p<<1,l,r); node y=Ask(p<<1|1,l,r); node re; re.sum=x.sum+y.sum; re.lmax=max(x.sum+y.lmax,x.lmax); re.rmax=max(y.sum+x.rmax,y.rmax); re.Max=max(max(x.Max,y.Max),x.rmax+y.lmax); return re; } } int main() { scanf("%d%d",&n,&m); for(int i=1; i<=n; i++) { scanf("%d",&Read_in[i]); } Build(1,1,n); int Index,a,b; node ans; for(int i=1; i<=m; i++) { scanf("%d",&Index); if(Index==1) { scanf("%d%d",&a,&b); if(a>b) { swap(a,b); } ans=Ask(1,a,b); printf("%d ",ans.Max); } else { scanf("%d%d",&a,&b); change(1,a,b); } } }