마늘 손님 연습 문제: 구간 정수 조작
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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
NOIP 2016 D2T 2 - 지렁이하지만 구원병 은 m 초가 걸 려 야 도착 할 수 있 습 니 다.구체 적 으로 그 는 m 초 동안 매 초 에 잘 린 지렁이 가 잘 리 기 전의 길이 (m 개 수) 를 알 고 싶 어 한다.m 초 후 모든 지렁이 의 길...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.