习题都来自董老师的博客和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;
}
标签：const,int,线段,练习,区间,include,mx,LL From： https://www.cnblogs.com/shirlybaby/p/17768043.html