uva 1400

又是一道线段树区间更新的题；
  1 #include<cstdio>
  2 #include<algorithm>
  3 #include<cstring>
  4 #define ll long long
  5 #define maxn 500005
  6 using namespace std;
  7 ll sum[maxn];
  8 struct tree
  9 {
 10     int l,r;
 11     int ml,mr;
 12     int pre,suf;
 13     tree *left,*right;
 14 } tr[maxn*2];
 15 
 16 int trcount;
 17 
 18 void build(tree *root,int l,int r)
 19 {
 20     root->l=l;
 21     root->r=r;
 22     if(l==r)
 23     {
 24         root->ml=l;
 25         root->mr=r;
 26         root->pre=l;
 27         root->suf=r;
 28         return;
 29     }
 30     trcount++;
 31     root->left=tr+trcount;
 32     trcount++;
 33     root->right=tr+trcount;
 34     int mid=(l+r)/2;
 35     build(root->left,l,mid);
 36     build(root->right,mid+1,r);
 37 
 38     //update the pre
 39     if((sum[root->left->pre]-sum[root->l-1])>=(sum[root->right->pre]-sum[root->l-1]))
 40         root->pre=root->left->pre;
 41     else root->pre=root->right->pre;
 42     //update the suf
 43     if((sum[root->r]-sum[root->left->suf-1])>=(sum[root->r]-sum[root->right->suf-1]))
 44         root->suf=root->left->suf;
 45     else root->suf=root->right->suf;
 46     //update the max
 47     if((sum[root->left->mr]-sum[root->left->ml-1])>=(sum[root->right->mr]-sum[root->right->ml-1]))
 48     {
 49         root->ml=root->left->ml;
 50         root->mr=root->left->mr;
 51     }
 52     else
 53     {
 54         root->mr=root->right->mr;
 55         root->ml=root->right->ml;
 56     }
 57     //update the max
 58     if((sum[root->mr]-sum[root->ml-1])<(sum[root->right->pre]-sum[root->left->suf-1]))
 59     {
 60         root->mr=root->right->pre;
 61         root->ml=root->left->suf;
 62     }
 63     else if((sum[root->mr]-sum[root->ml-1])==(sum[root->right->pre]-sum[root->left->suf-1]))
 64     {
 65         if(root->left->suf<root->ml||(root->left->suf==root->ml&&root->right->pre<root->mr))
 66         {
 67             root->mr=root->right->pre;
 68             root->ml=root->left->suf;
 69         }
 70     }
 71 }
 72 
 73 void query(tree *root,int ql,int qr,int &x,int &y,int &ansl,int &ansr)
 74 {
 75     if((ql<=root->l)&&(root->r<=qr))
 76     {
 77         x=root->ml;
 78         y=root->mr;
 79         ansl=root->pre;
 80         ansr=root->suf;
 81         return;
 82     }
 83     int mid=(root->r+root->l)>>1;
 84     if(qr<=mid)query(root->left,ql,qr,x,y,ansl,ansr);
 85     else if(ql>=mid+1)query(root->right,ql,qr,x,y,ansl,ansr);
 86     else
 87     {
 88         int x1,x2,y1,y2,pre1,pre2,suf1,suf2;
 89 
 90         query(root->left,ql,mid,x1,y1,pre1,suf1);
 91         query(root->right,mid+1,qr,x2,y2,pre2,suf2);
 92 
 93         ansl=(sum[pre1]-sum[root->l-1])>=(sum[pre2]-sum[root->l-1])?pre1:pre2;
 94         ansr=(sum[root->r]-sum[suf1-1])>=(sum[root->r]-sum[suf2-1])?suf1:suf2;
 95 
 96         if((sum[y1]-sum[x1-1])>=(sum[y2]-sum[x2-1]))
 97         {
 98             x= x1;
 99             y= y1;
100         }
101         else
102         {
103             x= x2;
104             y= y2;
105         }
106         if((sum[pre2]-sum[suf1-1])>(sum[y]-sum[x-1]))
107         {
108             x= suf1;
109             y= pre2;
110         }
111         else if((sum[pre2]-sum[suf1-1])==(sum[y]-sum[x-1]))
112         {
113             if((suf1<x)||((suf1==x)&&(pre2<y)))
114             {
115                 x = suf1;
116                 y = pre2;
117             }
118         }
119     }
120 }
121 
122 
123 int main()
124 {
125     int n,q,ca=1;
126     while(scanf("%d%d",&n,&q)!=EOF)
127     {
128         ll x;
129         trcount=0;
130         memset(sum,0,sizeof sum);
131         for(int i=1; i<=n; i++)
132         {
133             scanf("%lld",&x);
134             sum[i]=sum[i-1]+x;
135         }
136         build(tr,1,n);
137         int a,b,ans1,ans2,xx,yy;
138         printf("Case %d:
",ca++);
139         while(q--)
140         {
141             scanf("%d%d",&a,&b);
142             query(tr,a,b,xx,yy,ans1,ans2);
143             printf("%d %d
",xx,yy);
144         }
145     }
146     return 0;
147 }
View Code