PKU A Simple Problem with Integers 3468
코드 가 인터넷 에서 왔 습 니 다 (원본 이 아 닙 니 다)
- /*
- Q ， ， C ，
- ， s， d, C ， ， ， ， ， s 。 ， O(logn) .
- Memory: 6760K
- Time: 1579MS */
-
- #include <iostream>
- using namespace std;
- #define ll long long
- const int MAXN = 100001;
- struct {
- int l, r;
- ll s, d;
- } nod[MAXN*3];
- int a[MAXN];
- void creat(int t, int l, int r) {
- if(l == r) {
- nod[t].l = nod[t].r = l, nod[t].s = a[l], nod[t].d = 0;
- return;
- }
- int m = (l+r) / 2;
- nod[t].l = l, nod[t].r = r, nod[t].d = 0;
- creat(t*2, l, m), creat(t*2+1, m+1, r);
- nod[t].s = nod[t*2].s + nod[t*2+1].s;
- }
- void inc(int t, int l, int r, int c) {
- if(l == nod[t].l && r == nod[t].r) {nod[t].d += c; return;}
- if(r <= nod[t*2].r) inc(t*2, l, r, c);
- else if(l >= nod[t*2+1].l) inc(t*2+1, l, r, c);
- else inc(t*2, l, nod[t*2].r, c), inc(t*2+1, nod[t*2+1].l, r, c);
- nod[t].s = nod[t*2].s + nod[t*2].d * (nod[t*2].r-nod[t*2].l+1) + nod[t*2+1].s + nod[t*2+1].d * (nod[t*2+1].r-nod[t*2+1].l+1);
- }
- ll query(int t, int l, int r) {
- if(nod[t].l == l && nod[t].r == r) return nod[t].s + nod[t].d * (r-l+1);
- ll sum;
- if(r <= nod[t*2].r) sum = query(t*2, l, r);
- else if(l >= nod[t*2+1].l) sum = query(t*2+1, l, r);
- else sum = query(t*2, l, nod[t*2].r) + query(t*2+1, nod[t*2+1].l, r);
- return sum + nod[t].d * (r-l+1);
- }
- int main() {
- int i, n, q, x1, x2, c;
- char s[2];
- while(scanf("%d%d", &n, &q) != EOF) {
- for(i = 1; i <= n; i++) scanf("%d", &a[i]);
- creat(1, 1, n);
- while(q--) {
- scanf("%s%d%d", s, &x1, &x2);
- if(s[0] == 'C') {scanf("%d", &c); inc(1, x1, x2, c);}
- else printf("%lld
", query(1, x1, x2));
- }
- }
- return 0;
- }
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
