화신

제목:
길이 가 n 인 비 마이너스 시퀀스 와 m 개의 조작 을 보 여 줍 니 다.
조작 1 조회 구간 과;
조작 2 구간 내의 모든 숫자 를 처방 한다.
문제 풀이:
신 문 제 를 한참 미 룬 줄 알 았 는데 바보 문제 가 되 었 다.
한 마디 로 10 ^ 9 제곱 을 다섯 번 열 면 1 이 되 고 더 이상 수정 하지 않 을 수 있다 는 것 이다.
그러면 표 시 를 기록 하면 이 구간 이 제곱 으로 열 릴 수 있 는 지 여 부 를 나타 낸다.
선분 수 폭력 하면 돼. 롱 롱 켜 야 돼.
코드:
#include
#include
#include
#include
#define N 100100
#define lson l,mid,no<<1
#define rson mid+1,r,no<<1|1
using namespace std;
typedef long long ll;
ll sum[N<<2],a[N];
bool is[N<<2];
void Pushup(ll no)
{
	sum[no]=sum[no<<1]+sum[no<<1|1];
	is[no]=is[no<<1]&is[no<<1|1];
}
void build(ll l,ll r,ll no)
{
	if(l==r)
	{
		scanf("%lld",a+l);
		sum[no]=a[l];
		if(a[l]==1||a[l]==0)
			is[no]=1;
		else
			is[no]=0;
	}
	else
	{
		ll mid=(l+r)>>1;
		build(lson);
		build(rson);
		Pushup(no);
	}
}
void update(ll l,ll r,ll no,ll st,ll en)
{
	if(st<=l&&r<=en)
	{
		if(!is[no])
		{
			if(l!=r)
			{
				ll mid=(l+r)>>1;
				if(st<=mid)		update(lson,st,en);
				if(mid+1<=en)	update(rson,st,en);
				Pushup(no);
			}
			else
			{
				a[l]=sqrt(a[l]);
				sum[no]=a[l];
				if(a[l]==1)
					is[no]=1;
			}
		}
	}
	else
	{
		ll mid=(l+r)>>1;
		if(st<=mid)		update(lson,st,en);
		if(mid+1<=en)	update(rson,st,en);
		Pushup(no);
	}
}
ll query(ll l,ll r,ll no,ll st,ll en)
{
	if(st<=l&&r<=en)
	{
		return sum[no];
	}
	else
	{
		ll mid=(l+r)>>1;
		if(en<=mid)			return query(lson,st,en);
		else if(st>=mid+1)	return query(rson,st,en);
		else
			return query(lson,st,en)+query(rson,st,en);
	}
}
int main()
{
	ll n,m,i,j,k,l,r,op;
	scanf("%lld",&n);
	build(1,n,1);
	scanf("%lld",&m);
	for(i=1;i<=m;i++)
	{
		scanf("%lld%lld%lld",&op,&l,&r);
		if(op==1)
		{
			printf("%lld
",query(1,n,1,l,r)); } else { update(1,n,1,l,r); } } return 0; }

좋은 웹페이지 즐겨찾기