线段树学习记录

网上看到了线段树的b站的学习路线

然后给了一个题单

大概有：

1. 基础知识(线段树和树状数组的模板，支持四种操作)
2. 逆序对问题
3. 扫描线问题
4. 特殊修改问题

学了一段时间线段树还是学习方法有问题，没有及时对学到的内容整理复习，还好间隔的时间不是特别的长，慢慢把丢下的东西捡起来吧。

今天晚上完成，特修6道题目的整理。

[GSS4 - Can you answer these queries IV](SP2713 GSS4 - Can you answer these queries IV - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))

$longlong$范围内区间开方，区间求和。势能线段树板子题

观察到$1e^{18}$只需要开$6$次方就可以变成$1$ ,对于一个区间，如果区间的最大值为 $1 $ 那么明显是不需要开方的，因为开方求和与和的开方是不同的，所以没办法维护懒标记，只能将区间修改变成单点暴力修改，如果某个区间的最大值$>1$ 那么就递归进入这个区间修改，否则不修改。

得到的trick :

while(scanf("%d,&n")!=EOF)与while(~scanf("%d",&n))是等价的
但是如果写成
while(scanf("%d",&n),n!=EOF)，这是错误的！（对于本题来说），
当然
while(scanf("%d",&n),n)，也是错误的！（对于本题来说） 这样写会ＲＥ

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;

int n;
ll a[N];
struct Node
{
	int l,r;//修改几次，维护一个区间最大值，如果最大值是1的话那么就不用modify了 
	ll sum=0,maxn=-1e18; 
	#define ls p<<1
	#define rs p<<1|1
}t[N*4];

void pushup(int p){	
	t[p].sum=t[ls].sum+t[rs].sum;
	t[p].maxn=max(t[ls].maxn,t[rs].maxn);
}

void build(int p,int l,int r){
	t[p].l=l,t[p].r=r;
	if(l==r){
		t[p].sum=t[p].maxn=a[l];
		return ;
	}
	int mid=l+r>>1;
	build(ls,l,mid);
	build(rs,mid+1,r);
	pushup(p);
}

// 区间最大值＞１的暴力修改，否则不修改
void modify(int p,int tl,int tr)//暴力变成单点修改 
{
	if(t[p].l==t[p].r){／／单点修改
		t[p].sum=sqrt(t[p].sum);
		t[p].maxn=t[p].sum;
		return ;	
	}
	int mid=t[p].l+t[p].r>>1;
	if(tl<=mid&&t[p].maxn>1){／／带限制条件的暴力修改
		modify(ls,tl,tr);
	}
	if(tr>mid&&t[p].maxn>1){
		modify(rs,tl,tr);
	}
	pushup(p);
}

ll query(int p,int tl,int tr)／／不带ｐｕｓｈｄｏｗｎ的普通ｑｕｅｒｙ
{
	if(t[p].l>=tl&&t[p].r<=tr){
		return t[p].sum;
	}
	int mid=t[p].l+t[p].r>>1;
	ll res=0;
	if(tl<=mid){
		res=query(ls,tl,tr);
	}
	if(tr>mid){
		res+=query(rs,tl,tr);
	}
	return res;
}

int main()
{
	int t=1;
	while(scanf("%d",&n)!=EOF){
		for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
		build(1,1,n);
		cout<<"Case #"<<t++<<":"<<endl;
		int q;
		cin>>q;
		while(q--){
			int l,r,k;
			scanf("%d%d%d",&k,&l,&r);
			if(l>r)swap(l,r);
			if(k==0){
				modify(1,l,r);
			}
			else{
				printf("%lld\n",query(1,l,r));
			}
		}
		cout<<endl;
	}
	return 0;
}