习题都来自董老师的博客和b站:
其实这道题的思路肯定是用线段树,但是为了计算结果线段树需要维护哪些信息?
//mx表示区间内的最大斜率,sum表示区间内可见的,主要就是递归求出sum
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<vector> #include<algorithm> #include<cstdlib> #define ls u<<1 #define rs u<<1|1 #define mid ((l+r)>>1) using namespace std; const int maxn=1e5+10; const int INF=0x3f3f3f3f; //其实这道题的思路肯定是用线段树,但是为了计算结果线段树需要维护哪些信息? //mx表示区间内的最大斜率,sum表示区间内可见的,主要就是递归求出sum double mx[maxn<<2]; int summ[maxn<<2]; int dfs(int u,int l,int r,double mls){//求右分支sum if(mx[u]<=mls) return 0; //剪枝 if(l==r) return mx[u]>mls; if(mx[ls]<=mls) return dfs(rs,mid+1,r,mls); else return dfs(ls,l,mid,mls)+summ[u]-summ[ls]; } void pushup(int u,int l,int r){ //上传标记 这个过程中要递归更新值 mx[u]=max(mx[ls],mx[rs]); summ[u]=summ[ls]+dfs(rs,mid+1,r,mx[ls]); //需要查询 } void change(int u,int l,int r,int x,double v){ //点修改 if(l==r) { mx[u]=v;summ[u]=1;return; } if(x<=mid) change(ls,l,mid,x,v); else change(rs,mid+1,r,x,v); pushup(u,l,r); } int main(){ int n,m; cin>>n>>m; for(int i=1;i<=m;i++){ int x,y;cin>>x>>y; change(1,1,n,x,(double)y/x); cout<<summ[1]<<endl; } return 0; }
//暴力区间修改,主要是修改的方式不好合并或者打标记
//优化:每个区间维护一个最大值mx,只要mx=1就不用向下分裂了
//每个叶子节点最多修改6次 从12次方到1
//所以综复杂度是6NlogN
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<vector> #include<algorithm> #include<cstdlib> #define LL long long #define ls u<<1 #define rs u<<1|1 #define mid ((l+r)>>1) using namespace std; const int maxn=1e5+10; const int INF=0x3f3f3f3f; //暴力区间修改,主要是修改的方式不好合并或者打标记 //优化:每个区间维护一个最大值mx,只要mx=1就不用向下分裂了 //每个叶子节点最多修改6次 从12次方到1 //所以综复杂度是6NlogN LL a[maxn]; LL mx[maxn<<2],summ[maxn<<2]; void pushup(int u){ summ[u]=summ[ls]+summ[rs]; mx[u]=max(mx[ls],mx[rs]); } void build(int u,int l,int r){ //建树 summ[u]=mx[u]=a[l]; if(l==r) return; build(ls,l,mid); build(rs,mid+1,r); pushup(u); } void change(int u,int l,int r,int x,int y){ //区间修改 if(mx[u]==1) return; //剪枝 if(l==r){ summ[u]=sqrt(summ[u]); mx[u]=sqrt(mx[u]); return; } if(x<=mid) change(ls,l,mid,x,y); if(y>mid) change(rs,mid+1,r,x,y); pushup(u); } LL query(int u,int l,int r,int x,int y){ //区间查询 if(x<=l&&r<=y) return summ[u]; LL s=0; if(x<=mid) s+=query(ls,l,mid,x,y); if(y>mid) s+=query(rs,mid+1,r,x,y); return s; } int main(){ int n,m,opt,l,r; cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; build(1,1,n); cin>>m; while(m--){ cin>>opt>>l>>r; if(l>r) swap(l,r); if(opt==0){ change(1,1,n,l,r); } else cout<<query(1,1,n,l,r)<<endl; } return 0; }
//差分数组可以将点查询--->区间查询 区间修改--->点修改
//把原数组弄成差分数组,方便加上等差数列
//设差分数列为a,等差数列的首项为s,末项为e,公差为d
//区间[l,r]加上等差数量,等于al+s, al+1~ar +d ar+1-e
//!!对原始序列的点查询--转化为对差分序列的区间查询(前缀和)
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<vector> #include<algorithm> #include<cstdlib> #define LL long long #define ls u<<1 #define rs u<<1|1 #define mid ((l+r)>>1) using namespace std; const int maxn=1e5+10; const int INF=0x3f3f3f3f; //差分数组可以将点查询--->区间查询 区间修改--->点修改 //把原数组弄成差分数组,方便加上等差数列 //设差分数列为a,等差数列的首项为s,末项为e,公差为d //区间[l,r]加上等差数量,等于al+s, al+1~ar +d ar+1-e //!!对原始序列的点查询--转化为对差分序列的区间查询(前缀和) int a[maxn]; LL summ[maxn<<2],tag[maxn<<2]; //懒标记 void pushup(int u){ //上传 summ[u]=summ[ls]+summ[rs]; } void pushdown(int u,int l,int r){ //下传 summ[ls]+=tag[u]*(mid-l+1); summ[rs]+=tag[u]*(r-mid); //懒标记下传 tag[ls]+=tag[u]; tag[rs]+=tag[u]; tag[u]=0; } void build(int u,int l,int r){ summ[u]=a[l]; tag[u]=0; if(l==r) return; build(ls,l,mid); build(rs,mid+1,r); pushup(u); } void change(int u,int l,int r,int x,int y,LL v){ if(x<=l&&r<=y){ summ[u]+=(r-l+1)*v; tag[u]+=v; return; } pushdown(u,l,r); //先下传 if(x<=mid) change(ls,l,mid,x,y,v); if(y>mid) change(rs,mid+1,r,x,y,v); pushup(u); } LL query(int u,int l,int r,int x,int y){ if(x<=l&&r<=y) return summ[u]; pushdown(u,l,r); LL s=0; if(x<=mid) s+=query(ls,l,mid,x,y); if(y>mid) s+=query(rs,mid+1,r,x,y); return s; } int main(){ int n,m,op,l,r,k,d,p; cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=n;i>1;i--) a[i]-=a[i-1]; //倒着修改 build(1,1,n) ;//用差分数组建树 for(int i=1;i<=m;i++){ cin>>op; if(op==1){ cin>>l>>r>>k>>d; change(1,1,n,l,l,k); //首项修改 if(l+1<=r) change(1,1,n,l+1,r,d) ;//注意要判断范围 if(r<n) change(1,1,n,r+1,r+1,-(k+d*(r-l))); } else { cin>>p; cout<<query(1,1,n,1,p)<<endl; } } return 0; }
//这个和花神那个是一样的,左右括号法
//前缀和思想:把区间查询转化为前缀和之差
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<vector> #include<algorithm> #include<cstdlib> #define LL long long #define ls u<<1 #define rs u<<1|1 #define mid ((l+r)>>1) using namespace std; const int maxn=1e5+10; const int INF=0x3f3f3f3f; //这个和花神那个是一样的,左右括号法 //前缀和思想:把区间查询转化为前缀和之差 int n,m; struct node{ int l,r; int sum[2]; }tr[maxn<<2]; //sum[0]:区间起点数, sum[1]:区间终点数 void pushup(int u,int k){ tr[u].sum[k]=tr[ls].sum[k]+tr[rs].sum[k]; //对应的相加 } void build(int u,int l,int r){ tr[u]={l,r,0,0}; if(l==r) return ; build(ls,l,mid); build(rs,mid+1,r); } void change(int u,int x,int k){ if(tr[u].l==tr[u].r){ tr[u].sum[k]++; return; } if(x<=tr[ls].r) change(ls,x,k); else change(rs,x,k); pushup(u,k); } int query(int u,int x,int y,int k){ if(x>tr[u].r||y<tr[u].l) return 0; if(x<=tr[u].l&&tr[u].r<=y) return tr[u].sum[k]; return query(ls,x,y,k)+query(rs,x,y,k); } int main(){ cin>>n>>m; build(1,1,n); for(int i=1;i<=m;i++){ int q,l,r; cin>>q>>l>>r; if(q==1) change(1,l,0),change(1,r,1); else cout<<query(1,1,r,0)-query(1,1,l-1,1)<<endl; //到r的终点数-到l的起点数 } return 0; }