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

暴力修改，记录一段是否全部为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;

}