POJ 3468 Integers 문제 풀이 및 코드 가 있 는 간단 한 문제

제목: n 개의 수 를 한 열 로 배열 하고 q 개의 조작 이 있 습 니 다. Q 와 C, Q 조작 [l, r] 질문 구간 [l, r] 의 구간 과 C 조작 [l, r] 은 [l, r] 구간 에 x 를 동시에 추가 하고 제목 에 따라 출력 하면 됩 니 다. 문제 풀이: 선분 수 는 주로 오 랜 만 에 쓰 고 오 랜 시간 동안 틀 렸 습 니 다. 만년 LL 은 더 이상 말 하지 않 겠 습 니 다. 범 위 를 잘못 보고 sum [] 은 LL 이 필요 없다 고 생각 합 니 다.또 중요 한 것 은 query 와 insert 가 경 계 를 넘 어 접근 할 수 없 기 때문에 구간 이 이 데이터 에 대해 무효 구간 이 라 하 더 라 도 대응 구간 에 접근 하면 반드시 pushdown.. 결 과 를 오랫동안 고민 한 것 을 잊 고 작은 데 이 터 는 문 제 를 찾 을 수 없습니다.

#include<iostream>
#include<cstdio>
#define LL long long
#define lson (o<<1)
#define rson ((o<<1)|1)
using namespace std;
const int maxn = 100005;
int n,q,l,r,c,a[maxn],lazy[4*maxn];
LL sum[4*maxn];
char s[5];
void build(int o,int l,int r)
{
    if(l==r)
    {
        sum[o]=(LL)a[l];
        return;
    }
    int mid = (l+r)/2;
    build(lson,l,mid);
    build(rson,mid+1,r);
    sum[o]=sum[lson]+sum[rson];
}
void pushdown(int o,int l,int r)
{
    if(lazy[o] && l!=r)
    {
        int mid = (l+r)/2;
        lazy[lson]+=lazy[o];
        lazy[rson]+=lazy[o];
        sum[lson]+=(LL)lazy[o]*(LL)(mid-l+1);
        sum[rson]+=(LL)lazy[o]*(LL)(r-mid);
    }
    lazy[o]=0;
}
void Insert(int o,int l,int r,int L,int R,int c)
{
    pushdown(o,l,r);
    if(l>=L && r<=R)
    {
        lazy[o]+=c;
        sum[o]+=(LL)(r-l+1)*(LL)lazy[o];
        pushdown(o,l,r);
        return;
    }
    if(l>R || r<L)return;
    int mid = (l+r)/2;
    Insert(lson,l,mid,L,R,c);
    Insert(rson,mid+1,r,L,R,c);
    sum[o]=sum[lson]+sum[rson];
}
LL query(int o,int l,int r,int L,int R)
{
    pushdown(o,l,r);
    if(l>=L && r<=R)return sum[o];
    if(l>R || r<L)return 0;
    int mid = (l+r)/2;
    LL ret=query(lson,l,mid,L,R)+query(rson,mid+1,r,L,R);
    sum[o]=sum[lson]+sum[rson];
    return ret;
}
int main(void)
{
    scanf("%d%d",&n,&q);
    for(int i = 1; i <= n; i++)
        scanf("%d",&a[i]);
    build(1,1,n);
    for(int i = 0; i < q; i++)
    {
        scanf("%s%d%d",s,&l,&r);
        if(s[0]=='C')
        {
            scanf("%d",&c);
            Insert(1,1,n,l,r,c);
        }
        else printf("%lld
",query(1,1,n,l,r));
    }
    return 0;
}