怎么用html建网站,国内平面设计公司,移动端网站和app开发,台州市城乡建设局网站目录 简单介绍 题目
1. 上帝造题的七分钟 2
2.SUM and REPLACE
3. And RMQ
总结 简单介绍 题目
1. 上帝造题的七分钟 2
链接#xff1a;https://www.luogu.com.cn/problem/P4145 维护两种操作 1.区间开根号(下取整) 2.区间和询问 显然无法通过懒标记来计算区间开根号…目录 简单介绍 题目
1. 上帝造题的七分钟 2
2.SUM and REPLACE
3. And RMQ
总结 简单介绍 题目
1. 上帝造题的七分钟 2
链接https://www.luogu.com.cn/problem/P4145 维护两种操作 1.区间开根号(下取整) 2.区间和询问 显然无法通过懒标记来计算区间开根号后的值其由叶子结点本身的值决定。容易发现当一个数连续进行开根号操作会在很少的次数变为1且值不再改变1即为零势能点。因此我们可以维护区间max。一旦区间修改时发现此区间的max1时我们不需要再次修改直接return即可否则向下递归修改。
Code: #includebits/stdc.h
using namespace std;
#define PII pairint,int
#define endl \n
#define int long long
const int N1e510;
struct segment_tree {int a[N];struct node {int l,r;int mx,sum;}tr[N2];void build(int u,int l,int r) {tr[u].ll,tr[u].rr;if(lr) {tr[u].mxtr[u].suma[l];return ;}int mid(lr)1;build(u1,l,mid);build(u1|1,mid1,r);pushup(u);} void modify(int u,int l,int r) {if(tr[u].mx1) return ;if(tr[u].ltr[u].r) {tr[u].mxsqrt(tr[u].mx);tr[u].sumtr[u].mx;return ;}int mid(tr[u].ltr[u].r)1;if(lmid) modify(u1,l,r);if(rmid) modify(u1|1,l,r);pushup(u);} int query(int u,int l,int r) {if(tr[u].lltr[u].rr) {return tr[u].sum;}int mid(tr[u].ltr[u].r)1;int res0;if(lmid) resquery(u1,l,r);if(rmid) resquery(u1|1,l,r);return res;}void pushup(int u) {tr[u].sumtr[u1].sumtr[u1|1].sum;tr[u].mxmax(tr[u1].mx,tr[u1|1].mx);}
}ST;
signed main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int n,m;cinn;for(int i1;in;i) cinST.a[i];ST.build(1,1,n);cinm;while(m--) {int op,l,r;cinoplr;if(lr) swap(l,r);if(op0) ST.modify(1,l,r);else coutST.query(1,l,r)endl; }
} 2.SUM and REPLACE
链接https://codeforces.com/contest/920/problem/F 定义f(x)为x因子的数量 维护三种操作 1.区间修改xf(x) 2.区间和查询 手动模拟f(x)可以发现进行f(x)操作数值单调不增且x2时其值不在改变因此同上题一样维护区间最大值即可。f(x)可以O(nlogn)时间预处理出来。 #includeiostream
#includecmath
#includecstring
#includealgorithm
#includecstdio
#includevector
#includequeue
#includemap
#includeset
using namespace std;
#define PII pairint,int
#define endl \n
#define int long long
const int N3e510,M1e610;
int d[M1];
struct segment_tree {int a[N];struct node {int l,r;int mx,sum;}tr[N2];void build(int u,int l,int r) {tr[u].ll,tr[u].rr;if(lr) {tr[u].mxtr[u].suma[l];return ;}int mid(lr)1;build(u1,l,mid);build(u1|1,mid1,r);pushup(u);} void modify(int u,int l,int r) {if(tr[u].mx2) return ;if(tr[u].ltr[u].r) {tr[u].mxd[tr[u].mx];tr[u].sumtr[u].mx;return ;}int mid(tr[u].ltr[u].r)1;if(lmid) modify(u1,l,r);if(rmid) modify(u1|1,l,r);pushup(u);} int query(int u,int l,int r) {if(tr[u].lltr[u].rr) {return tr[u].sum;}int mid(tr[u].ltr[u].r)1;int res0;if(lmid) resquery(u1,l,r);if(rmid) resquery(u1|1,l,r);return res;}void pushup(int u) {tr[u].sumtr[u1].sumtr[u1|1].sum;tr[u].mxmax(tr[u1].mx,tr[u1|1].mx);}
};
signed main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);for(int i1;iM;i) { //预处理for(int ji;jM;ji) {d[j];}}int n,m;cinnm;segment_tree ST;for(int i1;in;i) cinST.a[i];ST.build(1,1,n);while(m--) {int op,l,r;cinoplr;if(op1) ST.modify(1,l,r);else coutST.query(1,l,r)endl;}
} 3. And RMQ
链接 维护三个操作 1.区间按位与x 2.区间最大值 3.单点修改 这题零势能点藏得较深我们考虑将x二进制展开发现在x的二进制位为零的位置区间所有数的二进制位也为零则操作可以忽略。维护区间或
当 orsum x orsum,则直接return
Code:
#includeiostream
#includecmath
#includecstring
#includealgorithm
#includecstdio
#includevector
#includequeue
#includemap
#includeset
using namespace std;
#define PII pairint,int
#define endl \n
const int N4e510;
struct segment_tree {int a[N];struct node {int l,r;int mx,sum;}tr[N2];void build(int u,int l,int r) {tr[u].ll,tr[u].rr;if(lr) {tr[u].mxtr[u].suma[l];return ;}int mid(lr)1;build(u1,l,mid);build(u1|1,mid1,r);pushup(u);} void modify(int u,int l,int r,int x) {if((tr[u].sumx)tr[u].sum) return ;if(tr[u].ltr[u].r) {tr[u].mxtr[u].mxx;tr[u].sumtr[u].mx;return ;}int mid(tr[u].ltr[u].r)1;if(lmid) modify(u1,l,r,x);if(rmid) modify(u1|1,l,r,x);pushup(u);} int query(int u,int l,int r) {if(tr[u].lltr[u].rr) {return tr[u].mx;}int mid(tr[u].ltr[u].r)1;int res0;if(lmid) resmax(res,query(u1,l,r));if(rmid) resmax(res,query(u1|1,l,r));return res;}void update(int u,int k,int x) {if(tr[u].ltr[u].r) {tr[u].mxtr[u].sumx;return ;}int mid(tr[u].ltr[u].r)1;if(kmid) update(u1,k,x);else update(u1|1,k,x);pushup(u);}void pushup(int u) {tr[u].sumtr[u1].sum|tr[u1|1].sum;tr[u].mxmax(tr[u1].mx,tr[u1|1].mx);}
}ST;
int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int n,m;cinnm;for(int i1;in;i) cinST.a[i];ST.build(1,1,n);while(m--) {int l,r,x;string op;cinop;if(opAND) {cinlrx;ST.modify(1,l,r,x);}else if(opUPD) {cinlx;ST.update(1,l,x);}else {cinlr;coutST.query(1,l,r)endl;}}
}
总结
1.对于区间修改操作修改操作会使得值在趋向零势能点前严格单调减少在变为零势能点后不在变化。需要维护一个值来界定是否到达零势能
2.且题目不能出现其他非单调的区间修改操作如区间加区间乘等。如果有其他修改操作可以通过构造形如 update1 ,update 2,update 1,update 2 的数据破坏单调性从而使操作1复杂度变为暴力修改的O(nlogn)
