PAT1046

题目链接：http://pat.zju.edu.cn/contests/pat-a-practise/1046

用普通方法累加最后一个case会超时，因为要求区间的总值，用树状数组即可！

 1 #include<cstdio>
 2 #include<vector>
 3 using namespace std;
 4 
 5 /*树状数组*/
 6 vector<int> c;
 7 vector<int> v;
 8 
 9 int lowint(int t){
10     return t&(t^(t-1));
11 }
12 
13 void add(int pos, int num){
14     while(pos < c.size()){
15         c[pos]+=num;
16         pos+=lowint(pos);
17     }
18 }
19 
20 int sum(int pos){
21     int sum(0);
22     while(pos > 0){
23         sum+=c[pos];
24         pos-=lowint(pos);
25     }
26     return sum;
27 }
28 
29 int main(){
30     int N;scanf("%d", &N);
31     int total_dis(0);
32     c.resize(N+1);
33     v.resize(N+1);
34     for(int i=1; i<N+1; ++i){
35         int in; scanf("%d", &in);
36         total_dis+=in;
37         add(i, in);
38         v[i]=in;
39     }
40     int M; scanf("%d", &M);
41     for(int i=0; i<M; ++i){
42         int a,b; scanf("%d%d", &a,&b);
43         if(a > b){
44             int c = a;a= b;b=c;
45         }
46         int dis = sum(b)-v[b]-(sum(a)-v[a]);
47         int dis2= total_dis-dis;
48         printf("%d
", dis > dis2 ? dis2: dis);
49     }
50     return 0;
51 }