글 읽기 - 뭐가 문제인지 모르겠네요ㅜㅜ

joseph0528 3년 전 1

제목그대로 뭐가 문제인지모르겠어요ㅜㅜ tree1=lazytree tree1를 struct으로 왼쪽,오른쪽값을 저장할수있게 한뒤 범위안에 들었을때 그범위의 왼쪽을 n*2에 넣고 n*2+1에 오른쪽을 넣어주고 자신의 위치에서만 구간의 합을 더해주는방식인데 방식은 맞는거같은데 왜 틀린지 모르겠네요 ㅜㅜ

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<long long>l(1000001);
struct nod{
    ll le,ri;
};
ll a,tree[5000000];
nod tree1[5000000];
ll seg(ll n,ll s,ll e){
    if(s==e){return tree[n]=l[s];}
    return tree[n]=seg(n * 2,s,(s + e) / 2) + seg(n * 2 + 1,(s + e) / 2 + 1,e);
}
void propagate(ll n,ll s,ll e){
    if(tree1[n].le>0){
        if(s!=e){
            tree1[n * 2]={tree1[n].le, (tree1[n].le + tree1[n].ri) / 2};
            tree1[n * 2 + 1]={(tree1[n].le + tree1[n].ri) / 2 + 1, tree1[n].ri};
        }
        tree[n]+=(tree1[n].ri * (tree1[n].ri + 1) / 2)-((tree1[n].le - 1) * tree1[n].le / 2);
        tree1[n]={0,0};
    }
}
ll max1(ll n,ll s,ll e,ll left,ll right){
    propagate(n,s,e);
    if(left>e||right<s){return 0;}
    if(left<=s&&e<=right){return tree[n];}
    return max1(n * 2,s,(s + e)/2,left,right)+max1(n * 2 + 1,(s + e) / 2 + 1,e,left,right);
}
void change(ll n,ll s,ll e,ll s1,ll e1){
    propagate(n,s,e);
    if(s1<=s&&e<=e1){tree1[n].le=s-s1+1;tree1[n].ri=e-s1+1;propagate(n,s,e);return;}
    if(e1<s||s1>e){return;}
    change(n * 2,s,(s + e) / 2,s1,e1);
    change(n * 2 + 1,(s + e) / 2 + 1,e,s1,e1);
    tree[n]=tree[n * 2]+tree[n * 2 + 1];
}
int main()
{
    ll b,c,d,q,k,gh,gk;
    scanf("%lld",&a);
    int i;
    for(i=0;i<a;i++){scanf("%lld",&l[i]);}
    seg(1,0,a-1);
    scanf("%lld",&b);
    for(i=0;i<b;i++){
        scanf("%lld",&q);
        if(q==2){
            scanf("%lld",&c);
            printf("%lld\n",max1(1,0,a-1,c-1,c-1));
        }
        else{
            scanf("%lld %lld",&c,&d);
            change(1,0,a-1,c-1,d-1);
        }
    }
}

leinad2 3년 전 0

지금 풀이에서 틀린 점은 발견하지 못했지만, 더 좋은 방법을 추천드립니다. B[i]=A[i]-A[i-1]이라 설정하면 어떻게 될까요? ㅎㅎ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

뭐가 문제인지 모르겠네요ㅜㅜ

joseph0528 3년 전 1

leinad2 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말