[codevs 1080] 선분 트 리 연습 (단점 수정 + 구간 과)
5732 단어 = = = = 데이터 구조 = =선분 수템 플 릿
입력 설명 Input Description 입력 파일 의 첫 번 째 행동 의 정수 N 을 입력 하 십시오. 다음은 n 줄 n 개의 정수 입 니 다. 칸 의 원래 정 수 를 표시 합 니 다.다음 정수 m 를 이 어 m 줄 이 있다. m 개의 질문 을 나타 낸다. 첫 번 째 정 수 는 문의 번 호 를 나타 내 고 문의 번 호 는 1 이 증가 하 는 것 을 나타 내 며 뒤의 두 개의 수 x 와 A 는 위치 X 에 있 는 수치 에 A 를 증가 하 는 것 을 나타 낸다. 문의 번 호 는 구간 구 화 를 나타 내 고 뒤의 두 정 수 는 a 와 b 를 나타 내 며 [a, b] 간 의 구간 과 를 요구한다.
출력 설명 출력 설명
샘플 입력 Sample Input 6
4
5
6
2
1
3
4
1 3 5
2 1 4
1 1 9
2 2 6
샘플 출력 샘플 출력 22
22
데이터 범위 및 제시 Data Size & Hint 1 ≤ N ≤ 100000, m ≤ 10000.
#include
#include
#include
#include
#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define sz(x) (tree[x].r-tree[x].l+1)
#define ll long long
using namespace std;
const ll maxn=200000+5;
ll num[maxn];
ll n,m;
struct edge
{
ll l,r;
ll add,sum;
}tree[maxn<<2];
void update(ll p)
{
tree[p].sum=tree[L(p)].sum+tree[R(p)].sum;
return;
}
void spread(ll p)
{
if(!tree[p].add) return;
tree[L(p)].add+=tree[p].add;
tree[R(p)].add+=tree[p].add;
tree[L(p)].sum+=tree[p].add*sz(L(p));
tree[R(p)].sum+=tree[p].add*sz(R(p));
tree[p].add=0;
update(p);
return;
}
void build(ll l,ll r,ll p)
{
tree[p].l=l,tree[p].r=r;
if(l==r)
{
tree[p].sum=num[l];
return;
}
ll mid=(tree[p].l+tree[p].r)>>1;
build(l,mid,L(p));
build(mid+1,r,R(p));
update(p);
return;
}
/*void change(ll l,ll r,ll p,ll v)
{
if(l<=tree[p].l&&tree[p].r<=r)
{
tree[p].add+=v;
tree[p].sum+=v*sz(p);
return;
}
spread(p);
ll mid=(tree[p].l+tree[p].r)>>1;
if(l<=mid) change(l,r,L(p),v);
if(r>mid) change(l,r,R(p),v);
update(p);
return;
}
*/
void change(ll w,ll v,ll p)
{
if(tree[p].l==tree[p].r)
{
//tree[p].add+=v;
tree[p].sum+=v;
return;
}
spread(p);
ll mid=(tree[p].l+tree[p].r)>>1;
if(w<=mid) change(w,v,L(p));
else change(w,v,R(p));
update(p);
return;
}
ll ask_sum(ll l,ll r,ll p)
{
if(l<=tree[p].l&&tree[p].r<=r)
{
return tree[p].sum;
}
spread(p);
ll ans=0,mid=(tree[p].l+tree[p].r)>>1;
if(l<=mid) ans+=ask_sum(l,r,L(p));
if(r>mid) ans+=ask_sum(l,r,R(p));
return ans;
}
ll t,a,b;
int main()
{
scanf("%lld",&n);
memset(num,0,sizeof(num));
for(int i=1;i<=n;i++)
{
scanf("%lld",&num[i]);
}
build(1,n,1);
scanf("%lld",&m);
while(m--)
{
scanf("%lld%lld%lld",&t,&a,&b);
if(t==1)
{
change(a,b,1);
}
else if(t==2)
{
cout<1)<<'
';
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
HDUoj 1166 적군 포진 (나무 모양 배열/선분 수C 국 의 앙 숙 A 국 은 그동안 군사훈련 을 하고 있 었 기 때문에 C 국 간첩 두목 인 데 릭 과 그의 수하 인 티 디 는 또 바 빠 지기 시작 했다.A 국 가 는 해안선 을 따라 직선 으로 N 개 공병 캠프 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.