NYOJ228 士兵杀敌（五）

士兵杀敌（五）

时间限制：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取余后输出

样例输入

样例输出

19
6

  1 /*
  2 //代码一：------超时--试着用线段树 （题目还要求士兵号从0开始，这个代码是从1开始的）
  3 #include<stdio.h>
  4 #include<malloc.h>
  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<s)     
 27         return ;
 28     else if(s<tree[T].lc&&t<=tree[T].rc)
 29         tree[T].sum+=add*(t-tree[T].lc+1);
 30     else if(s>=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].lc||s>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<t1;++i)
 65     {
 66             scanf("%d%d%d",&st,&end,&k);
 67             insert(st,end,k,1);
 68     }
 69     for(i=0;i<t2;++i)
 70     {
 71         scanf("%d%d",&st,&end);
 72         printf("%d\n",qurry(st,end,1)%10003);      //输出st到end个人的军工
 73     }
 74     return 0;
 75 }
 76 */
 77 
 78 //代码二：----不知道为啥改成动态分配数组就错了
 79 /*
 80 题目解析：
 81     是一道妙用数组的题，由于问题都是在更新完所有以后问的，所以刚开始时可以不用更新，
 82     记录下来需要更新的，当输入完后再一次更新，求出每个点的值，之后再求出前n项和就可以了
 83 通过这道题我越发的发现搞程序、写算法的人真是太牛逼了，各种算法，各种牛叉，叫我们这些菜鸟情何以堪。。。。。。。
 84 */
 85 #include<stdio.h>
 86 #include<malloc.h>
 87 #include<string.h>
 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 }

功不成，身已退