Lazy Propagation에 대해 공부해 보았다.
바로바로 업데이트하지 않고 lazy 배열을 만들어서 사용하는 것이 인상깊었다.
https://www.acmicpc.net/problem/10999
#include <stdio.h>
using namespace std;
typedef long long int ll;
int N,M,K;
ll arr[1000005],tree[4000005],lazy[4000005];
void build(int n,int l,int r){
if(l==r){
tree[n]=arr[l];
return;
}
int m=(l+r)/2;
build(n*2,l,m);build(n*2+1,m+1,r);
tree[n]=tree[n*2]+tree[n*2+1];
}
void update_lazy(int n,int l,int r){
if(lazy[n]!=0){
tree[n]+=lazy[n]*(r-l+1);
if(l!=r){
lazy[n*2]+=lazy[n];
lazy[n*2+1]+=lazy[n];
}
lazy[n]=0;
}
}
void update_range(int rl,int rr,ll dif,int n,int l,int r){
update_lazy(n,l,r);
if(r<rl||rr<l)return;
if(rl<=l&&r<=rr){
tree[n]+=dif*(r-l+1);
if(l!=r){
lazy[n*2]+=dif;
lazy[n*2+1]+=dif;
}
return;
}
int m=(l+r)/2;
update_range(rl,rr,dif,n*2,l,m);update_range(rl,rr,dif,n*2+1,m+1,r);
tree[n]=tree[n*2]+tree[n*2+1];
}
ll sum(int ql,int qr,int n,int l,int r){
어쩌구저쩌구
}
int main()
{
scanf("%d%d%d",&N,&M,&K);
for(int i=1;i<=N;i++){
scanf("%lld",&arr[i]);
}
build(1,1,N);
int x=K+M;
while(x--){
ll cmd,b,c,d;
scanf("%lld",&cmd);
if(cmd==1){
scanf("%lld%lld%lld",&b,&c,&d);
update_range(b,c,d,1,1,N);
}
else{
scanf("%lld%lld",&b,&c);
printf("%lld\n",sum(b,c,1,1,N));
}
}
return 0;
}
#include <stdio.h>
#include <algorithm>
using namespace std;
typedef long long int ll;
int N,M;
int arr[500005],tree[2000005],lazy[2000005];
void build(int n,int l,int r){
if(l==r){
tree[n]=arr[l];
return;
}
int m=(l+r)/2;
build(n*2,l,m);build(n*2+1,m+1,r);
tree[n]=tree[n*2]^tree[n*2+1];
}
void update_lazy(int n,int l,int r){
if(lazy[n]!=0){
tree[n]^=((r-l+1)%2==1?lazy[n]:0);
if(l!=r){
lazy[n*2]^=lazy[n];
lazy[n*2+1]^=lazy[n];
}
lazy[n]=0;
}
}
void update_range(int rl,int rr,int dif,int n,int l,int r){
update_lazy(n,l,r);
if(r<rl||rr<l)return;
if(rl<=l&&r<=rr){
tree[n]^=((r-l+1)%2==1?dif:0);
if(l!=r){
lazy[n*2]^=dif;
lazy[n*2+1]^=dif;
}
return;
}
int m=(l+r)/2;
update_range(rl,rr,dif,n*2,l,m);
update_range(rl,rr,dif,n*2+1,m+1,r);
tree[n]=tree[n*2]^tree[n*2+1];
}
int Xor(int ql,int qr,int n,int l,int r){
어쩌구저쩌구
}
int main()
{
scanf("%d",&N);
for(int i=1;i<=N;i++){
scanf("%d",&arr[i]);
}
build(1,1,N);
scanf("%d",&M);
while(M--){
int cmd,i,j,k;
scanf("%d",&cmd);
if(cmd==1){
scanf("%d%d%d",&i,&j,&k);
if(i>j)swap(i,j);
update_range(i+1,j+1,k,1,1,N);
}
else{
scanf("%d%d",&i,&j);
if(i>j)swap(i,j);
printf("%d\n",Xor(i+1,j+1,1,1,N));
}
}
return 0;
}
댓글 0