화신
2037 단어 bzoj데이터 구조OIer 문제 풀이 기록
길이 가 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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
bzoj1010 장난감 포장 [결정 단조성 최적화 dp]하나의 모범 문제라고 할 수 있다.우리는 먼저 소박한 dp방정식을 얻을 수 있다. f[i]=min(f[j]+w(j,i)),j∈[0,i). w(j,i)는 j+1~i를 포장하여 운송하는 비용의 시간 복잡도는 O(n2)라...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.