우 객 연습 경기 28B [선분 수 + 구간 과 + 구간 제곱 과 + 구간 수정]

링크:https://www.nowcoder.com/acm/contest/200/B 우 객 망
제목 설명
qn 언니 최고 ~
    qn 언니 가 너 에 게 n 길이 의 서열 과 m 번 의 조작 을 해 주 었 다.
    1 l r 질문 구간 [l, r] 내의 원소 와
    2 l r 질문 구간 [l, r] 내 원소 의 제곱 화해시키다
    3 l r x 구간 [l, r] 내의 모든 요 소 를 x 에 곱 하기
    4 l r x 구간 [l, r] 내의 모든 요 소 를 x 로 추가 합 니 다.
입력 설명:

      n,m

     n        

   m            opt，

 opt=1  opt=2，         l,r

 opt=3  opt=4，         l,r,x

            

출력 설명:

       1,2，        

 
예시 1
입력

5 6
1 2 3 4 5
1 1 5
2 1 5
3 1 2 1
4 1 3 2
1 1 4
2 2 3

출력

15
55
16
41

비고:

  100%    n=10000,m=200000 (      )

          long long    

문제 풀이:

#include 
#include 
#include 
#include 
#include 
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 10010;
int n, m;
struct SegmentTree{
    int l, r;
    ll sum1, sum2, add, mul;
    #define l(p) t[p].l
    #define r(p) t[p].r
    #define sum1(p) t[p].sum1
    #define sum2(p) t[p].sum2
    #define add(p) t[p].add
    #define mul(p) t[p].mul
}t[maxn<<2];
ll a[maxn];
void push_up(int p){
    sum1(p) = sum1(p<<1) + sum1(p<<1|1);
    sum2(p) = sum2(p<<1) + sum2(p<<1|1);
}
void push_down(int p){
    if(mul(p) != 1){
        mul(2*p) *= mul(p);
        mul(2*p+1) *= mul(p);
        if(add(2*p)) add(2*p) *= mul(p);
        if(add(2*p+1)) add(2*p+1) *= mul(p);
        sum1(2*p) *= mul(p);
        sum1(2*p+1) *= mul(p);
        sum2(2*p) *= (mul(p)*mul(p));
        sum2(2*p+1) *= (mul(p)*mul(p));
        mul(p) = 1;
    }
    if(add(p)){
        add(2*p) += add(p);
        add(2*p+1) += add(p);
        sum2(2*p) += ((r(2*p)-l(2*p)+1)*add(p)*add(p) + 2*sum1(2*p)*add(p));
        sum2(2*p+1) += ((r(2*p+1)-l(2*p+1)+1)*add(p)*add(p) + 2*sum1(2*p+1)*add(p));
        sum1(2*p) += add(p)*(r(2*p)-l(2*p)+1);
        sum1(2*p+1) += add(p)*(r(2*p+1)-l(2*p+1)+1);
        add(p) = 0;
    }
}
void build(int p, int l, int r){
    l(p) = l, r(p) = r;
    add(p) = 0, mul(p) = 1;
    if(l == r){
        sum1(p) = a[l];
        sum2(p) = a[l] * a[l];
        return ;
    }
    int mid = (l+r)>>1;
    build(2*p, l, mid);
    build(2*p+1, mid+1, r);
    push_up(p);
}
void change(int p, int l, int r, int c, int op){
    if(l <= l(p) && r >= r(p)){
        if(op == 3){
            mul(p) = mul(p)*c;
            if(add(p)) add(p) = add(p)*c;
            sum1(p) = sum1(p)*c;
            sum2(p) = sum2(p)*c*c;
        }else{
            add(p) +=  c;
            sum2(p) += (r(p)-l(p)+1)*c*c + 2*sum1(p)*c;
            sum1(p) += (r(p)-l(p)+1)*c;
        }
        return ;
    }
    push_down(p);
    int mid = (l(p)+r(p)) / 2;
    if(l <= mid) change(2*p, l, r, c, op);
    if(r > mid) change(2*p+1, l, r, c, op);
    push_up(p);
}
ll ask(int p, int l, int r, int op){
    if(l <= l(p) && r >= r(p)){
        if(op == 1) return sum1(p);
        if(op == 2) return sum2(p);
    }
    push_down(p);
    int mid = (l(p)+r(p))/2;
    ll sum = 0;
    if(l <= mid) sum += ask(2*p, l, r, op);
    if(r > mid) sum += ask(2*p+1, l, r, op);
    return sum;
}
int main()
{
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++){
        scanf("%lld
", &a[i]);
    }
    build(1, 1, n);
    int op, l, r, x;
    while(m--){
        scanf("%d %d %d", &op, &l, &r);
        if(op == 1){
            printf("%lld
", ask(1, l, r, 1));
        }else if(op == 2){
            printf("%lld
", ask(1, l, r, 2));
        }else if(op == 3){
            scanf("%d", &x);
            change(1, l, r, x, 3);
        }else{
            scanf("%d", &x);
            change(1, l, r, x, 4);
        }
    }
    return 0;
}