wa成屎了。。。还是没过！
-----------------------------
过了！！！各种bug啊。。。刚才又瞄了一眼，发现移位多写了一个1。我草。fuck!
题意：给出一个长度为n的整数序列D，你的任务是对m个询问做出回答。对于询问（a,b），需要找到两个下标x,和y，使得a<=x<=y<=b，并且Dx+Dx+1+....+Dy尽量大。如果有多组满足条件的x和y，x尽量小。如果还有多个解，y应该尽量小
分析：这个需要应用求最大连续子序列的分治算法：最优解要么完全在左半序列，要么完全在右半序列，要么跨越中点；
构造一颗线段树，其中每个结点维护3个值：区间最大连续和max_sub(a,b)，区间前缀最大连续和max_prefix(a,b)，区间后缀最大连续和max_suffix(a,b)
max_sub(a,b)=max(max_sub(a,m),max(max_sub(m+1,b),max_suffix(a,m)+max_preffix(m+1,b)));
max_preffix(a,b)=max(max_preffix(a,m),max_preffix(m+1,b)+sum[m]-sum[a-1]);
max_suffix(a,b)=max(max_suffix(m+1,b),max_suffix(a,m)+sum[b]-sum[m]);
// File Name: 1400.cpp // Author: zlbing // Created Time: 2013/3/12 11:54:33 #include<iostream> #include<string> #include<algorithm> #include<cstdlib> #include<cstdio> #include<set> #include<map> #include<vector> #include<cstring> #include<stack> #include<cmath> #include<queue> using namespace std; #define CL(x,v); memset(x,v,sizeof(x)); #define INF 0x3f3f3f3f #define LL long long #define REP(i,n) for(int i=0;i<n;i++) #define REP1(i,n) for(int i=1;i<n+1;i++) #define lson l , m , rt << 1 #define rson m + 1 , r , rt << 1 | 1 const int MAXN = 511111; LL sum[MAXN<<2]; LL Lsum[MAXN<<2]; LL Rsum[MAXN<<2]; int asum[MAXN<<2]; int bsum[MAXN<<2]; int bLsum[MAXN<<2]; int aLsum[MAXN<<2]; int aRsum[MAXN<<2]; int bRsum[MAXN<<2]; LL S[MAXN<<2]; struct node{ LL s; int a,b; }; void PushUp(int rt,int m) { sum[rt]=max(sum[rt<<1],max(sum[rt<<1|1],Rsum[rt<<1]+Lsum[rt<<1|1])); if(sum[rt]==sum[rt<<1]){ asum[rt]=asum[rt<<1]; bsum[rt]=bsum[rt<<1]; }else if(sum[rt]==Rsum[rt<<1]+Lsum[rt<<1|1]){ asum[rt]=aRsum[rt<<1]; bsum[rt]=bLsum[rt<<1|1]; }else if(sum[rt]==sum[rt<<1|1]){ asum[rt]=asum[rt<<1|1]; bsum[rt]=bsum[rt<<1|1]; } LL v1=S[bLsum[rt<<1]]-S[aLsum[rt<<1]-1]; LL v2=S[bLsum[rt<<1|1]]-S[aLsum[rt<<1]-1]; if(v1>=v2){ Lsum[rt]=v1; aLsum[rt]=aLsum[rt<<1]; bLsum[rt]=bLsum[rt<<1]; }else{ Lsum[rt]=v2; aLsum[rt]=aLsum[rt<<1]; bLsum[rt]=bLsum[rt<<1|1]; } v1=S[bRsum[rt<<1|1]]-S[aRsum[rt<<1|1]-1]; v2=S[bRsum[rt<<1|1]]-S[aRsum[rt<<1]-1]; if(v2>=v1){ Rsum[rt]=v2; aRsum[rt]=aRsum[rt<<1]; bRsum[rt]=bRsum[rt<<1|1]; }else{ Rsum[rt]=v1; aRsum[rt]=aRsum[rt<<1|1]; bRsum[rt]=bRsum[rt<<1|1]; } } void build(int l,int r,int rt) { if (l == r){ sum[rt]=Lsum[rt]=Rsum[rt]=S[l]-S[l-1]; asum[rt]=l; bsum[rt]=l; bLsum[rt]=l; aLsum[rt]=l; aRsum[rt]=l; bRsum[rt]=l; return ; } int m = (l + r) >> 1; build(lson); build(rson); PushUp(rt,r-l+1); } node query_prefix(int L,int R,int l,int r,int rt){ node t; if(bLsum[rt]<=R){ t.a=aLsum[rt]; t.b=bLsum[rt]; t.s=S[t.b]-S[t.a-1]; return t; } int m=(l+r)>>1; if(R<=m)return query_prefix(L,R,lson); t=query_prefix(L,R,rson); t.a=l; t.s=S[t.b]-S[t.a-1]; if(Lsum[rt<<1]>=t.s){ t.s=Lsum[rt<<1]; t.a=aLsum[rt<<1]; t.b=bLsum[rt<<1]; } return t; } node query_suffix(int L,int R,int l,int r,int rt){ node t; if(aRsum[rt]>=L){ t.a=aRsum[rt]; t.b=bRsum[rt]; t.s=S[t.b]-S[t.a-1]; return t; } int m=(l+r)>>1; if(L>m)return query_suffix(L,R,rson); t=query_suffix(L,R,lson); t.b=r; t.s=S[t.b]-S[t.a-1]; if(t.s<Rsum[rt<<1|1]){ t.s=Rsum[rt<<1|1]; t.a=aRsum[rt<<1|1]; t.b=bRsum[rt<<1|1]; } return t; } node query(int L,int R,int l,int r,int rt){ if(L<=l&&R>=r){ node temp; temp.a=asum[rt]; temp.b=bsum[rt]; temp.s=sum[rt]; return temp; } int m=(l+r)>>1; if(R<=m)return query(L,R,lson); if(L>m)return query(L,R,rson); node t1=query(L,R,lson); node t2=query(L,R,rson); node t=t1; if(t.s<t2.s)t=t2; t1=query_prefix(L,R,rson); t2=query_suffix(L,R,lson); t1.a=t2.a; t1.s+=t2.s; if(t1.s==t.s){ if(t.a>t1.a)t=t1; }else if(t1.s>t.s){ t=t1; } return t; } int main(){ int n,m; int cas=1; while(~scanf("%d%d",&n,&m)){ int a,b; S[0]=0; REP1(i,n){ scanf("%d",&a); S[i]=S[i-1]+a; } build(1,n,1); printf("Case %d:\n",cas++); REP(i,m){ scanf("%d%d",&a,&b); node ans=query(a,b,1,n,1); printf("%d %d\n",ans.a,ans.b); } } return 0; }
// LA3938 Ray, Pass me the dishes! // Rujia Liu 正确代码 #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn = 500000 + 10; const int maxnode = 1000000 + 10; typedef long long LL; typedef pair<int,int> Interval; LL prefix_sum[maxn]; LL sum(int L, int R) { return prefix_sum[R] - prefix_sum[L-1]; } LL sum(Interval p) { return sum(p.first, p.second); } Interval better(Interval a, Interval b) { if(sum(a) != sum(b)) return sum(a) > sum(b) ? a : b; return a < b ? a : b; // 利用pair自带的字典序 } int qL, qR; struct IntervalTree { int max_prefix[maxnode]; int max_suffix[maxnode]; Interval max_sub[maxnode]; void build(int o, int L, int R) { if(L == R) { max_prefix[o] = max_suffix[o] = L; max_sub[o] = make_pair(L, L); } else { int M = L + (R-L)/2; // 递归创建子树 int lc = o*2, rc = o*2+1; build(lc, L, M); build(rc, M+1, R); // 递推max_prefix LL v1 = sum(L, max_prefix[lc]); LL v2 = sum(L, max_prefix[rc]); if(v1 == v2) max_prefix[o] = min(max_prefix[lc], max_prefix[rc]); else max_prefix[o] = v1 > v2 ? max_prefix[lc] : max_prefix[rc]; // 递推max_suffix v1 = sum(max_suffix[lc], R); v2 = sum(max_suffix[rc], R); if(v1 == v2) max_suffix[o] = min(max_suffix[lc], max_suffix[rc]); else max_suffix[o] = v1 > v2 ? max_suffix[lc] : max_suffix[rc]; // 递推max_sub max_sub[o] = better(max_sub[lc], max_sub[rc]); // 完全在左子树或者右子树 max_sub[o] = better(max_sub[o], make_pair(max_suffix[lc], max_prefix[rc])); // 跨越中线 } } Interval query_prefix(int o, int L, int R) { if(max_prefix[o] <= qR) return make_pair(L, max_prefix[o]); int M = L + (R-L)/2; int lc = o*2, rc = o*2+1; if(qR <= M) return query_prefix(lc, L, M); Interval i = query_prefix(rc, M+1, R); i.first = L; return better(i, make_pair(L, max_prefix[lc])); } Interval query_suffix(int o, int L, int R) { if(max_suffix[o] >= qL) return make_pair(max_suffix[o], R); int M = L + (R-L)/2; int lc = o*2, rc = o*2+1; if(qL > M) return query_suffix(rc, M+1, R); Interval i = query_suffix(lc, L, M); i.second = R; return better(i, make_pair(max_suffix[rc], R)); } Interval query(int o, int L, int R) { if(qL <= L && R <= qR) return max_sub[o]; int M = L + (R-L)/2; int lc = o*2, rc = o*2+1; if(qR <= M) return query(lc, L, M); if(qL > M) return query(rc, M+1, R); Interval i1 = query_prefix(rc, M+1, R); // 右半的前缀 Interval i2 = query_suffix(lc, L, M); // 左半的后缀 Interval i3 = better(query(lc, L, M), query(rc, M+1, R)); return better(make_pair(i2.first, i1.second), i3); } }; IntervalTree tree; int main() { int kase = 0, n, a, Q; while(scanf("%d%d", &n, &Q) == 2) { prefix_sum[0] = 0; for(int i = 0; i < n; i++) { scanf("%d", &a); prefix_sum[i+1] = prefix_sum[i] + a; } tree.build(1, 1, n); printf("Case %d:\n", ++kase); while(Q--) { int L, R; scanf("%d%d", &L, &R); qL = L; qR = R; Interval ans = tree.query(1, 1, n); printf("%d %d\n", ans.first, ans.second); } } return 0; }