士兵杀敌（五） 树状数组，线段树，标记数组（变区间，问区间）

连接：http://acm.nyist.net/JudgeOnline/problem.php?pid=228

士兵杀敌（五）

时间限制：2000 ms  |  内存限制：65535 KB

难度：5

 

描述

南将军麾下有百万精兵，现已知共有M个士兵，编号为0~M，每次有任务的时候，总会有一批编号连在一起人请战（编号相近的人经常在一块，相互之间比较熟悉），最终他们获得的军功，也将会平分到每个人身上，这样，有时候，计算他们中的哪一个人到底有多少军功就是一个比较困难的事情。

 

在这样的情况下，南将军却经常会在许多次战役之后询问军师小工第i号士兵到第j号士兵所有人的总军功数。

请你帮助军师小工回答南将军的提问。

 

 

输入

只有一组测试数据
第一行是三个整数N,C,Q(1<=N,C,Q<=1000000)，其中N表示士兵的总数。
随后的C行，每行有三个整数Mi,Ni,Ai(0<=Mi<=Ni<=N,0<=Ai<=100)，表示从第Mi号到第Ni号士兵所有人平均增加了Ai的军功。
再之后的Q行，每行有两个正正数m,n，表示南将军询问的是第m号士兵到第n号士兵。

输出

请对每次询问输出m号士兵到第n号士兵的总军功数，由于该数值可能太大，请把结果对10003取余后输出

样例输入

5 3 2
1 3 2
2 4 1
5 5 10
1 5
2 3

样例输出

19
6

 

 

#include<stdio.h>
int bing[1000010];
int MAX;
void add(int a,int b,int c)
{
	int n;
	n=a-1;
	while(n>0)
	{
		bing[n]-=c;
		n-=(n&(-n));
	}
	n=b;
	while(n>0)
	{
		bing[n]+=c;
		n-=(n&(-n));
	}
}
int chazhao(int a,int b)
{
	int totle=0,i,n,term;
	for(i=a;i<=b;i++)
	{
		n=0;term=i;
		while(term<MAX)
		{
			n+=bing[term];
			term+=(term&(-term));
		}
		totle+=n;
	}
	return(totle);
}
int main()
{
	int cc,q;
	int a,b,c;
	scanf("%d%d%d",&MAX,&cc,&q);
	while(cc--)
	{
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c);
	}
	while(q--)
	{
		scanf("%d%d",&a,&b);
		printf("%d\n",chazhao(a,b)%10003);
	}
	return(0);
}

 

 

 

#include<stdio.h>
struct Bing
{
	int l;
	int r;
	int date;
}bing[3*1000000];
void build(int a,int b,int n=1)
{
	bing[n].l=a;
	bing[n].r=b;
	bing[n].date=0;
	if(a==b)return;
	int zhong=(a+b)>>1;
	build(a,zhong,2*n);
	build(zhong+1,b,2*n+1);
}
void add(int a,int b,int c,int n=1)
{
	int zhong;
	if(bing[n].l==a&&bing[n].r==b)
	{
		bing[n].date+=c;
		return;
	}
	else
	{
		zhong=(bing[n].l+bing[n].r)>>1;
		if(b<=zhong)add(a,b,c,2*n);
		else if(a>zhong)add(a,b,c,2*n+1);
		else
		{
			add(a,zhong,c,2*n);
			add(zhong+1,b,c,2*n+1);
		}
	}
}
void find(int a,int b,int &c,int n=1)
{
	if(n==1)c=0;
	c+=bing[n].date*(b-a+1);
	if(bing[n].l==bing[n].r)return;
	int zhong=(bing[n].l+bing[n].r)>>1;
	if(b<=zhong)find(a,b,c,2*n);
	else if(a>zhong)find(a,b,c,2*n+1);
	else
	{
		find(a,zhong,c,2*n);
		find(zhong+1,b,c,2*n+1);
	}
}
int main()
{
	int aa,bb,cc;
	int n,c,q;
	scanf("%d%d%d",&n,&c,&q);
	build(1,n+1,1);
	while(c--)
	{
		scanf("%d%d%d",&aa,&bb,&cc);
		add(aa+1,bb+1,cc);
	}
	while(q--)
	{
		scanf("%d%d",&aa,&bb);
		find(aa+1,bb+1,cc);
		printf("%d\n",cc%10003);
	}
	return(0);
}

 

 

#include<stdio.h>
int p[1000010];
int main()
{
	int n,c,q;
	int a,b,cc;
	int i;
	scanf("%d%d%d",&n,&c,&q);
	while(c--)
	{
		scanf("%d%d%d",&a,&b,&cc);
		p[a]+=cc;
		p[b+1]-=cc;
	}
	for(i=1;i<=n;i++)
		p[i]+=p[i-1];
	for(i=1;i<=n;i++)
		p[i]=(p[i-1]+p[i])%10003;
	while(q--)
	{
		scanf("%d%d",&a,&b);
		printf("%d\n",(p[b]-p[a-1]+10003)%10003);
	}
	return(0);
}