1   2 #include <bits/stdc++.h> 3  4 using namespace std; 5  6 int a[1000005]; 7 int sum[1000005]; 8  9 int main()10 {11     int n,m;12     scanf("%d%d",&n,&m);13 14     sum[0] = 0;15     for(int i=1;i<=n;i++) {16         scanf("%d",&a[i]);17         sum[i] = sum[i-1] + a[i];18     }19 20     while(m--) {21         int m,n;22         scanf("%d%d",&m,&n);23         if(m>n)24             swap(m,n);25         printf("%d\n",sum[n]-sum[m-1]);26 27     }28 29     return 0;30 }31         

 1   2 #include <bits/stdc++.h> 3  4 using namespace std; 5  6 const int maxn = 1000000+5; 7  8 int C[maxn]; 9 int n,m;10 11 12 int lowbit(int x) {13     return x&-x;14 }15 16 //A[1] + A[2] + ... + A[x]17 int sum(int x) {18     int ret = 0;19     while(x>0) {20         ret +=C[x];21         x-=lowbit(x);22     }23     return ret;24 }25 26 //A[x] +=d;27 void add(int x,int d) {28     while(x<=n) {29         C[x] +=d;30         x+=lowbit(x);31     }32 }33 34 int main()35 {36     scanf("%d%d",&n,&m);37     for(int i=1;i<=n;i++) {38         int x;39         scanf("%d",&x);40         add(i,x);41     }42 43     char cmd[10];44     for(int i=0;i<m;i++) {45         scanf("%s",cmd);46         if(cmd[0]==‘A‘)47         {48             int x,d;49             scanf("%d%d",&x,&d);50             add(x,d);51         }52         else {53             int u,v;54             scanf("%d%d",&u,&v);55             printf("%d\n",sum(v)-sum(u-1));56         }57     }58 59     return 0;60 }61         

 1   2 #include <bits/stdc++.h> 3  4 using namespace std; 5  6 const int maxn = 100005; 7  8 struct RMQ { 9 10     int dmin[maxn][20];11     int dmax[maxn][20];12 13     void RMQ_init(const vector<int>& A) {14         int n = A.size();15         for(int i=0;i<n;i++)16         {17             dmin[i][0] = A[i];18             dmax[i][0] = A[i];19         }20 21         for(int j=1;(1<<j)<=n;j++) {22             for(int i=0;i+(1<<j)-1<n;i++) {23                 dmin[i][j] = min(dmin[i][j-1],dmin[i+(1<<(j-1))][j-1]);24                 dmax[i][j] = max(dmax[i][j-1],dmax[i+(1<<(j-1))][j-1]);25             }26         }27     }28 29     int RMQ_min(int L,int R) {30         int k = 0;31         while((1<<(k+1))<=R-L+1)32             k++;33         return min(dmin[L][k],dmin[R-(1<<k)+1][k]);34     }35 36     int RMQ_max(int L,int R) {37         int k = 0;38         while((1<<(k+1))<=R-L+1)39             k++;40         int ans = max(dmax[L][k],dmax[R-(1<<k)+1][k]);41         return ans;42     }43 44 45 }sol;46 47 int main()48 {49     int n,m;50     scanf("%d%d",&n,&m);51     vector<int> v;52     for(int i=0;i<n;i++) {53         int x;54         scanf("%d",&x);55         v.push_back(x);56     }57     sol.RMQ_init(v);58 59     for(int i=0;i<m;i++) {60         int l,r;61         scanf("%d%d",&l,&r);62         l--;r--;63         printf("%d\n",sol.RMQ_max(l,r)-sol.RMQ_min(l,r));64     }65 66     return 0;67 }68         

 1   2 #include <bits/stdc++.h> 3  4 using namespace std; 5  6 const int maxn = 1000000+5; 7 int C[maxn]; 8 int m,t; 9 int lowbit(int x)10 {11     return x&-x;12 }13 14 void add(int star,int num) {15     while(star>0) {16         C[star]+=num;17         star-=lowbit(star);18     }19 }20 21 int sum(int star) {22     int sum = 0;23     while(star<=m) {24         sum+=C[star];25         star+=lowbit(star);26     }27     return sum;28 }29 30 int main()31 {32     scanf("%d%d",&t,&m);33     while(t--) {34         char cmd[10];35         scanf("%s",cmd);36         if(cmd[0]==‘A‘) {37             int u,v,c;38             scanf("%d%d%d",&u,&v,&c);39             add(v,c);40             add(u-1,-c);41         }42         else {43             int pos;44             scanf("%d",&pos);45             printf("%d\n",sum(pos));46         }47     }48 49     return 0;50 }51         

  1 /*  2 #include <bits/stdc++.h>  3   4 using namespace std;  5   6 const int maxnode = 1000001<<2;  7 int _min,_max,_sum;  8 int qL,qR,v;  9  10 struct IntervalTree 11 { 12     int sumv[maxnode], minv[maxnode], maxv[maxnode], addv[maxnode]; 13     void maintain(int o, int L, int R) 14     { 15         int lc = o*2, rc = o*2+1; 16         sumv[o] = minv[o] = maxv[o] = 0; 17         if(R > L) 18         { 19             sumv[o] = sumv[lc] + sumv[rc]; 20             minv[o] = min(minv[lc], minv[rc]); 21             maxv[o] = max(maxv[lc], maxv[rc]); 22         } 23         if(addv[o]) 24         { 25             minv[o] += addv[o]; 26             maxv[o] += addv[o]; 27             sumv[o] += addv[o] * (R-L+1); 28         } 29     } 30  31     void update(int o, int L, int R) 32     { 33         int lc = o*2, rc = o*2+1; 34         if(qL <= L && qR >= R) 35         { 36             addv[o] += v; 37         } 38         else 39         { 40             int M = L + (R-L)/2; 41             if(qL <= M) update(lc, L, M); 42             if(qR > M) update(rc, M+1, R); 43         } 44         maintain(o, L, R); 45     } 46  47     void query(int o, int L, int R, int add) 48     { 49         if(qL <= L && qR >= R) 50         { 51             _sum += (sumv[o] + add * (R-L+1))%10003; 52             _min = min(_min, minv[o] + add); 53             _max = max(_max, maxv[o] + add); 54         } 55         else 56         { 57             int M = L + (R-L)/2; 58             if(qL <= M) query(o*2, L, M, add + addv[o]); 59             if(qR > M) query(o*2+1, M+1, R, add + addv[o]); 60         } 61     } 62  63 }tree; 64  65 int main() 66 { 67     int n,c,q; 68     scanf("%d%d%d",&n,&c,&q); 69     while(c--) { 70         scanf("%d%d%d",&qL,&qR,&v); 71         tree.update(1,1,n); 72     } 73  74     while(q--) { 75         _sum = 0; 76         scanf("%d%d",&qL,&qR); 77         tree.query(1,1,n,0); 78         printf("%d\n",_sum); 79     } 80  81     return 0; 82 } 83 */ 84  85 #include <bits/stdc++.h> 86  87 using namespace std; 88  89 const int maxn = 1000005; 90 int num[maxn]; 91  92 int main() 93 { 94     int n,c,q; 95     memset(num,0,sizeof(num)); 96     scanf("%d%d%d",&n,&c,&q); 97     for(int i=0;i<c;i++) { 98         int l,r,v; 99         scanf("%d%d%d",&l,&r,&v);100         num[l]+=v;101         num[r+1]-=v;102     }103 104     for(int i=1;i<=n;i++) {105         num[i]+=num[i-1];106     }107 108     for(int i=1;i<=n;i++) {109         num[i]=(num[i]+num[i-1])%10003;110     }111     while(q--) {112         int l,r;113         scanf("%d%d",&l,&r);114         printf("%d\n",(num[r]-num[l-1]+10003)%10003);115     }116 117     return 0;118 }