士兵杀敌（五）

时间限制：

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 21 3 22 4 15 5 101 52 3

样例输出

196

1 /*  2 //代码一：------超时--试着用线段树 （题目还要求士兵号从0开始，这个代码是从1开始的）  3 #include
       
          4 #include
        
           5   6 struct node  7 {  8     int lc,rc;  9     long long sum; 10 }*tree; 11  12 void build(int s,int t,int T) 13 { 14     int mid=(s+t)>>1; 15     tree[T].lc=s; 16     tree[T].rc=t; 17     tree[T].sum=0; 18     if(s==t) 19         return ; 20     build(s,mid,T<<1); 21     build(mid+1,t,(T<<1)|1); 22 } 23  24 void insert(int s,int t,int add,int T)  //线段树插入还是不会写，网上说的都是用lazy思想找到正好匹配的节点就不用往下更新了， 25 {                                        //但是自己还是不会写，还是全部更新一遍,------有待学习 26     if(tree[T].lc>t||tree[T].rc
         
          =tree[T].lc&&t<=tree[T].rc) 31         tree[T].sum+=add*(t-s+1); 32     else if(s>=tree[T].lc&&t>tree[T].rc) 33         tree[T].sum+=add*(tree[T].rc-s+1); 34     else  35         tree[T].sum+=add*(tree[T].rc-tree[T].lc+1); 36     if(tree[T].lc==tree[T].rc) 37         return ; 38     insert(s,t,add,T<<1); 39     insert(s,t,add,(T<<1)|1); 40 } 41  42 long long qurry(int s,int t,int T) 43 { 44     int mid=(tree[T].lc+tree[T].rc)>>1; 45     if(t
          
           tree[T].rc)  //不在此范围内直接跳出 46         return 0; 47     if(tree[T].lc==s&&tree[T].rc==t) 48         return tree[T].sum; 49     if(t<=mid) 50         return qurry(s,t,T<<1); 51     else if(s>mid) 52         return qurry(s,t,(T<<1)|1); 53     else 54         return qurry(s,mid,T<<1)+qurry(mid+1,t,(T<<1)|1); 55 } 56  57 int main() 58 { 59     int t1,t2,st,end,k,i,n; 60     char cmd[10]; 61     scanf("%d%d%d",&n,&t1,&t2); 62     tree=(struct node *)malloc(n*3*sizeof(struct node)); 63     build(1,n,1); 64     for(i=0;i
           
             86 #include
            
              87 #include
             
               88 int p[1000003]; 89 //int *p; 90 int main() 91 { 92 int n,m,k,s,t,i,add; 93 scanf("%d%d%d",&n,&m,&k); 94 // p=(int *)malloc((n+2)*sizeof(int)); 95 // memset(p,0,(n+2)*sizeof(int)); 96 while(m--) 97 { 98 scanf("%d%d%d",&s,&t,&add); 99 p[s]+=add;100 p[t+1]-=add;101 }102 for(i=1;i<=n;++i) //算出来每个士兵杀敌的人数103 p[i]+=p[i-1];104 for(i=1;i<=n;++i) //将数组改存为前i个人杀敌的总人数105 p[i]=(p[i-1]+p[i])%10003;106 while(k--)107 {108 scanf("%d%d",&s,&t);109 printf("%d\n",(p[t]-p[s-1]+10003)%10003);110 }111 // system("pause");112 return 0;113 }