【线段树】bzoj3038 上帝造题的七分钟2 / bzoj3211 花神游历各国

时间:2022-03-17 16:06:25

暴力修改,记录一段是否全部为1或0,若全是了,则不再修改。

注意3211一定要判是否为0,否则会T得惨无人道。

#include<cstdio>
#include<cmath>
using namespace std;
#define lson rt<<1,l,m
#define rson rt<<1|1,m+1,r
int f,c;
typedef long long ll;
inline void R(int &x){
c=0;f=1;
for(;c<'0'||c>'9';c=getchar())if(c=='-')f=-1;
for(x=0;c>='0'&&c<='9';c=getchar())(x*=10)+=(c-'0');
x*=f;
}
void P(ll x){
if(x<10)putchar(x+'0');
else{P(x/10);putchar(x%10+'0');}
}
ll sumv[400001];
bool All[400001];
int op;
int x,y,n,m;
void buildtree(int rt,int l,int r)
{
if(l==r)
{
int t; R(t); sumv[rt]=(ll)t;
if(sumv[rt]==1||sumv[rt]==0) All[rt]=1;
return;
}
int m=(l+r)>>1;
buildtree(lson); buildtree(rson);
sumv[rt]=sumv[rt<<1]+sumv[rt<<1|1];
All[rt]=(All[rt<<1]&All[rt<<1|1]);
}
void update(int ql,int qr,int rt,int l,int r)
{
if(All[rt]) return;
if(l==r)
{
sumv[rt]=sqrt(sumv[rt]);
if(sumv[rt]==1) All[rt]=1;
return;
}
int m=l+r>>1;
if(ql<=m) update(ql,qr,lson);
if(m<qr) update(ql,qr,rson);
sumv[rt]=sumv[rt<<1]+sumv[rt<<1|1];
All[rt]=(All[rt<<1]&All[rt<<1|1]);
}
ll query(int ql,int qr,int rt,int l,int r)
{
if(ql<=l&&r<=qr) return sumv[rt];
int m=l+r>>1; ll res=0;
if(ql<=m) res+=query(ql,qr,lson);
if(m<qr) res+=query(ql,qr,rson);
return res;
}
int main()
{
R(n);
buildtree(1,1,n);
R(m);
for(int i=1;i<=m;++i)
{
R(op); R(x); R(y);
if(op==2) update(x,y,1,1,n);
else P(query(x,y,1,1,n)),puts("");
}
return 0;
}