社区讨论
感觉思路没什么问题,但得不到正确答案
P4145上帝造题的七分钟 2 / 花神游历各国参与者 3已保存回复 7
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 7 条
- 当前快照
- 1 份
- 快照标识符
- @lojd5nwu
- 此快照首次捕获于
- 2023/11/04 09:26 2 年前
- 此快照最后确认于
- 2023/11/17 23:07 2 年前
附上了注释
唯一有问题的就是sum能不能直接开方
CPP#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n,m;
int w[N];
struct SegTree
{
int l,r;//[l,r]
long long sum,maxn;
}tr[N << 2];
//快读
inline void read(int& x)
{
x=0;int f = 1;char c = getchar();
while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}
while(isdigit(c)){x = (x<<1)+(x<<3)+(c^48);c = getchar();}
x*=f;
}
//向上更新回根
void pushup(int u)
{
tr[u].sum = tr[u<<1].sum+tr[u<<1|1].sum;
tr[u].maxn = max(tr[u<<1].maxn,tr[u<<1|1].maxn);
}
//递归建树tr[u]存储[l,r]
void build(int u,int l,int r)
{
if(l == r) tr[u] = {l,r,w[r],w[r]};
else
{
tr[u] = {l,r};
int mid = (l+r)>>1;
//左子树
build(u<<1,l,mid);
//右子树
build(u<<1|1,mid+1,r);
//递归建树区间和要上传到根
pushup(u);
}
}
//区间修改
void modify(int u,int l,int r)
{
//在当前区间内部
if(tr[u].l>=l && tr[u].r<=r)
{
//区间和满足结合律吗?这么写不知道可不可以
tr[u].sum = floor(sqrt(tr[u].sum));
tr[u].maxn = floor(sqrt(tr[u].maxn));
}
else//只要考虑大于1的情况
{
int mid = (tr[u].l+tr[u].r)>>1;
//当前区间在左半区间
if(l<=mid && tr[u<<1].maxn>1) modify(u<<1,l,r);
//当前区间在右半区间
if(r>mid && tr[u<<1|1].maxn>1) modify(u<<1|1,l,r);
//向上更新
pushup(u);
}
}
//区间查询
long long query(int u,int l,int r)
{
//就是当前区间
if(tr[u].l>=l && tr[u].r<=r) return tr[u].sum;
int mid = (tr[u].l+tr[u].r) >> 1;
long long sum = 0;
//当前区间在左半区间
if(l<=mid) sum += query(u<<1,l,r);
//当前区间在右半区间
if(r>mid) sum+=query(u<<1|1,l,r);
return sum;
}
int main()
{
read(n);
for(int i=1;i<=n;i++) read(w[i]);
read(m);
build(1,1,n);
int op,l,r;
while(m--)
{
read(op);read(l);read(r);
if(op == 2) modify(1,l,r);
else printf("%lld\n",query(1,l,r));
}
return 0;
}
回复
共 7 条回复,欢迎继续交流。
正在加载回复...