@Junlier
2018-10-28T18:57:46.000000Z
字数 1029
阅读 2021
知识点总结
阅读体验:https://zybuluo.com/Junlier/note/1283868
校内题单(闲人免入):https://www.cnblogs.com/cjoierljl/p/9683242.html
持续更新。。。
这里不水啊,毕竟也是高二的老选手了。。。
丢个题单:
对于区间一起往什么地方连边的问题
考虑用线段树优化
因为可以把线段树中代表一段区间的点看做图中的一个节点
那么这个节点包含的区间都与他连边
让这个节点与需要连的地方连边
复杂度优化成,是连边次数,是区间长度
动态开点线段树
合并两棵线段树时
如果当前节点有一棵不存在,直接就是存在的那一个
如果当前节点两棵都存在,合并信息,递归合并左右儿子
新不新开点就是可不可持久化的问题了。。。
具体情况具体分析
把询问按照线段树的方法进行分治
第一种方法码量短那么一丢丢:不管查询区间的变化,直接往下找,常数也小
//随便kuai的一段代码
void Modify(int now,int L,int R,int le,int ri,int xx)
{
if(L==le&&R==ri){~~~;return;}
Pushdown(now);int mid=(L+R)>>1;
if(ri<=mid)Modify(ls,L,mid,le,ri,~);
if(le>mid) Modify(rs,mid+1,R,le,ri,~);
if(le<=mid&&ri>mid)Modify(ls,L,mid,le,mid,~),Modify(rs,mid+1,R,mid+1,ri,~);
Psuhup(now);
}
第二种方法码量稍长,但容易理解:全部准确判断,特定情况下会好一些
void Modify(int now,int L,int R,int le,int ri,lst xx)
{
if(L==le&&R==ri){~~~;return;}
Pushdown(now);int mid=(L+R)>>1;
if(ri<=mid)Modify(ls,L,mid,le,ri,~);
if(le>mid) Modify(rs,mid+1,R,le,ri,~);
if(le<=mid&&ri>mid)
Modify(ls,L,mid,le,mid,~),Modify(rs,mid+1,R,mid+1,ri,~);
Pushup(now);
}