Ideone.com

download

copy

 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
 
struct SegmentTreeNode 
{
    ll sum = 0;
    void assignLeaf(ll value) 
    {
        sum = value;
    }
 
    void merge(SegmentTreeNode& left, SegmentTreeNode& right) 
    {
        sum = left.sum + right.sum;
    }
 
    ll getValue() 
    {
        return sum;
    }
};
 
class SegmentTree 
{
    SegmentTreeNode* nodes;
    int N;
    vector<ll> lazy;
    public:
 
    SegmentTree(ll arr[], int N) 
    {
        this->N = N;
        nodes = new SegmentTreeNode[4*N+1];
        lazy.resize(4*N+1,0);
        buildTree(arr, 1, 0, N-1);
    }
 
    ~SegmentTree() 
    {
        delete[] nodes;
    }
 
    ll getValue(int lo, int hi) 
    {
        SegmentTreeNode result = getValue(1, 0, N-1, lo, hi);
        return result.getValue();
    }
 
    void update(int index, ll value)
    {
        update(1, 0, N-1, index, value);
    }
 
 
    void buildTree(ll arr[], int stIndex, int lo, int hi) 
    {
        if (lo == hi) 
        {
            nodes[stIndex].assignLeaf(arr[lo]);
            return;
        }
        int left = 2 * stIndex, right = left + 1, mid = (lo + hi) / 2;
        buildTree(arr, left, lo, mid);
        buildTree(arr, right, mid + 1, hi);
        nodes[stIndex].merge(nodes[left], nodes[right]);
    }
 
    SegmentTreeNode getValue(int stIndex, int left, int right, int lo, int hi) 
    {
        if (left == lo && right == hi)
        return nodes[stIndex];
 
        int mid = (left + right) / 2;
        if (lo > mid)
        return getValue(2*stIndex+1, mid+1, right, lo, hi);
        if (hi <= mid)
        return getValue(2*stIndex, left, mid, lo, hi);
 
        SegmentTreeNode leftResult = getValue(2*stIndex, left, mid, lo, mid);
        SegmentTreeNode rightResult = getValue(2*stIndex+1, mid+1, right, mid+1, hi);
        SegmentTreeNode result;
        result.merge(leftResult, rightResult);
        return result;
    }
 
    int getSegmentTreeSize(int N) 
    {
        int size = 1;
        for (; size < N; size <<= 1);
        return size << 1;
    }
 
    void update(int stIndex, int lo, int hi, int index, ll value) 
    {
        if (lo == hi) 
        {
            nodes[stIndex].assignLeaf(value);
            return;
        }
 
        int left = 2 * stIndex, right = left + 1, mid = (lo + hi) / 2;
        if (index <= mid)
        update(left, lo, mid, index, value);
        else
        update(right, mid+1, hi, index, value);   
        nodes[stIndex].merge(nodes[left], nodes[right]);
    }
 
    void lazy_update(int a, int b, int start, int end, int index, ll val)
    {
        if(lazy[index] != 0)
        {
            nodes[index].sum += (end-start+1)*lazy[index];
            if(start != end)
            {
                lazy[2*index] += lazy[index];
                lazy[2*index+1] += lazy[index];
            }            
            lazy[index] = 0;
        }
        if(b < start || a > end) return;
 
        if(a <= start && b >= end)
        {
            nodes[index].sum += (end-start+1)*val;
            if(start != end)
            {
                lazy[2*index] += val;
                lazy[2*index+1] += val;
            }
            return;
        }
 
        else
        {
            int mid = (start+end)/2;
            lazy_update(a,b,start,mid,2*index,val);
            lazy_update(a,b,mid+1,end,2*index+1,val);
            nodes[index].sum = nodes[2*index].sum + nodes[2*index+1].sum;
        }
    }
 
    ll lazy_query(int a, int b, int start,int end, int index)
    {
        if(b < start || a > end) return 0;
 
        if(lazy[index] != 0)
        {
            nodes[index].sum += (end-start+1)*lazy[index];
            if(start != end)
            {
                lazy[2*index] += lazy[index];
                lazy[2*index+1] += lazy[index];
            }            
            lazy[index] = 0;
        }
 
        if(a <= start && b >= end)
        {
            return nodes[index].sum;
        }
 
        else
        {
            int mid = (start+end)/2;
            ll l = lazy_query(a,b,start,mid,2*index);
            ll r = lazy_query(a,b,mid+1,end,2*index+1);
            return l+r;
        }
    }
};
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin>>t;
    while(t--)
    {
        int n,c;
        cin>>n>>c;
        ll arr[n];
        for(int i=0; i<n; ++i) arr[i] = 0;
        SegmentTree st(arr,n);
        while(c--)
        {
            int x;
            cin>>x;
            if(x == 0)
            {
                int a,b;
                ll value;
                cin>>a>>b>>value;
                st.lazy_update(a-1,b-1,0,n-1,1,value);
            }
            else
            {
                int a,b;
                cin>>a>>b;
                cout << st.lazy_query(a-1,b-1,0,n-1,1) <<"\n";
            }
        }
    }
    return 0;
}

CiNpbmNsdWRlPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgbGwgbG9uZyBsb25nCiAKc3RydWN0IFNlZ21lbnRUcmVlTm9kZSAKewogICAgbGwgc3VtID0gMDsKICAgIHZvaWQgYXNzaWduTGVhZihsbCB2YWx1ZSkgCiAgICB7CiAgICAgICAgc3VtID0gdmFsdWU7CiAgICB9CiAgICAKICAgIHZvaWQgbWVyZ2UoU2VnbWVudFRyZWVOb2RlJiBsZWZ0LCBTZWdtZW50VHJlZU5vZGUmIHJpZ2h0KSAKICAgIHsKICAgICAgICBzdW0gPSBsZWZ0LnN1bSArIHJpZ2h0LnN1bTsKICAgIH0KICAgIAogICAgbGwgZ2V0VmFsdWUoKSAKICAgIHsKICAgICAgICByZXR1cm4gc3VtOwogICAgfQp9OwogCmNsYXNzIFNlZ21lbnRUcmVlIAp7CiAgICBTZWdtZW50VHJlZU5vZGUqIG5vZGVzOwogICAgaW50IE47CiAgICB2ZWN0b3I8bGw+IGxhenk7CiAgICBwdWJsaWM6CiAgICAKICAgIFNlZ21lbnRUcmVlKGxsIGFycltdLCBpbnQgTikgCiAgICB7CiAgICAgICAgdGhpcy0+TiA9IE47CiAgICAgICAgbm9kZXMgPSBuZXcgU2VnbWVudFRyZWVOb2RlWzQqTisxXTsKICAgICAgICBsYXp5LnJlc2l6ZSg0Kk4rMSwwKTsKICAgICAgICBidWlsZFRyZWUoYXJyLCAxLCAwLCBOLTEpOwogICAgfQogIAogICAgflNlZ21lbnRUcmVlKCkgCiAgICB7CiAgICAgICAgZGVsZXRlW10gbm9kZXM7CiAgICB9CiAgCiAgICBsbCBnZXRWYWx1ZShpbnQgbG8sIGludCBoaSkgCiAgICB7CiAgICAgICAgU2VnbWVudFRyZWVOb2RlIHJlc3VsdCA9IGdldFZhbHVlKDEsIDAsIE4tMSwgbG8sIGhpKTsKICAgICAgICByZXR1cm4gcmVzdWx0LmdldFZhbHVlKCk7CiAgICB9CiAgCiAgICB2b2lkIHVwZGF0ZShpbnQgaW5kZXgsIGxsIHZhbHVlKQogICAgewogICAgICAgIHVwZGF0ZSgxLCAwLCBOLTEsIGluZGV4LCB2YWx1ZSk7CiAgICB9CiAgCiAgICAKICAgIHZvaWQgYnVpbGRUcmVlKGxsIGFycltdLCBpbnQgc3RJbmRleCwgaW50IGxvLCBpbnQgaGkpIAogICAgewogICAgICAgIGlmIChsbyA9PSBoaSkgCiAgICAgICAgewogICAgICAgICAgICBub2Rlc1tzdEluZGV4XS5hc3NpZ25MZWFmKGFycltsb10pOwogICAgICAgICAgICByZXR1cm47CiAgICAgICAgfQogICAgICAgIGludCBsZWZ0ID0gMiAqIHN0SW5kZXgsIHJpZ2h0ID0gbGVmdCArIDEsIG1pZCA9IChsbyArIGhpKSAvIDI7CiAgICAgICAgYnVpbGRUcmVlKGFyciwgbGVmdCwgbG8sIG1pZCk7CiAgICAgICAgYnVpbGRUcmVlKGFyciwgcmlnaHQsIG1pZCArIDEsIGhpKTsKICAgICAgICBub2Rlc1tzdEluZGV4XS5tZXJnZShub2Rlc1tsZWZ0XSwgbm9kZXNbcmlnaHRdKTsKICAgIH0KICAKICAgIFNlZ21lbnRUcmVlTm9kZSBnZXRWYWx1ZShpbnQgc3RJbmRleCwgaW50IGxlZnQsIGludCByaWdodCwgaW50IGxvLCBpbnQgaGkpIAogICAgewogICAgICAgIGlmIChsZWZ0ID09IGxvICYmIHJpZ2h0ID09IGhpKQogICAgICAgIHJldHVybiBub2Rlc1tzdEluZGV4XTsKICAgICAgICAgICAgCiAgICAgICAgaW50IG1pZCA9IChsZWZ0ICsgcmlnaHQpIC8gMjsKICAgICAgICBpZiAobG8gPiBtaWQpCiAgICAgICAgcmV0dXJuIGdldFZhbHVlKDIqc3RJbmRleCsxLCBtaWQrMSwgcmlnaHQsIGxvLCBoaSk7CiAgICAgICAgaWYgKGhpIDw9IG1pZCkKICAgICAgICByZXR1cm4gZ2V0VmFsdWUoMipzdEluZGV4LCBsZWZ0LCBtaWQsIGxvLCBoaSk7CiAgICAgICAgICAgIAogICAgICAgIFNlZ21lbnRUcmVlTm9kZSBsZWZ0UmVzdWx0ID0gZ2V0VmFsdWUoMipzdEluZGV4LCBsZWZ0LCBtaWQsIGxvLCBtaWQpOwogICAgICAgIFNlZ21lbnRUcmVlTm9kZSByaWdodFJlc3VsdCA9IGdldFZhbHVlKDIqc3RJbmRleCsxLCBtaWQrMSwgcmlnaHQsIG1pZCsxLCBoaSk7CiAgICAgICAgU2VnbWVudFRyZWVOb2RlIHJlc3VsdDsKICAgICAgICByZXN1bHQubWVyZ2UobGVmdFJlc3VsdCwgcmlnaHRSZXN1bHQpOwogICAgICAgIHJldHVybiByZXN1bHQ7CiAgICB9CiAKICAgIGludCBnZXRTZWdtZW50VHJlZVNpemUoaW50IE4pIAogICAgewogICAgICAgIGludCBzaXplID0gMTsKICAgICAgICBmb3IgKDsgc2l6ZSA8IE47IHNpemUgPDw9IDEpOwogICAgICAgIHJldHVybiBzaXplIDw8IDE7CiAgICB9CiAgCiAgICB2b2lkIHVwZGF0ZShpbnQgc3RJbmRleCwgaW50IGxvLCBpbnQgaGksIGludCBpbmRleCwgbGwgdmFsdWUpIAogICAgewogICAgICAgIGlmIChsbyA9PSBoaSkgCiAgICAgICAgewogICAgICAgICAgICBub2Rlc1tzdEluZGV4XS5hc3NpZ25MZWFmKHZhbHVlKTsKICAgICAgICAgICAgcmV0dXJuOwogICAgICAgIH0KICAgIAogICAgICAgIGludCBsZWZ0ID0gMiAqIHN0SW5kZXgsIHJpZ2h0ID0gbGVmdCArIDEsIG1pZCA9IChsbyArIGhpKSAvIDI7CiAgICAgICAgaWYgKGluZGV4IDw9IG1pZCkKICAgICAgICB1cGRhdGUobGVmdCwgbG8sIG1pZCwgaW5kZXgsIHZhbHVlKTsKICAgICAgICBlbHNlCiAgICAgICAgdXBkYXRlKHJpZ2h0LCBtaWQrMSwgaGksIGluZGV4LCB2YWx1ZSk7ICAgCiAgICAgICAgbm9kZXNbc3RJbmRleF0ubWVyZ2Uobm9kZXNbbGVmdF0sIG5vZGVzW3JpZ2h0XSk7CiAgICB9CiAKICAgIHZvaWQgbGF6eV91cGRhdGUoaW50IGEsIGludCBiLCBpbnQgc3RhcnQsIGludCBlbmQsIGludCBpbmRleCwgbGwgdmFsKQogICAgewogICAgICAgIGlmKGxhenlbaW5kZXhdICE9IDApCiAgICAgICAgewogICAgICAgICAgICBub2Rlc1tpbmRleF0uc3VtICs9IChlbmQtc3RhcnQrMSkqbGF6eVtpbmRleF07CiAgICAgICAgICAgIGlmKHN0YXJ0ICE9IGVuZCkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgbGF6eVsyKmluZGV4XSArPSBsYXp5W2luZGV4XTsKICAgICAgICAgICAgICAgIGxhenlbMippbmRleCsxXSArPSBsYXp5W2luZGV4XTsKICAgICAgICAgICAgfSAgICAgICAgICAgIAogICAgICAgICAgICBsYXp5W2luZGV4XSA9IDA7CiAgICAgICAgfQogICAgICAgIGlmKGIgPCBzdGFydCB8fCBhID4gZW5kKSByZXR1cm47CiAKICAgICAgICBpZihhIDw9IHN0YXJ0ICYmIGIgPj0gZW5kKQogICAgICAgIHsKICAgICAgICAgICAgbm9kZXNbaW5kZXhdLnN1bSArPSAoZW5kLXN0YXJ0KzEpKnZhbDsKICAgICAgICAgICAgaWYoc3RhcnQgIT0gZW5kKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBsYXp5WzIqaW5kZXhdICs9IHZhbDsKICAgICAgICAgICAgICAgIGxhenlbMippbmRleCsxXSArPSB2YWw7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgcmV0dXJuOwogICAgICAgIH0KIAogICAgICAgIGVsc2UKICAgICAgICB7CiAgICAgICAgICAgIGludCBtaWQgPSAoc3RhcnQrZW5kKS8yOwogICAgICAgICAgICBsYXp5X3VwZGF0ZShhLGIsc3RhcnQsbWlkLDIqaW5kZXgsdmFsKTsKICAgICAgICAgICAgbGF6eV91cGRhdGUoYSxiLG1pZCsxLGVuZCwyKmluZGV4KzEsdmFsKTsKICAgICAgICAgICAgbm9kZXNbaW5kZXhdLnN1bSA9IG5vZGVzWzIqaW5kZXhdLnN1bSArIG5vZGVzWzIqaW5kZXgrMV0uc3VtOwogICAgICAgIH0KICAgIH0KIAogICAgbGwgbGF6eV9xdWVyeShpbnQgYSwgaW50IGIsIGludCBzdGFydCxpbnQgZW5kLCBpbnQgaW5kZXgpCiAgICB7CiAgICAgICAgaWYoYiA8IHN0YXJ0IHx8IGEgPiBlbmQpIHJldHVybiAwOwogCiAgICAgICAgaWYobGF6eVtpbmRleF0gIT0gMCkKICAgICAgICB7CiAgICAgICAgICAgIG5vZGVzW2luZGV4XS5zdW0gKz0gKGVuZC1zdGFydCsxKSpsYXp5W2luZGV4XTsKICAgICAgICAgICAgaWYoc3RhcnQgIT0gZW5kKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBsYXp5WzIqaW5kZXhdICs9IGxhenlbaW5kZXhdOwogICAgICAgICAgICAgICAgbGF6eVsyKmluZGV4KzFdICs9IGxhenlbaW5kZXhdOwogICAgICAgICAgICB9ICAgICAgICAgICAgCiAgICAgICAgICAgIGxhenlbaW5kZXhdID0gMDsKICAgICAgICB9CiAKICAgICAgICBpZihhIDw9IHN0YXJ0ICYmIGIgPj0gZW5kKQogICAgICAgIHsKICAgICAgICAgICAgcmV0dXJuIG5vZGVzW2luZGV4XS5zdW07CiAgICAgICAgfQogCiAgICAgICAgZWxzZQogICAgICAgIHsKICAgICAgICAgICAgaW50IG1pZCA9IChzdGFydCtlbmQpLzI7CiAgICAgICAgICAgIGxsIGwgPSBsYXp5X3F1ZXJ5KGEsYixzdGFydCxtaWQsMippbmRleCk7CiAgICAgICAgICAgIGxsIHIgPSBsYXp5X3F1ZXJ5KGEsYixtaWQrMSxlbmQsMippbmRleCsxKTsKICAgICAgICAgICAgcmV0dXJuIGwrcjsKICAgICAgICB9CiAgICB9Cn07CiAKaW50IG1haW4oKQp7CiAgICBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKICAgIGNpbi50aWUoTlVMTCk7CiAgICBpbnQgdDsKICAgIGNpbj4+dDsKICAgIHdoaWxlKHQtLSkKICAgIHsKICAgICAgICBpbnQgbixjOwogICAgICAgIGNpbj4+bj4+YzsKICAgICAgICBsbCBhcnJbbl07CiAgICAgICAgZm9yKGludCBpPTA7IGk8bjsgKytpKSBhcnJbaV0gPSAwOwogICAgICAgIFNlZ21lbnRUcmVlIHN0KGFycixuKTsKICAgICAgICB3aGlsZShjLS0pCiAgICAgICAgewogICAgICAgICAgICBpbnQgeDsKICAgICAgICAgICAgY2luPj54OwogICAgICAgICAgICBpZih4ID09IDApCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGludCBhLGI7CiAgICAgICAgICAgICAgICBsbCB2YWx1ZTsKICAgICAgICAgICAgICAgIGNpbj4+YT4+Yj4+dmFsdWU7CiAgICAgICAgICAgICAgICBzdC5sYXp5X3VwZGF0ZShhLTEsYi0xLDAsbi0xLDEsdmFsdWUpOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgaW50IGEsYjsKICAgICAgICAgICAgICAgIGNpbj4+YT4+YjsKICAgICAgICAgICAgICAgIGNvdXQgPDwgc3QubGF6eV9xdWVyeShhLTEsYi0xLDAsbi0xLDEpIDw8IlxuIjsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KICAgIHJldHVybiAwOwp9IA==

Runtime error #stdin #stdout 0s 16672KB

stdin

copy

Standard input is empty

stdout

copy

https://ideone.com/728cAm

language:

C++ 4.3.2 (gcc-4.3.2)

created:

visibility:

secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language