10
1 2 3 4 5 6 7 8 9 10
5
0 1 10
1 1 10
1 1 5
0 5 8
1 4 8
Sample Output
Case #1: 19 7 6
剪枝：if(no[now].r-no[now].l+1 == no[now].val) return ;
#define ll long long
#define TLE std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout.precision(10);
#define lc now<<1
#define rc now<<1|1
#define ls now<<1,l,mid
#define rs now<<1|1,mid+1,r
#define half no[now].l+((no[now].r-no[now].l)>>1)
const int mxn = 100000+5; int mx;
struct node
{
int l,r,lazy;
ll val, num;
}no[mxn<<2];
void pushup(int now) { no[now].val = no[lc].val + no[rc].val ; return ;}
void build(int now , int l,int r)
{
no[now].l = l;no[now].r = r;
if(l==r)
{
scanf("%lld",&no[now].val);
return ;
}
int mid = l+((r-l)>>1);
build(lc,l,mid);
build(rc,mid+1,r);
pushup(now);
}
ll query(int now,int l,int r)
{
if(no[now].l>=l && r>=no[now].r)
return no[now].val;
ll mid = half;
ll cnt = 0 ;
if(l<=mid)
cnt += query(lc,l,r);
if(r>mid)
cnt += query(rc,l,r);
return cnt;
}
void updata(int now,int l,int r)
{
if(no[now].r-no[now].l+1 == no[now].val) return ;
if(no[now].l == no[now].r)
{
no[now].val = sqrt(no[now].val) ;
return ;
}
int mid = half;
if(l<=mid)
updata(lc,l,r);
if(r>mid)
updata(rc,l,r);
pushup(now);
}
// #define LOCAL
int main()
{
TLE;
int t,n,l,r,ase=1;
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
while(~scanf("%d",&n))
{
printf("Case #%d:\n",ase++);
build(1,1,n);
scanf("%d",&t);
while(t--)
{
int ch;
scanf("%d %d %d",&ch,&l,&r);
if(l>r) swap(l,r);
if(ch)
printf("%lld\n",query(1,l,r));
else
updata(1,l,r);
}
printf("\n");
}
return 0;
}
D - Can you answer these queries? （线段树+剪枝）
原文：https://www.cnblogs.com/Shallow-dream/p/11749712.html