nyoj228 士兵殺敵（五）（區間更新，區間查詢）

士兵殺敵（五）

描述

南將軍麾下有百萬精兵，現已知共有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

好機智的一道題 看了別人的題解 看了好久才理解

 

就是在更新的時候 用一個數組維護 比如要在【a,b】之間增加x,那麼就讓count[a]+=x,count[b+1]-=x。最後更新完以後

 

	for(int i=1;i<=max;i++)
	{
		count[i]=count[i]+count[i-1];
	//	sum[i]=(sum[i-1]+count[i])%mod;
	}

使用這個for循環 就能把更新的總人數 准確得得出 慢慢理解 哈哈

#include 
#include 
#define N 1000000+10
#define mod 10003
int count[N];
int sum[N];
int main()
{
	int n,c,q;
	memset(count,0,sizeof(count));
	memset(sum,0,sizeof(sum));
	scanf("%d %d %d",&n,&c,&q);
	int max=0;
	for(int i=0;imax)
		max=b;
	}
	sum[0]=count[0];
	for(int i=1;i<=max;i++)
	{
		count[i]=count[i]+count[i-1];
		sum[i]=(sum[i-1]+count[i])%mod;
	}
	for(int i=0;i