题目意思
其实看懂题目 就知道是线段树了
给的问题就是区间修改加区间查询
但是这题要把区间里的所有点的值开个平方
如果维护区间和和区间平方和的话
对这个区间做第二次修改的时候就会出问题
然后想了很久都没思路
看了题解发现他用了一种很神奇的优化方法
把区间修改变成单点修改
但是如果一直单点修改的话一定是会t的
所以需要优化剪枝
因为我们是对点开平方 所以修改的次数多的话
最后点的值会变成一 所以修改的时候把全是一的区间剪掉
这样就优化好了
看了之后感觉好神奇 我反正是想不到
ac代码
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#define pi 3.1415926535898
#define ll long long
#define lson rt<<1
#define rson rt<<1|1
#define eps 1e-6
#define ms(a,b) memset(a,b,sizeof(a))
#define legal(a,b) a&b
#define print1 printf("111\n")
using namespace std;
const int maxn = 1e5+10;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1000000007;
//998244353ll a[maxn];
ll t[maxn<<2];void pushup(int rt)
{t[rt]=t[lson]+t[rson];
}void build(int rt,int l,int r)
{if(l==r){t[rt]=a[l];return;}int mid=(l+r)>>1;build(lson,l,mid);build(rson,mid+1,r);pushup(rt);
}void update(int rt,int l,int r,int L,int R)
{if(l==r){t[rt]=sqrt(t[rt]);return;}if(l>R||r<L||t[rt]==r-l+1){return;}int mid=(l+r)>>1;if(L<=mid){update(lson,l,mid,L,R);}if(R>mid){update(rson,mid+1,r,L,R);}pushup(rt);
}ll query(int rt,int l,int r,int L,int R)
{if(L<=l&&r<=R){return t[rt];}int mid=(l+r)>>1;ll res=0;if(L<=mid)res+=query(lson,l,mid,L,R);if(R>mid)res+=query(rson,mid+1,r,L,R);return res;
}int main()
{int n,ce=0;while(scanf("%d",&n)!=EOF){for(int i=1;i<=n;i++)scanf("%lld",&a[i]);build(1,1,n);printf("Case #%d:\n",++ce);int m;scanf("%d",&m);for(int i=1;i<=m;i++){int c,x,y;scanf("%d%d%d",&c,&x,&y);if(c==0){if(x>y)swap(x,y);update(1,1,n,x,y);}if(c==1){if(x>y)swap(x,y);ll ans=query(1,1,n,x,y);printf("%lld\n",ans);}}printf("\n");}}