哈尔滨网站建设索q.479185700,网站次页,网站结构建设方案,打开网站后直接做跳转页面学过数据结构和会做题完全是两个概念orz 各种各样的题目都应该见识一下 简单的目录#xff1a; 最大连续长度 吉司机线段树 线段树合并/分裂 最大连续长度问题 典型题目#xff1a;HDU 3911 #xff08;$Black$ $And$ $White$#xff09; 题目大意#xff1a;有一个长度为…学过数据结构和会做题完全是两个概念orz 各种各样的题目都应该见识一下 简单的目录 最大连续长度 吉司机线段树 线段树合并/分裂 最大连续长度问题 典型题目HDU 3911 $Black$ $And$ $White$ 题目大意有一个长度为$n$$1\le n\le 10^5$的$01$序列$a_i$现在有$m$个操作将区间$[l_i,r_i]$反转$01$互换或询问区间$[l_i,r_i]$中$1$最多连续出现多少次 区间的反转很显然可以用懒标记解决细节就不再赘述了比如打完标记向上更新啥的一开始我就忘了orz 难办的是区间内的最大连续长度原因在于两段小区间如何合并成一个大区间并不容易想到 先考虑最大连续长度可能的来源 仅在左半区间仅在右半区间横跨两个小区间 我们可以多记录一东西除了当前区间内的最大连续长度再记录当前区间内从最左端、最右端开始的最大连续长度 这样如果我们想把两个小区间合并得到的连续长度相当于是左半区间从右端开始的最大长度右半区间从左端开始的最大长度 这两个新加的记录值也是容易合并的求最左端开始的最大连续长度如果左半区间全是相同数字那么可以与右半区间的最左端合并否则就是左半区间的最大连续长度求最右端开始的亦是如此 所以本题的启示是加入一些新的记录值来帮助计算 #include cstdio
#include cmath
#include cstring
#include cstdlib
using namespace std;inline int max(int a,int b)
{return (ab?a:b);
}
inline int min(int a,int b)
{return (ab?a:b);
}
inline void swap(int a,int b)
{int tmpa;ab,btmp;
}const int MAX100005;int n,m;
int c[MAX1];int sz;
int left[MAX2][2],right[MAX2][2],mid[MAX2][2];
int tag[MAX2];inline void Calc(int k,int a,int b)
{int len(b-a1)1;for(int i0;i2;i){left[k][i]left[k1][i](left[k1][i]len?left[(k1)1][i]:0);right[k][i]right[(k1)1][i](right[(k1)1][i]len?right[k1][i]:0);mid[k][i]max(mid[k1][i],mid[(k1)1][i]);//#1mid[k][i]max(mid[k][i],right[k1][i]left[(k1)1][i]);}
}inline void Build(int k,int a,int b)
{if(ab){left[k][c[a]]right[k][c[a]]mid[k][c[a]]1;return;}Build(k1,a,(ab)1);Build((k1)1,((ab)1)1,b);Calc(k,a,b);
}inline void Update(int k,int a,int b)
{if(!tag[k])return;swap(left[k][0],left[k][1]);swap(right[k][0],right[k][1]);swap(mid[k][0],mid[k][1]);tag[k]0;if(a!b){tag[k1]^1;tag[(k1)1]^1;}
}inline void Modify(int k,int l,int r,int a,int b)
{Update(k,a,b);if(ar || bl)return;if(al br){tag[k]^1;Update(k,a,b);return;}Modify(k1,l,r,a,(ab)1);Modify((k1)1,l,r,((ab)1)1,b);Calc(k,a,b);
}inline int Query(int k,int l,int r,int a,int b)
{Update(k,a,b);if(ar || bl)return 0;if(al br)return mid[k][1];int half(ab)1;if(rhalf)return Query(k1,l,r,a,half);if(lhalf)return Query((k1)1,l,r,half1,b);int midvmax(Query(k1,l,r,a,half),Query((k1)1,l,r,half1,b));midvmax(midv,min(right[k1][1],half-l1)min(left[(k1)1][1],r-half));return midv;
}int main()
{
// freopen(input.txt,r,stdin);while(~scanf(%d,n)){memset(left,0,sizeof(left));memset(right,0,sizeof(right));memset(mid,0,sizeof(mid));memset(tag,0,sizeof(tag));memset(c,0,sizeof(c));for(int i1;in;i)scanf(%d,c[i]);sz1;while(szn)sz1;Build(1,1,sz);scanf(%d,m);while(m--){int op,x,y;scanf(%d%d%d,op,x,y);if(op1)Modify(1,x,y,1,sz);elseprintf(%d\n,Query(1,x,y,1,sz));}}return 0;
} View Code 吉司机线段树 这种做法有一种明显的标志有一种操作是用$min(a_i,w)$来取代$a_i$ 经典模板题HDU 5306$Gorgeous$ $Sequence$ 感谢这篇题解https://www.cnblogs.com/shenben/p/6641984.html 做法的精髓是不仅记录 当前节点表示的区间中 的最大值$x$和区间和$sum$不然只是普通的线段树了同时记录区间中最大值的出现次数$cnt$和严格次大值$y$ 现在我们考虑如何处理题目中的$0$修改 首先通过递归定位到某个严格包含在区间中的线段$t_k$然后根据具体情况分为三种处理方式 $t[k].x\le w$即区间内的最大值也小于$w$那么区间内的所有元素都不会改变直接退出即可$t[k].ywt_k.x$即区间内仅有最大值大于$w$那么区间内的$t[k].cnt$个最大值都需要变成$w$同时对$t[k].sum$做出更新$t[k].sum-t[k].cnt\times (t[k].x-w)$注意强制转换成long long$t[k].y\le w$即区间内有超过一种值大于等于$w$如果$t[k].yw$归于第2类那么$t[k].cnt$不会更新无法直接更新需要向下继续递归结束后再重新计算来更新同时我们发现所有的更新仅限于第$2$类其并没有进行到底所以每个节点的$t[k].x$都有类似懒标记的作用在修改与查询的过程中应当将这个懒标记向下更新 这个做法的复杂度没找到推导...虽然有人说$O(NlogN)$但还是觉得$O(N(logN)^2)$更靠谱点 #include cstdio
#include cstring
#include cmath
#include algorithm
using namespace std;typedef long long ll;
const int MAX1000005;struct Node
{int x,y,cnt;ll sum;Node(int a0,int b0,int c-1,ll d0LL){xa,yb,cntc,sumd;}
};int n,m;
int val[MAX1];
Node t[MAX2];inline void Update(int k)
{int leftk1,rightleft1;t[k].sumt[left].sumt[right].sum;if(t[left].xt[right].x){t[k].xt[left].x;t[k].ymax(t[left].y,t[right].y);t[k].cntt[left].cntt[right].cnt;}else{if(t[left].xt[right].x)swap(left,right);t[k].xt[left].x;t[k].ymax(t[left].y,t[right].x);t[k].cntt[left].cnt;}
}inline void Build(int k,int a,int b)
{if(ab){t[k]Node(val[a],-1,1,val[a]);return;}Build(k1,a,(ab)1);Build((k1)1,((ab)1)1,b);Update(k);
}inline void Dec(int k,int x)
{if(t[k].xx)return;t[k].sum-(ll)t[k].cnt*(t[k].x-x);t[k].xx;
}inline void Pushdown(int k)
{Dec(k1,t[k].x);Dec(k1|1,t[k].x);
}inline void Modify(int k,int l,int r,int a,int b,int w)
{if(ar || bl)return;if(al br)//***{if(t[k].xw)return;if(t[k].yw)//***{Dec(k,w);return;}}Pushdown(k);Modify(k1,l,r,a,(ab)1,w);Modify(k1|1,l,r,((ab)1)1,b,w);Update(k);
}inline int Max(int k,int l,int r,int a,int b)
{if(ar || bl)return 0;if(al br)return t[k].x;Pushdown(k);return max(Max(k1,l,r,a,(ab)1),Max(k1|1,l,r,((ab)1)1,b));
}inline ll Sum(int k,int l,int r,int a,int b)
{if(ar || bl)return 0;if(al br)return t[k].sum;Pushdown(k);return Sum(k1,l,r,a,(ab)1)Sum(k1|1,l,r,((ab)1)1,b);
}int main()
{
// freopen(input.txt,r,stdin);int T;scanf(%d,T);while(T--){scanf(%d%d,n,m);for(int i1;in;i)scanf(%d,val[i]);int sz1;while(szn)sz1;Build(1,1,sz);while(m--){int op,x,y,w;scanf(%d%d%d,op,x,y);if(op0){scanf(%d,w);Modify(1,x,y,1,sz,w);}if(op1)printf(%d\n,Max(1,x,y,1,sz));if(op2)printf(%lld\n,Sum(1,x,y,1,sz));}for(int i1;in;i)val[i]0;for(int i1;iszn;i)t[i]Node();}return 0;
} View Code 一道更加综合的题BZOJ 4695 最假女选手 这道题目就是上一题的加强版了不仅有区间取$min$还有区间加区间取$max$ 所以我们不仅要保存区间和、最大值、次大值、最大值出现次数还要保存最小值、次小值、最小值出现次数、区间加的懒标记貌似最后一个可以不用有时间研究一下... 虽然大家保存的节点结构都差不多但后面的标记传递还是有点差距的我的写法虽然常数巨大但是竟然能省略很多细节 首先考虑区间加操作$1$ 跟普通的线段树区间加是一样的操作先定位然后给$tag$加上这个数并改变$sum$每次将要访问下层节点的时候将$tag$向下传递 但是这道题中tag的存在感比普通的区间加中的要强很多因为对于每个线段树节点最值、次最值都是相对值真实的值需要加上这个节点的$tag$这个在操作$2$、$3$出现 然后是区间取$min$操作$3$ -跟上一题一样讲起来方便 先递归到严格区间内然后分三步操作比较的时候记得加上$tag$ 但是这里存在比上一题麻烦的地方修改区间最大、次大值的同时我们还有可能改变区间的最小、次小值 别的大佬们在这里就直接讨论了但我写的时候没有想那么多怀疑常数出现在这里 我们先考虑一下在什么时候才会从操作$3$的递归进入对单点的修改 这下最小、次小值改变的条件就清晰一些了 如果存在次小值且最大值等于次小值次小值改变最小值不变如果不存在次小值即区间内全是最大值此时最小值也是最大值那么最小值改变次小值仍不存在否则即次小值存在且小于最大值最小值、次小值都不改变区间取$max$操作$2$是这个的镜像操作别写岔就行了 要记得将$tag$、小值、大值向下传递与前一题差不多并在递归后更新节点我写的巨丑也是大常数的来源...有必要再学习一下别人的代码 这题跑了$46000MS$快反向登顶了哎... #include cstdio
#include cstring
#include cmath
#include ctime
#include algorithm
using namespace std;typedef long long ll;
const int MAX500005;
const int INF130;struct Node
{ll sum;int tag,len;int fst[2],sec[2],cnt[2];Node(){fst[0]sec[0]-INF;fst[1]sec[1]INF;cnt[0]cnt[1]sumtaglen0;}Node(int x){fst[0]fst[1]x;sec[0]-INF,sec[1]INF;cnt[0]cnt[1]len1;sumx,tag0;}
};int n,m,sz1;
int val[MAX1];
Node t[MAX2];inline void Update(int k)
{Node lt[k1],rt[k1|1];t[k].suml.sumr.sum;for(int i0;i2;i){ l.fst[i]l.fst[i]l.tag-t[k].tag;l.sec[i]l.sec[i]l.tag-t[k].tag;r.fst[i]r.fst[i]r.tag-t[k].tag;r.sec[i]r.sec[i]r.tag-t[k].tag;if(l.fst[i]r.fst[i]){t[k].fst[i]l.fst[i];if(i0)t[k].sec[i]max(l.sec[i],r.sec[i]);elset[k].sec[i]min(l.sec[i],r.sec[i]);t[k].cnt[i]l.cnt[i]r.cnt[i];}else{if(i0 l.fst[i]r.fst[i])swap(l,r);if(i1 l.fst[i]r.fst[i])swap(l,r);t[k].fst[i]l.fst[i];if(i0)t[k].sec[i]max(l.sec[i],r.fst[i]);elset[k].sec[i]min(l.sec[i],r.fst[i]);t[k].cnt[i]l.cnt[i];}}
}inline void Build(int k,int r,int a,int b)
{if(ar)return;if(ab){t[k]Node(val[a]);return;}Build(k1,r,a,(ab)1);Build(k1|1,r,((ab)1)1,b);Update(k);t[k].lent[k1].lent[k1|1].len;
}inline void DecMax(int k,ll w)
{w-t[k].tag;if(t[k].fst[0]w)return;t[k].sum-(ll)t[k].cnt[0]*(t[k].fst[0]-w);if(t[k].fst[0]t[k].sec[1])t[k].sec[1]w;if(t[k].fst[0]t[k].fst[1])t[k].fst[1]w;t[k].fst[0]w;
}inline void DecMin(int k,ll w)
{w-t[k].tag;if(t[k].fst[1]w)return;t[k].sum-(ll)t[k].cnt[1]*(t[k].fst[1]-w);if(t[k].fst[1]t[k].sec[0])t[k].sec[0]w;if(t[k].fst[1]t[k].fst[0])t[k].fst[0]w;t[k].fst[1]w;
}inline void DecTag(int k)
{if(t[k].tag0)return;for(int i0;i2;i){t[k].fst[i]t[k].tag;t[k].sec[i]t[k].tag;}if(ksz){t[k1].tagt[k].tag;t[k1].sum(ll)t[k].tag*t[k1].len;t[k1|1].tagt[k].tag;t[k1|1].sum(ll)t[k].tag*t[k1|1].len;}t[k].tag0;
}inline void Down(int k)
{DecTag(k);DecMax(k1,t[k].fst[0]);DecMin(k1,t[k].fst[1]);DecMax(k1|1,t[k].fst[0]);DecMin(k1|1,t[k].fst[1]);
}inline void Add(int k,int l,int r,int a,int b,int w)
{if(ar || bl)return;if(al br){t[k].tagw;t[k].sum(ll)t[k].len*w;return;}Down(k);Add(k1,l,r,a,(ab)1,w);Add(k1|1,l,r,((ab)1)1,b,w);Update(k);
}inline void ModifyMax(int k,int l,int r,int a,int b,int w)
{if(ar || bl)return;if(al br){if(t[k].fst[1]t[k].tagw)return;if(t[k].sec[1]t[k].tagw){DecMin(k,w);return;}}Down(k);ModifyMax(k1,l,r,a,(ab)1,w);ModifyMax(k1|1,l,r,((ab)1)1,b,w);Update(k);
}inline void ModifyMin(int k,int l,int r,int a,int b,int w)
{if(ar || bl)return;if(al br){if(t[k].fst[0]t[k].tagw)return;if(t[k].sec[0]t[k].tagw){DecMax(k,w);return;}}Down(k);ModifyMin(k1,l,r,a,(ab)1,w);ModifyMin(k1|1,l,r,((ab)1)1,b,w);Update(k);
}inline ll QuerySum(int k,int l,int r,int a,int b)
{if(ar || bl)return 0LL;if(al br)return t[k].sum;Down(k);return QuerySum(k1,l,r,a,(ab)1)QuerySum(k1|1,l,r,((ab)1)1,b);
}inline int QueryMax(int k,int l,int r,int a,int b)
{if(ar || bl)return -INF;if(al br)return t[k].fst[0]t[k].tag;Down(k);return max(QueryMax(k1,l,r,a,(ab)1),QueryMax(k1|1,l,r,((ab)1)1,b));
}inline int QueryMin(int k,int l,int r,int a,int b)
{if(ar || bl)return INF;if(al br)return t[k].fst[1]t[k].tag;Down(k);return min(QueryMin(k1,l,r,a,(ab)1),QueryMin(k1|1,l,r,((ab)1)1,b));
}int main()
{
// freopen(input.txt,r,stdin);
// freopen(my.txt,w,stdout); scanf(%d,n);for(int i1;in;i)scanf(%d,val[i]);while(szn)sz1;Build(1,n,1,sz);scanf(%d,m);while(m--){int op,x,y,w;scanf(%d%d%d,op,x,y);if(op4)scanf(%d,w);if(op1)Add(1,x,y,1,sz,w);if(op2)ModifyMax(1,x,y,1,sz,w);if(op3)ModifyMin(1,x,y,1,sz,w);if(op4)printf(%lld\n,QuerySum(1,x,y,1,sz));if(op5)printf(%d\n,QueryMax(1,x,y,1,sz));if(op6)printf(%d\n,QueryMin(1,x,y,1,sz));}return 0;
} View Code 线段树合并 这个一开始学起来真的有点困难...稍微有点抽象 在我的感觉中是处理有关元素的有序性的问题的 例如将两个区间$[1,8]$的统计元素出现次数的线段树合并 我们先想想如何实现 为了防止空间爆炸我们写的线段树必然是动态开点的那么便有一大优势可以类似可持久化线段树一样通过将新节点的儿子指向已经存在的某节点来重复利用 在这个基础上考虑将两棵线段树对于一个区间的两个节点$x$、$y$合并成一个新节点 若$x$、$y$都为空则合并后也为空若$x$、$y$其中一个为空那么可以直接指向不为空的节点因为与空树合并原本的结构不变若$x$、$y$都不为空那么分为左、右儿子继续向下递归最后在将左右的统计值相加其实还是有很多细节的最好学习写法比较好的代码比如后面引用到的 这样下来复杂度是怎么样的呢 首先一般情况如果一颗数值区间为$[1,n]$的线段树是由$n$条链依次合并成的那么就跟可持久化线段树一样是$O(NlogN)$的时间复杂度 但是总有特例吧比如下图两棵线段树在叶节点互补意会一下 这样的一次合并是$O(N)$的 但是不要着急如果想构成这样的情形首先这两个树应当分别构造且如果想让单次合并的消耗尽量大在叶节点处应当同样互补 这样总的算下来时间复杂度是$O(N2\times \frac{N}{2}4\times \frac{N}{4}...)O(NlogN)$可以放心食用 由于合并大多伴随着开点所以空间复杂度也是$O(NlogN)$应当注意不要MLE 说了这么多具体代码怎么实现比较好又有什么用呢 且看这道题目BZOJ 2212 $POI2011$$Tree Rotations$ 我完全看的是这篇题解胡小兔神奇的操作——线段树合并例题: BZOJ2212 具体题目分析和代码实现都无可挑剔我就不做无用功了 但是仅仅做出这一道题离熟练掌握还差距很大 再来一道题目BZOJ 4552 $TJoi2016$ $HEoi2016$排序 准备学习一下这份代码fjzzq2002线段树合并与分裂 这道题目更加综合一些不仅要求线段树的合并还有分裂 其实在掌握合并的基础上分裂也是容易处理的 加入我们想在以$root$为根的线段树上将第$p$个元素包含第$p$个分裂成一颗新树就可以类似主席树上找第$k$大的递归处理 对于当前节点$x$$t_x$表示节点$x$覆盖的区间共有多少元素 若$t_{l_i}\le p$那么第$p$个元素一定在$x$的左儿子中将$r_x$直接割给新树若$t_{l_i}p$那么第$p$个元素一定在$x$的右儿子中若已经到达底端则此时$x$就是以$root$为根的线段树中第$p$个元素将$x$割给新树在这里我的实现是将$t_x$清零将新树中对于节点$t_{cur}$赋成$1$然后可以删去一些分裂中被割走的节点如果对于当前节点$x$$t_{l_x}0$即左子树为空那么令$l_x0$以免之后的合并访问到这个没必要经过的节点对于$r_x$同理 在这题中除去了线段树的合并与分裂总体应该是$O(NlogN)$但是具体不会证我们还需要一种数据结构告诉我们应该合并哪些线段树 一开始的想法是用一颗区间赋值线段树给合并后的每一段打上懒标记但是如果想要从一段合并区间到另一段感觉上需要在树上累加应该是$O(logN)$的跳转细节还很多 zzq给出的思路是用set排序的依据是区间的左端点 这样一来我们对每次排序的$[op,x,y]$操作能够直接二分$O(logN)$的找出左右端点所在的合并区间然后再通过$iterator$遍历将线段树合并 不过我对set十分陌生一开始将s.lower_bound(x)写成lower_bound(s.begin(),s.end(),x)应该是不能这样用的 他是setint我写的是setpairint,int 细节还非常的繁琐...应当学习一下他的处理方法 除去set的部分我的代码还是能看的 #include cstdio
#include cstring
#include cmath
#include cstdlib
#include algorithm
#include set
using namespace std;typedef pairint,int pii;
const int MAX100005;
const int LOG100;int tot;
int l[MAX*LOG],r[MAX*LOG],t[MAX*LOG],rev[MAX*LOG];inline int Build(int x,int a,int b)
{int curtot;t[cur]1;if(ab)return cur;int mid(ab)1;if(xmid)l[cur]Build(x,a,mid);elser[cur]Build(x,mid1,b);return cur;
}inline int Merge(int x,int y,int a,int b)
{if(!x || !y)return xy;int curtot,mid(ab)1;l[cur]Merge(l[x],l[y],a,mid);r[cur]Merge(r[x],r[y],mid1,b);t[cur]t[l[cur]]t[r[cur]];return cur;
}inline void Update(int x)
{if(!t[l[x]])l[x]0;if(!t[r[x]])r[x]0;
}inline int Split(int x,int a,int b,int p)
{int curtot,mid(ab)1;if(ab){t[cur]t[x];t[x]0;return cur;}if(t[l[x]]p){l[cur]Split(l[x],a,mid,p);r[cur]r[x];r[x]0;}elser[cur]Split(r[x],mid1,b,p-t[l[x]]);Update(x);Update(cur);t[x]t[l[x]]t[r[x]];t[cur]t[l[cur]]t[r[cur]];return cur;
}inline int Locate(int x,int a,int b,int p)
{if(ab)return a;int mid(ab)1;if(t[l[x]]p)return Locate(l[x],a,mid,p);elsereturn Locate(r[x],mid1,b,p-t[l[x]]);
}int n,m,sz1;
int val[MAX];
setpii s;int main()
{
// freopen(input.txt,r,stdin);
// freopen(output.txt,w,stdout);scanf(%d%d,n,m);while(szn)sz1;for(int i1;in;i){scanf(%d,val[i]);s.insert(pii(i,Build(val[i],1,sz)));}for(int i1;im;i){int op,x,y;scanf(%d%d%d,op,x,y);setpii::iterator begs.lower_bound(pii(x,0));if((*beg).firstx || begs.end())beg--;setpii::iterator ends.lower_bound(pii(y,0));if((*end).firsty || ends.end())end--;int idx1(*beg).second,left1(*beg).first,idx2(*end).second,left2(*end).first;if(idx1idx2){s.erase(beg);int p1x-left11,p2y-left12;int rp1t[idx1]-(x-left1)1,rp2t[idx1]-(y-left1);int left,right,mid;if(!rev[idx1]){leftidx1,midSplit(idx1,1,sz,p1),rightSplit(mid,1,sz,p2-p11);if(t[left])s.insert(pii(left1,left));if(t[right])s.insert(pii(y1,right));s.insert(pii(x,mid));}else{leftidx1,midSplit(idx1,1,sz,rp2),rightSplit(mid,1,sz,rp1-rp21);if(t[left])s.insert(pii(y1,left));if(t[right])s.insert(pii(left1,right));rev[left]rev[right]1;s.insert(pii(x,mid));}rev[mid]op;continue;}int num1left1t[idx1]-x,num2y-left21;int p1t[idx1]-num11,p2num21;int rp1num11,rp2t[idx2]-num21;int begn,endn,rem1,rem2,newn;if(!rev[idx1])begnSplit(idx1,1,sz,p1),rem1idx1;elsebegnidx1,rem1Split(idx1,1,sz,rp1),rev[rem1]1;//if(!rev[idx2])endnidx2,rem2Split(idx2,1,sz,p2);elseendnSplit(idx2,1,sz,rp2),rem2idx2,rev[rem2]1;//newnMerge(begn,endn,1,sz);setpii::iterator itbeg;it;while(it!end)newnMerge(newn,(*it).second,1,sz),it;s.erase(beg,end);s.erase(end);if(t[rem1])s.insert(pii(left1,rem1));if(t[rem2])s.insert(pii(y1,rem2));s.insert(pii(x,newn));rev[newn]op;}int q;scanf(%d,q);setpii::iterator its.lower_bound(pii(q,0));if((*it).firstq || its.end())//it--;int x(*it).second,left(*it).first;int p(rev[x]?t[x]-(q-left):q-left1);printf(%d\n,Locate(x,1,sz,p));return 0;
} View Code 这题还有一种玩法是$O(N(logN)^2)$的二分线段树区间修改网上大部分都是这样的题解也是一种有趣的思路吧 #include cstdio
#include cstring
#include cmath
using namespace std;const int MAX100005;int n,m,q;
int val[MAX],op[MAX],ql[MAX],qr[MAX];
int c[MAX];int sz1;
int t[MAX2],len[MAX2],tag[MAX2];inline void Build(int k,int l,int r)
{if(lr){if(ln){t[k]c[l];len[k]1;}return;}int mid(lr)1;Build(k1,l,mid);Build(k1|1,mid1,r);t[k]t[k1]t[k1|1];len[k]len[k1]len[k1|1];
}inline void Update(int x)
{if(!tag[x])return;t[x1](tag[x]0?len[x1]:0);tag[x1]tag[x];t[x1|1](tag[x]0?len[x1|1]:0);tag[x1|1]tag[x];tag[x]0;
}inline int Query(int k,int l,int r,int a,int b)
{if(ar || bl)return 0;if(al br)return t[k];Update(k);int mid(ab)1;return Query(k1,l,r,a,mid)Query(k1|1,l,r,mid1,b);
}inline void Add(int k,int l,int r,int a,int b,int w)
{if(ar || bl)return;if(al br){tag[k]w;t[k](w0?len[k]:0);return;}Update(k);int mid(ab)1;Add(k1,l,r,a,mid,w);Add(k1|1,l,r,mid1,b,w);t[k]t[k1]t[k1|1];//
}int Check(int x)
{memset(tag,0,sizeof(tag));for(int i1;in;i)c[i](val[i]x);Build(1,1,sz);for(int i1;im;i){int xql[i],yqr[i],numQuery(1,x,y,1,sz);if(op[i]0){Add(1,x,xnum-1,1,sz,1);Add(1,xnum,y,1,sz,-1);}else{Add(1,x,y-num,1,sz,-1);Add(1,y-num1,y,1,sz,1);}}return Query(1,q,q,1,sz);
}int main()
{
// freopen(input.txt,r,stdin);
// freopen(output.txt,w,stdout);scanf(%d%d,n,m);while(szn)sz1;for(int i1;in;i)scanf(%d,val[i]);for(int i1;im;i)scanf(%d%d%d,op[i],ql[i],qr[i]);scanf(%d,q);int l1,rn,mid;while(lr){mid(lr)1;if(Check(mid))rmid;elselmid1;}if(!Check(l))l;printf(%d\n,l);return 0;
} View Code 待续慢慢补题转载于:https://www.cnblogs.com/LiuRunky/p/Segment_Tree.html
