社区讨论
为什么线段树暴力区间修改能过,暴力区间查询不能过
P4145上帝造题的七分钟 2 / 花神游历各国参与者 4已保存回复 5
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 5 条
- 当前快照
- 1 份
- 快照标识符
- @mhjcue2h
- 此快照首次捕获于
- 2025/11/04 00:29 4 个月前
- 此快照最后确认于
- 2025/11/04 00:29 4 个月前
#11 TLE
CPP#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M=100009;
ll n,m,a[M],k,l,r;
struct SegmentTree{
ll l,r,add,cnt;
} t[4*M];
void build(ll p,ll l,ll r){
t[p].l=l,t[p].r=r;
if(l==r) return;
ll mid=(l+r)>>1;
build(p<<1,l,mid);
build((p<<1)|1,mid+1,r);
}
void spread(ll p){
if(t[p].add!=0){
t[p<<1].add+=t[p].add; t[(p<<1)|1].add+=t[p].add;
t[p<<1].cnt+=t[p].add; t[(p<<1)|1].cnt+=t[p].add;
t[p].add=0;
}
}
void change(ll p,ll l,ll r){
if(t[p].l>=l&&t[p].r<=r){
t[p].add++; t[p].cnt++; return;
}
if(t[p].cnt>=6) return;
spread(p);
ll mid=(t[p].l+t[p].r)>>1;
if(l<=mid) change(p<<1,l,r);
if(r>mid) change((p<<1)|1,l,r);
}
ll ask(ll p,ll l,ll r){
if(t[p].l>=l&&t[p].r<=r){
if(t[p].cnt>=6) return t[p].r-t[p].l+1;
if(t[p].l==t[p].r){
while(t[p].add>0) a[t[p].l]=sqrt(a[t[p].l]),t[p].add--;
return a[t[p].l];
}
spread(p);
ll mid=(t[p].l+t[p].r)>>1;
return ask(p<<1,l,r)+ask((p<<1)|1,l,r);
}
spread(p);
ll mid=(t[p].l+t[p].r)>>1,val=0;
if(l<=mid) val+=ask(p<<1,l,r);
if(r>mid) val+=ask((p<<1)|1,l,r);
return val;
}
int main(){
scanf("%lld",&n);
for(ll i=1;i<=n;i++) scanf("%lld",&a[i]);
build(1,1,n);
scanf("%lld",&m);
while(m--){
scanf("%lld%lld%lld",&k,&l,&r); if(l>r) swap(l,r);
if(!k) change(1,l,r);
else printf("%lld\n",ask(1,l,r));
}
return 0;
}
回复
共 5 条回复,欢迎继续交流。
正在加载回复...