|
试题描述
|
|
花仔喜欢步行游历各国，花仔有一条游览路线，它是线型的，也就是说，所有游历国家呈一条线的形状排列，花仔对每个国家都有一个喜欢度（当然花仔并不一定喜欢所有国家），每一次旅行中，花仔会选择一条旅游路线，它在那一串国家中是连续的一段，这次旅行带来的开心值是这些国家的喜欢度的总和，当然花仔对这些国家的喜欢程序并不是恒定的，有时会突然对某些国家产生反感，使他对这些国家的喜欢度delta变为√delta，也就是开根号。现在给出花仔每次的旅行路线，以及开心度的变化，请求出花仔每次旅行的开心值。
|
|
输入
|
|
第一行是一个整数 N，表示有 N 个国家。
第二行有 N 个空格隔开的整数，表示每个国家的初始喜欢度delta[i]。 第三行是一个整数 M，表示有 M 条信息要处理。 第四行到最后，每行3个整数 x,l,r(l≤r)，当x=1 时，询问游历国家 l 到 r 的开心值总和，也就是 ∑i=l→r delta[i]；当x=2时，修改国家 l 到 r 中每个国家的喜欢度，delta=√delta。 注：建议使用 sqrt 函数，且向下取整。 |
|
输出
|
|
每次 x=1 时，每行一个整数。表示这次旅行的开心度。
|
|
输入示例
|
|
4
1 100 5 5 5 1 1 2 2 1 2 1 1 2 2 2 3 1 1 4 |
|
输出示例
|
|
101
11 11 |
|
其他说明
|
|
对于100%的数据，n≤10^5,m≤2×10^5,0≤delta[i]＜10^9。
|
可以说是个线段树的板子了
难度是在如何维护根号上，我们可以将开根操作转换为减法
即x=x-(x-sqrt(x))
因为数据范围很大，所以我们不能一个一个修改，但是判断条件要变一下，只有在修改范围内并且与其sqrt的差相同的才能同时修改
最后一点就是要开long long，但是不能开太多，可能会T
下面给出代码：
#include<iostream> #include<algorithm> #include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<cmath> using namespace std; inline int rd(){ int x=0,f=1; char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0'; return x*f; } inline void write(long long x){ if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10+'0'); return ; } struct node{ int l,r; long long maxn,minn; long long sum; int f; }tree[400006]; int n,m; void build(int i,int x,int y){ tree[i].l=x,tree[i].r=y; if(x==y){ tree[i].maxn=rd(); tree[i].sum=tree[i].minn=tree[i].maxn; return ; } int mid=(x+y)>>1; build(i*2,x,mid); build(i*2+1,mid+1,y); tree[i].sum=tree[i*2].sum+tree[i*2+1].sum; tree[i].maxn=max(tree[i*2].maxn,tree[i*2+1].maxn); tree[i].minn=min(tree[i*2].minn,tree[i*2+1].minn); return ; } void pushdown(int x){ if(!tree[x].f) return ; int h=tree[x].f; tree[x*2].f+=h,tree[x*2+1].f+=h; tree[x*2].sum-=(tree[x*2].r-tree[x*2].l+1)*h,tree[x*2+1].sum-=(tree[x*2+1].r-tree[x*2+1].l+1)*h; tree[x*2].maxn-=h,tree[x*2+1].maxn-=h,tree[x*2].minn-=h,tree[x*2+1].minn-=h; tree[x].f=0; return ; } void extract_a_root(int i,int x,int y){ if(tree[i].l>=x&&tree[i].r<=y&&(tree[i].maxn-(long long)sqrt(tree[i].maxn))==(tree[i].minn-(long long)sqrt(tree[i].minn))){ int h=tree[i].minn-(int)sqrt(tree[i].minn); tree[i].f+=h; tree[i].sum-=((tree[i].r-tree[i].l+1)*h); tree[i].maxn-=h; tree[i].minn-=h; return ; } if(tree[i].l>y||tree[i].r<x) return ; pushdown(i); if(tree[i*2].r>=x) extract_a_root(i*2,x,y); if(tree[i*2+1].l<=y) extract_a_root(i*2+1,x,y); tree[i].sum=tree[i*2].sum+tree[i*2+1].sum; tree[i].maxn=max(tree[i*2].maxn,tree[i*2+1].maxn); tree[i].minn=min(tree[i*2].minn,tree[i*2+1].minn); return ; } long long solve(int i,int x,int y){ if(tree[i].l>=x&&tree[i].r<=y) return tree[i].sum; if(tree[i].l>y||tree[i].r<x) return 0; pushdown(i); long long num=0; if(tree[i*2].r>=x) num+=solve(i*2,x,y); if(tree[i*2+1].l<=y) num+=solve(i*2+1,x,y); return num; } int main(){ n=rd(); build(1,1,n); m=rd(); for(int i=1;i<=m;i++){ int f=rd(),x=rd(),y=rd(); if(f==2) extract_a_root(1,x,y); if(f==1) write(solve(1,x,y)),puts(""); } return 0; }