Cod sursa(job #434)

Utilizator gigi_becaliGigi Becali gigi_becali Data 11 decembrie 2006 11:28:43
Problema Datorii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
#include <cstdio>
#define maxn 1<<20
#define bit(i)  (((i) & ((i)-1))  ^ (i))
int s[maxn];
int n;
void update(int x, int val, int sgn)

{
	for(;x<=n;x+=bit(x))s[x]+=val*sgn;

}

int query(int x)
{
int sum=0;
for(;x>0;x-=bit(x)) sum+=s[x];
return sum;
}

int main()
{
	int  m;
	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(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(c)-query(b-1));
		else update(b, c, -1);
}
return 0;
}