免费网站建设有哪些,极限优化主题wordpress,展示图片的网站模板,小型旅游网站建设方案势能线段树
线段树能够通过打懒标记实现区间修改的条件有两个#xff1a;
能够快速处理懒标记对区间询问结果的影响能够快速实现懒标记的合并
但有的区间修改不满足上面两个条件#xff08;如区间整除/开方/取模等#xff09;。 但某些修改存在一些奇妙的性质#xff0c…势能线段树
线段树能够通过打懒标记实现区间修改的条件有两个
能够快速处理懒标记对区间询问结果的影响能够快速实现懒标记的合并
但有的区间修改不满足上面两个条件如区间整除/开方/取模等。 但某些修改存在一些奇妙的性质使得序列每个元素被修改的次数有一个上限。
所以可以在线段树每个节点上记录一个值表示对应区间内是否每个元素都达到修改次数上限。区间修改时暴力递归到叶子节点如果途中遇到一个节点这个节点的对应区间内每个元素都达到修改次数上限则在这个节点returnreturnreturn掉。
可以证明复杂度为 O((nmlogn)×lim)O((nm\log n)\times lim)O((nmlogn)×lim)其中nnn为序列长度mmm为询问次数limlimlim为修改次数上限。
LOJ6029——线段树区间除法
对于每个区间维护区间内的 最大值MaxMaxMax 和 最小值MinMinMin对于整除操作如果有Max−⌊Maxd⌋Min−⌊Mind⌋Max-\lfloor\frac{Max}{d}\rfloor Min − \lfloor\frac{Min}{d}\rfloorMax−⌊dMax⌋Min−⌊dMin⌋就转化为区间减。否则直接向下递归。
考虑何时满足Max−⌊Maxd⌋Min−⌊Mind⌋Max-\lfloor\frac{Max}{d}\rfloor Min − \lfloor\frac{Min}{d}\rfloorMax−⌊dMax⌋Min−⌊dMin⌋ 设Maxk1dc1,Mink2dc2(c1,c2∈[0,d−1],d≥2)Maxk_1dc_1,Mink_2dc_2(c_1,c_2\in[0,d-1],d\geq 2)Maxk1dc1,Mink2dc2(c1,c2∈[0,d−1],d≥2) Max−⌊Maxd⌋Min−⌊Mind⌋Max-\lfloor\frac{Max}{d}\rfloorMin-\lfloor\frac{Min}{d}\rfloorMax−⌊dMax⌋Min−⌊dMin⌋ Max−Min⌊Maxd⌋−⌊Mind⌋Max-Min\lfloor\frac{Max}{d}\rfloor-\lfloor\frac{Min}{d}\rfloorMax−Min⌊dMax⌋−⌊dMin⌋ (k1−k2)dc1−c2k1−k2(k_1-k_2)dc_1-c_2k_1-k_2(k1−k2)dc1−c2k1−k2 (k1−k2)(d−1)c2−c1(k_1-k_2)(d-1)c_2-c_1(k1−k2)(d−1)c2−c1 若k1k2,则c2c1,所以MaxMin若k_1k_2,则c_2c_1,所以MaxMin若k1k2,则c2c1,所以MaxMin 若k1k2,则(k1−k2)(d−1)≥d−1,又因为c2−c1≤d−1,所以当且仅当Maxk1d,Min(k1−1)dd−1时成立若k_1k_2,则(k_1-k_2)(d-1)\geq d-1,又因为c_2-c_1\leq d-1,所以当且仅当Maxk_1d,Min(k_1-1)dd-1时成立若k1k2,则(k1−k2)(d−1)≥d−1,又因为c2−c1≤d−1,所以当且仅当Maxk1d,Min(k1−1)dd−1时成立
所以一个区间最多暴力向下递归log2(Max−Min)\log_2(Max-Min)log2(Max−Min)次。记势能函数ϕ(T)\phi(T)ϕ(T)为线段树TTT每一个节点log(Max−Min)\log(Max−Min)log(Max−Min)的和每一次修改操作会影响O(logn)O(\log n)O(logn)个节点的Max−MinMax-MinMax−Min值让ϕ(T)\phi(T)ϕ(T)增加lognlogA\log n\log AlognlogA其中AAA为值域。因此总时间复杂度为O(nlogAmlognlogA)O(n\log Am\log n\log A)O(nlogAmlognlogA)。
UOJ228——线段树区间开根
同上对于每个区间维护区间内的 最大值MaxMaxMax 和 最小值MinMinMin对于开根操作如果有Max−⌊Max⌋Min−⌊Min⌋Max-\lfloor\sqrt{Max}\rfloor Min − \lfloor\sqrt{Min}\rfloorMax−⌊Max⌋Min−⌊Min⌋就转化为区间减。否则直接向下递归。
考虑何时满足Max−⌊Max⌋Min−⌊Min⌋Max-\lfloor\sqrt{Max}\rfloor Min − \lfloor\sqrt{Min}\rfloorMax−⌊Max⌋Min−⌊Min⌋ 设Maxk12c1,Mink22c2(c1∈[0,2k1];c2∈[0,2k2];k1,k2≥1)Maxk_1^2c_1,Mink_2^2c_2(c_1\in[0,2k_1];c_2\in[0,2k_2];k_1,k_2\geq 1)Maxk12c1,Mink22c2(c1∈[0,2k1];c2∈[0,2k2];k1,k2≥1) Max−⌊Max⌋Min−⌊Min⌋Max-\lfloor\sqrt{Max}\rfloor Min − \lfloor\sqrt{Min}\rfloorMax−⌊Max⌋Min−⌊Min⌋ k12c1−k1k22c2−k2k_1^2c_1-k_1k_2^2c_2-k_2k12c1−k1k22c2−k2 k12−k22−(k1−k2)c2−c1k_1^2-k_2^2-(k_1-k_2)c_2-c_1k12−k22−(k1−k2)c2−c1 (k1k2−1)(k1−k2)c2−c1(k_1k_2-1)(k_1-k_2)c_2-c_1(k1k2−1)(k1−k2)c2−c1 若k1k2,则c2c1,所以MaxMin若k_1k_2,则c_2c_1,所以MaxMin若k1k2,则c2c1,所以MaxMin 若k1k2,则(k1k2−1)(k1−k2)≥k1k2−1≥2k2,又因为c2−c1≤2k2,所以当且仅当Maxk12,Min(k1−1)22(k1−1)k12−1时成立若k_1k_2,则(k_1k_2-1)(k_1-k_2)\geq k_1k_2-1\geq 2k_2,又因为c_2-c_1\leq 2k_2,所以当且仅当Maxk_1^2,Min(k_1-1)^22(k_1-1)k_1^2-1时成立若k1k2,则(k1k2−1)(k1−k2)≥k1k2−1≥2k2,又因为c2−c1≤2k2,所以当且仅当Maxk12,Min(k1−1)22(k1−1)k12−1时成立
开根后区间极差由Max−MinMax-MinMax−Min变为Max−Min\sqrt{Max}-\sqrt{Min}Max−Min又由Max−MinMax−MinMaxMinMax−Min\frac{Max-Min}{\sqrt{Max}-\sqrt{Min}}\sqrt{Max}\sqrt{Min}\sqrt{Max}-\sqrt{Min}Max−MinMax−MinMaxMinMax−Min知Max−MinMax−Min\sqrt{Max-Min}\sqrt{Max}-\sqrt{Min}Max−MinMax−Min。
所以一个区间最多暴力向下递归 loglog(Max−Min)\log\log(Max−Min)loglog(Max−Min) 次总时间复杂度为O(nloglogAmlognloglogA)O(n\log\log Am\log n\log\log A)O(nloglogAmlognloglogA)其中AAA为值域。
#includeiostream
#includecstdio
#includecstring
#includecmath
using namespace std;
typedef long long ll;
const int inf1e97;
const int N1e510;
ll mx[N2],mn[N2],sum[N2],tag[N2],a[N];
int n,q;
ll Sqr(ll x){return sqrt(x);
}
void build(int u,int l,int r){tag[u]0;if(lr){mx[u]mn[u]sum[u]a[l];return;}int mid(lr)1;build(u1,l,mid);build(u1|1,mid1,r);mx[u]max(mx[u1],mx[u1|1]);mn[u]min(mn[u1],mn[u1|1]);sum[u]sum[u1]sum[u1|1];
}
void pushdown(int u,int l,int r){if(tag[u]!0){int mid(lr)1;mx[u1]tag[u];mn[u1]tag[u];sum[u1]tag[u]*(mid-l1);tag[u1]tag[u];mx[u1|1]tag[u];mn[u1|1]tag[u];sum[u1|1]tag[u]*(r-mid);tag[u1|1]tag[u];tag[u]0;}
}
void add(int u,int l,int r,int a,int b,ll x){if(alrb){mx[u]x;mn[u]x;sum[u]x*(r-l1);tag[u]x;return;}pushdown(u,l,r);int mid(lr)1;if(amid) add(u1,l,mid,a,b,x);if(bmid) add(u1|1,mid1,r,a,b,x);mx[u]max(mx[u1],mx[u1|1]);mn[u]min(mn[u1],mn[u1|1]);sum[u]sum[u1]sum[u1|1];
}
void sqr(int u,int l,int r,int a,int b){if(alrbmx[u]-Sqr(mx[u])mn[u]-Sqr(mn[u])){ll xmx[u]-Sqr(mx[u]);mx[u]-x;mn[u]-x;sum[u]-x*(r-l1);tag[u]-x;return;}pushdown(u,l,r);int mid(lr)1;if(amid) sqr(u1,l,mid,a,b);if(bmid) sqr(u1|1,mid1,r,a,b);mx[u]max(mx[u1],mx[u1|1]);mn[u]min(mn[u1],mn[u1|1]);sum[u]sum[u1]sum[u1|1];
}
ll Sum(int u,int l,int r,int a,int b){if(alrb) return sum[u];pushdown(u,l,r);int mid(lr)1;ll res0;if(amid) resresSum(u1,l,mid,a,b);if(bmid) resresSum(u1|1,mid1,r,a,b);return res;
}
int main(){scanf(%d%d,n,q);for(int i1;in;i) scanf(%lld,a[i]);build(1,1,n);int opt,l,r;ll x;while(q--){scanf(%d%d%d,opt,l,r);if(opt1){scanf(%lld,x);add(1,1,n,l,r,x);}else if(opt2){sqr(1,1,n,l,r);}else if(opt3){printf(%lld\n,Sum(1,1,n,l,r));}}return 0;
} CF438D——线段树区间取模
对于每个区间维护区间内的 最大值MaxMaxMax对于整除操作如果有MaxmodMaxmodMaxmod就直接忽略。否则暴力向下递归。 可以证明对于一个数xxx最多取模logx\log xlogx次就会令其变为1
若modx2mod\frac{x}{2}mod2x那么x%modx−modx2x\%modx−mod\frac{x}{2}x%modx−mod2x若modx2mod\frac{x}{2}mod2x那么x%mod0x\%mod0x%mod0若modx2mod\frac{x}{2}mod2x那么x%modmodx2x\%modmod\frac{x}{2}x%modmod2x
总时间复杂度为(nlogAmlognlogA)(n\log Am\log n\log A)(nlogAmlognlogA)其中AAA为值域。
CF920F——线段树区间取约数个数
设D(x)D(x)D(x)表示xxx的约数个数。 发现D(x)D(x)D(x)有以下性质
若x≤2x\leq 2x≤2D(x)xD(x)xD(x)xD(x)≤2xD(x)\leq 2\sqrt{x}D(x)≤2x
那么一个数xxx的修改次数上限为loglogx\log\log xloglogx。 套用上面的方法即可。
