Cod sursa(job #2890152)

Utilizator petru-robuRobu Petru petru-robu Data 14 aprilie 2022 18:22:22
Problema Arbori de intervale Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.79 kb
#include <bits/stdc++.h>
#define M 5000
using namespace std;
ifstream fin("data.txt");

int A[M], aint[2*M], n, q, res=0;
int lazy[2*M];

void citire()
{
  fin>>n;
  for(int i=1; i<=n; i++)
    fin>>A[i];
}

void build(int nod, int st, int dr)
{
  if(st==dr)
    aint[nod]=A[st];
  else
  {
    int m = (st+dr)/2;
    build(2*nod, st, m);
    build(2*nod+1, m+1, dr);
    aint[nod]=aint[2*nod]+aint[2*nod+1];
  }
}

void lazyUpdate(int nod, int st, int dr, int a, int b, int val)
{
  if(lazy[nod] != 0)
    {
      aint[nod] += (dr - st + 1) * lazy[nod];
      if(st!=dr)
      {
        lazy[nod*2] += lazy[nod];
        lazy[nod*2+1] += lazy[nod];
      }
      lazy[nod]=0;
    }

  if(a<=st && b>=dr)
  {
    aint[nod] += (dr-st+1) * val;
    if(st!=dr)
    {
      lazy[nod*2] += val;
      lazy[nod*2+1] += val;
    }
    return;
  }

  int m = (st+dr)/2;
  lazyUpdate(2*nod, st, m, a, b, val);
  lazyUpdate(2*nod, m+1, dr, a, b, val);
  aint[nod] = aint[nod*2] + aint[2*nod+1];
}

int lazyQuery(int nod, int st, int dr, int a, int b)
{
  if(lazy[nod]!=0)
  {
    aint[nod] += (dr-st+1)*lazy[nod];
    if(st!=dr)
    {
      lazy[nod*2] += lazy[nod];
      lazy[nod*2+1] += lazy[nod];
    }
    lazy[nod]=0;
  }

  if(st>=a && b>=dr)
    return aint[nod];
  int m = (st+dr)/2, p1=p2=0;
  if(stq<=m)
    p1=lazyQuery(2*nod, st, m, stq, drq);
  if(drq>m)
    p2=lazyQuery(2*nod+1, m+1, dr, stq, drq);

  return p1+p2;
}

int main()
{
  citire();
  fin>>q;
  for(int i=0; i<q; i++)
  {
    int t, a, b, c;
    if(!t)
    {
      fin>>a>>b;
      lazyQuery(1, 1, n, a, b);
    }
    else
    {
      fin>>a>>b>>c;
      lazyUpdate(1, 1, n, a, b, c);
      cout<<res<<'\n';
      res=0;
    }


  }

  fin.close();
  return 0;
}