势能线段树

目录

简单介绍

 题目

1. 上帝造题的七分钟 2 

2.SUM and REPLACE

3. And RMQ

总结 

简单介绍

 题目

1. 上帝造题的七分钟 2 

链接：https://www.luogu.com.cn/problem/P4145

 维护两种操作

1.区间开根号(下取整)

2.区间和询问

显然无法通过懒标记来计算区间开根号后的值，其由叶子结点本身的值决定。容易发现当一个数连续进行开根号操作会在很少的次数变为1，且值不再改变，1即为零势能点。因此我们可以维护区间max。一旦区间修改时发现此区间的max<=1时，我们不需要再次修改，直接return即可，否则向下递归修改。

Code:

#include<bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
#define endl "\n"
#define int long long
const int N=1e5+10;
struct segment_tree {int a[N];struct node {int l,r;int mx,sum;}tr[N<<2];void build(int u,int l,int r) {tr[u].l=l,tr[u].r=r;if(l==r) {tr[u].mx=tr[u].sum=a[l];return ;}int mid=(l+r)>>1;build(u<<1,l,mid);build(u<<1|1,mid+1,r);pushup(u);} void modify(int u,int l,int r) {if(tr[u].mx<=1) return ;if(tr[u].l==tr[u].r) {tr[u].mx=sqrt(tr[u].mx);tr[u].sum=tr[u].mx;return ;}int mid=(tr[u].l+tr[u].r)>>1;if(l<=mid) modify(u<<1,l,r);if(r>mid) modify(u<<1|1,l,r);pushup(u);} int query(int u,int l,int r) {if(tr[u].l>=l&&tr[u].r<=r) {return tr[u].sum;}int mid=(tr[u].l+tr[u].r)>>1;int res=0;if(l<=mid) res+=query(u<<1,l,r);if(r>mid) res+=query(u<<1|1,l,r);return res;}void pushup(int u) {tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;tr[u].mx=max(tr[u<<1].mx,tr[u<<1|1].mx);}
}ST;
signed main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int n,m;cin>>n;for(int i=1;i<=n;i++) cin>>ST.a[i];ST.build(1,1,n);cin>>m;while(m--) {int op,l,r;cin>>op>>l>>r;if(l>r) swap(l,r);if(op==0) ST.modify(1,l,r);else cout<<ST.query(1,l,r)<<endl;     }
}

2.SUM and REPLACE

链接：https://codeforces.com/contest/920/problem/F

定义f(x)为x因子的数量

维护三种操作

1.区间修改x=f(x)  

2.区间和查询

手动模拟f(x)可以发现，进行f(x)操作，数值单调不增，且x<=2时，其值不在改变，因此同上题一样维护区间最大值即可。f(x)可以O(nlogn)时间预处理出来。

#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define PII pair<int,int>
#define endl "\n"
#define int long long
const int N=3e5+10,M=1e6+10;
int d[M+1];
struct segment_tree {int a[N];struct node {int l,r;int mx,sum;}tr[N<<2];void build(int u,int l,int r) {tr[u].l=l,tr[u].r=r;if(l==r) {tr[u].mx=tr[u].sum=a[l];return ;}int mid=(l+r)>>1;build(u<<1,l,mid);build(u<<1|1,mid+1,r);pushup(u);} void modify(int u,int l,int r) {if(tr[u].mx<=2) return ;if(tr[u].l==tr[u].r) {tr[u].mx=d[tr[u].mx];tr[u].sum=tr[u].mx;return ;}int mid=(tr[u].l+tr[u].r)>>1;if(l<=mid) modify(u<<1,l,r);if(r>mid) modify(u<<1|1,l,r);pushup(u);} int query(int u,int l,int r) {if(tr[u].l>=l&&tr[u].r<=r) {return tr[u].sum;}int mid=(tr[u].l+tr[u].r)>>1;int res=0;if(l<=mid) res+=query(u<<1,l,r);if(r>mid) res+=query(u<<1|1,l,r);return res;}void pushup(int u) {tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;tr[u].mx=max(tr[u<<1].mx,tr[u<<1|1].mx);}
};
signed main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);for(int i=1;i<=M;i++) {  //预处理for(int j=i;j<=M;j+=i) {d[j]++;}}int n,m;cin>>n>>m;segment_tree ST;for(int i=1;i<=n;i++) cin>>ST.a[i];ST.build(1,1,n);while(m--) {int op,l,r;cin>>op>>l>>r;if(op==1) ST.modify(1,l,r);else cout<<ST.query(1,l,r)<<endl;}
}

3. And RMQ

链接：

维护三个操作

1.区间按位与x

2.区间最大值

3.单点修改

这题零势能点藏得较深，我们考虑将x二进制展开，发现在x的二进制位为零的位置，区间所有数的二进制位也为零，则操作可以忽略。维护区间或     

当 orsum & x =orsum,则直接return 

Code:

#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define PII pair<int,int>
#define endl "\n"
const int N=4e5+10;
struct segment_tree {int a[N];struct node {int l,r;int mx,sum;}tr[N<<2];void build(int u,int l,int r) {tr[u].l=l,tr[u].r=r;if(l==r) {tr[u].mx=tr[u].sum=a[l];return ;}int mid=(l+r)>>1;build(u<<1,l,mid);build(u<<1|1,mid+1,r);pushup(u);} void modify(int u,int l,int r,int x) {if((tr[u].sum&x)==tr[u].sum) return ;if(tr[u].l==tr[u].r) {tr[u].mx=tr[u].mx&x;tr[u].sum=tr[u].mx;return ;}int mid=(tr[u].l+tr[u].r)>>1;if(l<=mid) modify(u<<1,l,r,x);if(r>mid) modify(u<<1|1,l,r,x);pushup(u);} int query(int u,int l,int r) {if(tr[u].l>=l&&tr[u].r<=r) {return tr[u].mx;}int mid=(tr[u].l+tr[u].r)>>1;int res=0;if(l<=mid) res=max(res,query(u<<1,l,r));if(r>mid) res=max(res,query(u<<1|1,l,r));return res;}void update(int u,int k,int x) {if(tr[u].l==tr[u].r) {tr[u].mx=tr[u].sum=x;return ;}int mid=(tr[u].l+tr[u].r)>>1;if(k<=mid) update(u<<1,k,x);else update(u<<1|1,k,x);pushup(u);}void pushup(int u) {tr[u].sum=tr[u<<1].sum|tr[u<<1|1].sum;tr[u].mx=max(tr[u<<1].mx,tr[u<<1|1].mx);}
}ST;
int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int n,m;cin>>n>>m;for(int i=1;i<=n;i++) cin>>ST.a[i];ST.build(1,1,n);while(m--) {int l,r,x;string op;cin>>op;if(op=="AND")  {cin>>l>>r>>x;ST.modify(1,l,r,x);}else if(op=="UPD") {cin>>l>>x;ST.update(1,l,x);}else {cin>>l>>r;cout<<ST.query(1,l,r)<<endl;}}
}

总结 

1.对于区间修改操作，修改操作会使得值在趋向零势能点前严格单调减少，在变为零势能点后不在变化。需要维护一个值来界定是否到达零势能

2.且题目不能出现其他非单调的区间修改操作，如区间加，区间乘等。如果有其他修改操作，可以通过构造形如 update1 ,update 2,update 1,update 2 的数据破坏单调性，从而使操作1复杂度变为暴力修改的O(nlogn)