线段树练习

#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;
} 

#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;
}

#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;
}