跟我念三遍:
暴力修改暴力修改暴力修改
再念三遍:
立Flag立Flag立Flag
(貌似有什么奇怪的事情发生了)
P3038/P3211 通用AC Code:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAXN=200005;
long long a[MAXN*2],b[MAXN*2],sum[MAXN*2];
int n,m,xx,ll,rr;
inline int Lson(int x)
{
return x*2;
}
inline int Rson(int x)
{
return x*2+1;
}
void update(int x)
{
if (b[Lson(x)]==2||b[Rson(x)]==2)
b[x]=2;
else
b[x]=1;
sum[x]=sum[Lson(x)]+sum[Rson(x)];
}
void build(int x,int l,int r)
{
if (l==r)
{
scanf("%lld",&a[x]);
sum[x]=a[x];
if (a[x]<=1)
b[x]=1;
else
b[x]=2;
}
if (l>=r)
return;
int mid=(l+r)/2;
build(Lson(x),l,mid);
build(Rson(x),mid+1,r);
update(x);
}
void pushdown(int x,int l,int r)
{
if (b[x]<=1)
return;
if (l==r)
{
a[x]=sum[x]=sqrt(a[x]);
if (a[x]<=1)
b[x]=1;
return;
}
int mid=(l+r)/2;
pushdown(Lson(x),l,mid);
if (mid<r)
pushdown(Rson(x),mid+1,r);
update(x);
}
void change(int x,int l,int r,int L,int R)
{
if (b[x]<=1)
return;
int mid=(l+r)/2;
if (L<=l&&R>=r)
{
pushdown(x,l,r);
return;
}
if (L<=mid)
change(Lson(x),l,mid,L,R);
if (mid<R)
change(Rson(x),mid+1,r,L,R);
update(x);
}
long long Query(int x,int l,int r,int L,int R)
{
int mid=(l+r)/2;
long long ans=0;
if (l>=L&&r<=R)
return sum[x];
if (L<=mid)
ans+=Query(Lson(x),l,mid,L,R);
if (mid<R)
ans+=Query(Rson(x),mid+1,r,L,R);
return ans;
}
int main()
{
scanf("%d",&n);
build(1,1,n);
scanf("%d",&m);
while (m--)
{
scanf("%d%d%d",&xx,&ll,&rr);
if (ll>rr)
swap(ll,rr);
if (xx==1)
printf("%lld\n",Query(1,1,n,ll,rr));
else
change(1,1,n,ll,rr);
}
return 0;
}