Cod sursa(job #439)

Utilizator gigi_becaliGigi Becali gigi_becali Data 11 decembrie 2006 11:40:13
Problema Datorii Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <cstdio>
#define maxn 1<<15

int s[maxn], n, m;

void update(int n, int l, int r, int p, int val, int sgn)
{
  s[n]+=val*sgn;
  if(l==r) return ;

  int m=(l+r)>>1;
  if(p<=m) update(n<<1, l, m, p, val, sgn);
  else update((n<<1)|1, m+1, r, p, val, sgn);
}

int query(int n, int l, int r, int a, int b)
{
  if(a<=l && r<=b) return s[n];
  
  int m=(l+r)>>1, sum=0;
  if(a<=m) sum+=query(n<<1, l, m, a, b);
  if(b>m) sum+=query((n<<1)|1, m+1, r, a, b);
  return sum;
}

int main()
{
  freopen("datorii.in", "r", stdin);
  freopen("datorii.out", "w", stdout);
  scanf("%d %d\n", &n, &m);
  int i, p;
  for(i=1;i<=n;i++){ scanf("%d ", &p); update(1, 1, 32000, i, p, 1);}

  for(i=1;i<=m;i++) 
    {
      int a, b, c;
      scanf("%d %d %d\n", &a, &b, &c);
      if(a==1) printf("%d\n", query(1, 1, 17000, b, c));
      else update(1, 1, 17000, b, c, -1);
    }
  return 0;
}