Can you answer these queries?(线段树)

发布于 2020-10-08  0 次阅读


题目大意:

Can you answer these queries?
给你一个长度为n的序列,和序列中每个元素的值,和m次操作
分别给出op,x,y
如果op=0则更新区间x~y,更新操作为对每个值取平方根向下取整
op==1则查询区间x~y的元素和

思路:

显然线段树(毕竟我是练习线段树才找的这个题),区间更新,区间查询,维护区间和
注意点比较多:
元素的范围是long long
每组数据后换行
区间均为1时特判一下,不进行后续更新
区间x不一定小于y,记得处理一下

AC Code:

#include<bits/stdc++.h>
using namespace std;
#define debug(a) cout<<#a<<"="<<a<<endl;
const int N=1e5 +9;
int n, m;
long long a[N];
int op, x, y;
struct segtree{
	long long sum;
}tr[N<<2];
inline int lc(int p) {return p<<1;}
inline int rc(int p) {return p<<1|1;}
inline void push_up(int p) {tr[p].sum=tr[lc(p)].sum + tr[rc(p)].sum;}
inline void build(int p, int l, int r){
	if(l==r)	{scanf("%lld", &tr[p].sum); return ;}
	int mid=(l+r)>>1;
	build(lc(p), l, mid);
	build(rc(p), mid+1, r);
    push_up(p);
}
inline void updata(int p, int l, int r, int x, int y){
	if(x==y){
        tr[p].sum=sqrt(tr[p].sum);
		return ;
	}
    if(l<=x && r>=y && tr[p].sum==y-x+1) return ;
	int mid=(x+y)>>1;
	if(l<=mid) updata(lc(p), l, r, x, mid);
	if(r>mid) updata(rc(p), l, r, mid+1, y);
    push_up(p);
}
inline long long query(int p, int l, int r, int x, int y){
    if(l<=x && r>=y) return tr[p].sum;
    long long ans=0;
    int mid=(x+y)>>1;
    if(l<=mid)  ans+=query(lc(p), l, r, x, mid);
    if(r>mid)   ans+=query(rc(p), l, r, mid+1, y);
    return ans;
}
signed main(){
    int k=0;
    while(scanf("%d", &n)!=EOF){
        build(1,1,n);
        scanf("%d", &m);
        printf("Case #%d:\n", ++k);
        while(m--){
            scanf("%d%d%d", &op, &x, &y);
            if(x>y) swap(x,y);
            if(op) printf("%lld\n", query(1,x,y,1,n));
            else   updata(1,x,y,1,n);
        }
        printf("\n");
    }
	return 0;
}

平平无奇的大学在读本科生