3.2 区间信息的维护与查询

  1 //#define txtout
  2 //#define debug
  3 #include<bits/stdc++.h>
  4 #define mt(a,b) memset(a,b,sizeof(a))
  5 using namespace std;
  6 typedef long long LL;
  7 const double pi=acos(-1.0);
  8 const double eps=1e-8;
  9 const int inf=0x3f3f3f3f;
 10 const int M=5e5+10;
 11 typedef pair<int,int> pii;
 12 LL sum[M];
 13 class SegmentTree{
 14     #define lrrt int L,int R,int rt
 15     #define iall 1,n,1
 16     #define imid int mid=(L+R)>>1
 17     #define lson L,mid,rt<<1
 18     #define rson mid+1,R,rt<<1|1
 19     static const int MV=5e5+10;
 20     struct T{
 21         int Start,End,leftEnd,rightStart;
 22     }tree[MV<<2];
 23     int n;
 24     pii getBest(pii a,pii b){
 25         LL sa=sum[a.second]-sum[a.first-1];
 26         LL sb=sum[b.second]-sum[b.first-1];
 27         if(sa>sb) return a;
 28         if(sa<sb) return b;
 29         if(a.first<b.first) return a;
 30         if(a.first>b.first) return b;
 31         if(a.second<b.second) return a;
 32         return b;
 33     }
 34     T combine(int L,int R,T l,T r){
 35         pii a=make_pair(l.Start,l.End);
 36         pii b=make_pair(r.Start,r.End);
 37         pii c=make_pair(l.rightStart,r.leftEnd);
 38         a=getBest(a,b);
 39         a=getBest(a,c);
 40         T result;
 41         result.Start=a.first;
 42         result.End=a.second;
 43         a=make_pair(L,l.leftEnd);
 44         b=make_pair(L,r.leftEnd);
 45         result.leftEnd=getBest(a,b).second;
 46         a=make_pair(l.rightStart,R);
 47         b=make_pair(r.rightStart,R);
 48         result.rightStart=getBest(a,b).first;
 49         return result;
 50     }
 51     void pushup(lrrt){
 52         tree[rt]=combine(L,R,tree[rt<<1],tree[rt<<1|1]);
 53     }
 54     void build(lrrt){
 55         if(L==R){
 56             tree[rt].Start=L;
 57             tree[rt].End=L;
 58             tree[rt].leftEnd=L;
 59             tree[rt].rightStart=L;
 60             return ;
 61         }
 62         imid;
 63         build(lson);
 64         build(rson);
 65         pushup(L,R,rt);
 66     }
 67     T query(int x,int y,lrrt){
 68         if(x<=L&&R<=y) return tree[rt];
 69         T a,b;
 70         bool f1=false,f2=false;
 71         imid;
 72         if(mid>=x){
 73             a=query(x,y,lson);
 74             f1=true;
 75         }
 76         if(mid<y){
 77             b=query(x,y,rson);
 78             f2=true;
 79         }
 80         if(!f1) return b;
 81         if(!f2) return a;
 82         return combine(x,y,a,b);
 83     }
 84 public:
 85     void init(int tn){
 86         n=tn;
 87         build(iall);
 88     }
 89     pii query(int x,int y){
 90         T result=query(x,y,iall);
 91         return make_pair(result.Start,result.End);
 92     }
 93 }st;
 94 int n,m;
 95 int a[M];
 96 struct Q{
 97     int x,y;
 98     pii answer;
 99 }q[M];
100 void init_sum(){
101     sum[0]=0;
102     for(int i=1;i<=n;i++){
103         sum[i]=sum[i-1]+a[i];
104     }
105 }
106 void solve(){
107     init_sum();
108     st.init(n);
109     for(int i=0;i<m;i++){
110         q[i].answer=st.query(q[i].x,q[i].y);
111     }
112 }
113 int main(){
114     #ifdef txtout
115     freopen("in.txt","r",stdin);
116     freopen("out.txt","w",stdout);
117     #endif // txtout
118     int cas=1;
119     while(~scanf("%d%d",&n,&m)){
120         for(int i=1;i<=n;i++){
121             scanf("%d",&a[i]);
122         }
123         for(int i=0;i<m;i++){
124             scanf("%d%d",&q[i].x,&q[i].y);
125         }
126         solve();
127         printf("Case %d:
",cas++);
128         for(int i=0;i<m;i++){
129             printf("%d %d
",q[i].answer.first,q[i].answer.second);
130         }
131     }
132     return 0;
133 }