마늘 손님 연습 문제: 구간 정수 조작

문제 설명
N 개의 정수 A1, A2,..., AN 을 드 리 려 면 구간 더하기, 구간 구 화 를 처리 해 야 합 니 다.형식 첫 줄 두 정수 N 과 Q (1 ≤ N, Q ≤ 10 ^ 5) 를 입력 하 십시오.두 번 째 줄 N 개의 정 수 는 A1, A2... AN (8739 ° Ai 8739 ° ≤ 10 ^ 9) 의 초기 값 을 나타 낸다.다음 Q 줄, 각 줄 의 조작: C a b c 는 Aa, A + 1... ab 의 각 수 에 c (8739 ° c * 8739 ° ≤ 10000) 를 추가 합 니 다.Q. a. b 는 Aa, Aa + 1... ab 의 합 을 물 어보 면 32 비트 정 수 를 초과 할 수 있 습 니 다.출력 형식 은 모든 Q 질문 에 한 줄 에 답 을 출력 합 니 다.샘플 입력
10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

샘플 출력
4
55
9
15

AC 코드
#include 
#include 
using namespace std;
const int MAX_N=(1e5)+50;
long long int s[MAX_N*4];
long long int col[MAX_N*4];

void up(int p){
    s[p]=s[p*2]+s[p*2+1];
    return;
}

void down(int p,int l,int r){
    if(col[p]){
        int mid=(l+r)/2;
        s[p*2]+=col[p]*(mid-l+1);
        s[p*2+1]+=col[p]*(r-mid);
        col[p*2]+=col[p];
        col[p*2+1]+=col[p];
        col[p]=0;
    }
    return;
}

void molify(int p,int l,int r,int x,int y,int v){
    if(l>=x&&r<=y){
        col[p]+=v;
        s[p]+=v*(r-l+1);
        return;
    }
    down(p,l,r);
    int mid=(l+r)/2;
    if(x<=mid)molify(p*2,l,mid,x,y,v);
    if(y>mid)molify(p*2+1,mid+1,r,x,y,v);
    up(p);
    return;
}

long long query(int p,int l,int r,int x,int y){
    if(l>=x&&r<=y){
        return s[p];
    }
    down(p,l,r);
    int mid=(l+r)/2;
    long long int res=0;
    if(x<=mid)res+=query(p*2,l,mid,x,y);
    if(y>mid)res+=query(p*2+1,mid+1,r,x,y);
    return res;
}


int main(){
    int N,Q;
    cin>>N>>Q;
    for(int i=1;i<=N;i++){
        int d;
        scanf("%d",&d);
        molify(1,1,N,i,i,d);
    }
    for(int i=1;i<=Q;i++){
        char X;
        scanf(" %c",&X);
        if(X=='C'){
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            molify(1,1,N,a,b,c);
        }else{
            int a,b;
            scanf("%d%d",&a,&b);
            cout<1,1,N,a,b)<return 0;
}

좋은 웹페이지 즐겨찾기