USACO 2015 December Contest, Platinum Problem 3. Counting Haybales

http://www.usaco.org/index.php?page=viewproblem2&cpid=578

Tips: segment tree with lazy tag

#include <iostream>
#include <stdio.h>
#include <cstring>
using namespace std;

#define int long long
typedef long long LL;
const int MAX_N = 2e5 + 6;
const LL INF = 1e17+6;

struct Node {
    Node* lc;
    Node* rc;
    LL val,sum,mn;
    LL tag;
    Node() {
        lc=rc=NULL;
        val=sum=tag=0;
        mn=INF;
    }
    void pull() {
        sum=lc->sum + rc->sum;
        mn = min(lc->mn,rc->mn);
    }
};

LL v[MAX_N];

Node* Build(int L,int R) {
    Node* node= new Node();
    if (L==R) {
        node->val = node->sum = node->mn = v[L];
        return node;
    }
    int mid=(L+R)>>1;
    node->lc=Build(L,mid);
    node->rc=Build(mid+1,R);
    node->pull();
    return node;
}

void push(Node* node,int L,int R) {
    if (L==R) {
        node->tag=0;
        return;
    }
    else if (node->tag != 0) {
        int mid=(L+R)>>1;
        node->lc->tag += node->tag;
        node->rc->tag += node->tag;
        node->lc->sum += (mid-L+1) * node->tag;
        node->rc->sum += (R-mid) * node->tag;
        node->lc->mn += node->tag;
        node->rc->mn += node->tag;
    }
    node->tag=0;
}

void modify(Node* node,int L,int R,int l,int r,int val) {
    if (L>r || l>R) return;
    else if (l<=L && R<=r) {
        node->sum += (R-L+1)*val;
        node->mn += val;
        node->tag += val;
        return;
    }
    int mid=(L+R)>>1;
    push(node,L,R);
    modify(node->lc,L,mid,l,r,val);
    modify(node->rc,mid+1,R,l,r,val);
    node->pull();
    return;
}

LL query(Node* node,int L,int R,int l,int r,int type) {
    if (type==1) {
        if (l>R || L>r) return 0;
        else if (l<=L && R<=r) return node->sum;
        push(node,L,R);
        int mid=(L+R)>>1;
        return query(node->lc,L,mid,l,r,type) + query(node->rc,mid+1,R,l,r,type);
    }
    else {
        if (l>R || L>r) return INF;
        else if (l<=L && R<=r) return node->mn;
        push(node,L,R);
        int mid=(L+R)>>1;
        return min(query(node->lc,L,mid,l,r,type) ,query(node->rc,mid+1,R,l,r,type) );
    }
}

main () {
    if (fopen("haybales.in","r")) {
        freopen("haybales.in","r",stdin);
        freopen("haybales.out","w",stdout);
    }
    int n,q;
    while (scanf("%lld %lld",&n,&q) != EOF) {
        for (int x=1;n>=x;x++) {
            scanf("%lld",&v[x]);
        }
        Node* root = Build(1,n);
        for (int x=0;q>x;x++) {
            getchar();
            char t;
            int a,b,c;
            scanf("%c %lld %lld",&t,&a,&b);
            if (t=='P') scanf("%lld",&c);
            if (t=='M') {
                printf("%lld\n",query(root,1,n,a,b,2));
            }
            else if (t=='S') {
                printf("%lld\n",query(root,1,n,a,b,1));
            }
            else {
                modify(root,1,n,a,b,c);
            }
        }
    }
}