1 线段树回答区间最大字段和
对前缀和序列用线段树做RMQ
#include <iostream> #include <cstring> #include <cstdio> using namespace std; /** * 待处理序列A从1到N * min对应的序列是前缀和序列右移一位 */ const int MaxN = 500000; #define left first #define right second long long A[MaxN]; struct Range:pair<int,int>{ Range(int a=0,int b=0){ left = a; right = b; } long long sum() const { return A[right]-A[left-1]; } bool operator < (const Range& rig) const { if(sum()<rig.sum()) return 1; if(sum()>rig.sum()) return 0; if(left >rig.left) return 1; if(left <rig.left) return 0; if(right>rig.right) return 1; if(right<rig.right) return 0; return 1; } }; Range max(Range A,Range B){ return A < B ? B : A; } struct node { Range range; int maxPos,minPos; node(int x=0){range.left=range.right=maxPos=minPos=x;} long max(){return A[maxPos];} long min(){return A[minPos-1];} }; struct SegmentTree { #define MaxSegmentLength 500000 const int root; SegmentTree():root(1){} node data[4*MaxSegmentLength]; void newNode(int p,int x){data[p]=node(x);} void maintain(int p){ int lch= p*2,rch= p*2+1,t=0; data[p].range = max(data[rch].range,data[lch].range); Range MRange(data[lch].minPos,data[rch].maxPos); data[p].range = max(MRange,data[p].range); data[p].maxPos = (data[lch].max()>=data[rch].max())? data[lch].maxPos: data[rch].maxPos; data[p].minPos = (data[lch].min()<=data[rch].min())? data[lch].minPos: data[rch].minPos; } void build(int x,int y,int p){ if (x==y) newNode(p,x); else { int mid=(x+y)/2; build(x ,mid,p*2 ); build(mid+1,y ,p*2+1); maintain(p); } } int queryMax(int x,int y,int l,int r,int p) { //cout<<"QueryMax ("<<x<<','<<y<<") ["<<l<<','<<r<<"] @"<<p<<endl; if (x==l && y==r) return data[p].maxPos; int mid = (l+r)/2,LPos,RPos; //cout<<" "<<l<<','<<mid<<'|'<<mid+1<<','<<r<<endl; if (y<=mid) return queryMax(x,y,l ,mid,p*2 ); if (x >mid) return queryMax(x,y,mid+1,r ,p*2+1); LPos=queryMax(x ,mid,l ,mid,p*2); RPos=queryMax(mid+1,y ,mid+1,r ,p*2+1); //cout<<" max(L,R)"<<LPos<<' '<<RPos<<endl; return A[LPos]>=A[RPos] ? LPos : RPos; } int queryMin(int x,int y,int l,int r,int p) { //cout<<"QueryMin ("<<x<<','<<y<<") ["<<l<<','<<r<<"] @"<<p<<endl; if (x==l && y==r) return data[p].minPos; int mid = (l+r)/2,LPos,RPos; //cout<<" "<<l<<','<<mid<<'|'<<mid+1<<','<<r<<endl; if (y<=mid) return queryMin(x,y,l ,mid,p*2 ); if (x >mid) return queryMin(x,y,mid+1,r ,p*2+1); LPos=queryMin(x ,mid,l ,mid,p*2); RPos=queryMin(mid+1,y ,mid+1,r ,p*2+1); //cout<<" min(L,R)"<<LPos<<' '<<RPos<<endl; return A[LPos-1]<=A[RPos-1] ? LPos : RPos; } Range query(int x,int y,int l,int r,int p) { //cout<<"Query ("<<x<<','<<y<<") ["<<l<<','<<r<<"] @"<<p<<endl; if (x==l && y==r) return data[p].range; int mid = (l+r)/2 ; //cout<<" "<<l<<','<<mid<<'|'<<mid+1<<','<<r<<endl; if (y<=mid) return query(x,y,l ,mid,p*2 ); if (x >mid) return query(x,y,mid+1,r ,p*2+1); Range LRange,RRange,ans,MRange; LRange=query(x ,mid,l ,mid,p*2 ); RRange=query(mid+1,y ,mid+1,r ,p*2+1); ans = max(LRange,RRange); //cout<<" max(Query)"<<ans.sum()<<endl; int MaxPos=queryMax(mid+1,y ,mid+1,r ,p*2+1), MinPos=queryMin(x ,mid,l ,mid,p*2 ); //cout<<" MaxPos:"<<MaxPos<<" "<<"MinPos:"<<MinPos<<endl; MRange = Range(MinPos,MaxPos); ans = max(MRange,ans); /* if(A[MaxPos]-A[MinPos-1]>ans.sum()){ ans.left = MinPos; ans.right = MaxPos; } */ //cout<<" max(max-min)"<<ans.sum()<<endl; return ans; } #undef MaxSegmentLength }; SegmentTree Tree; int main() { int n,m,CaseNum=0;A[0]=0; while(scanf("%d%d",&n,&m)!=EOF){ for(int i=1;i<=n;i++) scanf("%lld",A+i); for(int i=2;i<=n;i++) A[i]+=A[i-1]; Tree.build(1,n,Tree.root); printf("Case %d: ",++CaseNum); for(int i=0;i<m;i++){ int a,b; scanf("%d%d",&a,&b); Range ans = Tree.query(a,b,1,n,Tree.root); printf("%d %d ",ans.left,ans.right); } } /* int N,delta; cin>>N; for(int i=1;i<=N;i++) cin>>A[i]; //delta=A[1]; //A[1]=A[0]=0; for(int i=2;i<=N;i++) A[i]+=A[i-1];//-delta; //for(int i=1;i<=N;i++)cout<<A[i]<<' '; //cout<<endl; Tree.build(1,N,Tree.root); int a,b; while(cin>>a>>b){ Range ans = Tree.query(a,b,1,N,Tree.root); cout<<ans.left<<' '<<ans.right<<endl; //cout<<ans.left<<','<<ans.right<<endl<<endl; } */ return 0; } //10 // 1 2 3 4 5 6 7 8 9 10 // 4 5 6 2 9 0 -1 13 9 -10 // 4 9 15 17 26 26 25 38 47 37 // 0 1 2 -2 5 -4 -5 9 5 -14
2 支持单点修改的线段树维护RMQ
#include <iostream> #include <cstring> #include <cstdio> using namespace std; /** * 待处理序列A从1到N */ const int MaxN = 200000+10; #define left first #define right second long long A[MaxN]; struct node { long long max; node(long long x=0):max(x){}; }; struct SegmentTree { #define MaxSegmentLength 200010 const int root; SegmentTree():root(1){} node data[4*MaxSegmentLength]; void newNode(int p,int x){data[p]=node(A[x]);} void maintain(int p){ int lch= p*2,rch= p*2+1; data[p].max=max(data[lch].max,data[rch].max); } void build(int x,int y,int p){ if (x==y) newNode(p,x); else { int mid=(x+y)/2; build(x ,mid,p*2 ); build(mid+1,y ,p*2+1); maintain(p); } } long long query(int x,int y,int l,int r,int p) { //cout<<"QueryMax ("<<x<<','<<y<<") ["<<l<<','<<r<<"] @"<<p<<endl; if (x==l && y==r) return data[p].max; int mid = (l+r)/2,LPos,RPos; //cout<<" "<<l<<','<<mid<<'|'<<mid+1<<','<<r<<endl; if (y<=mid) return query(x,y,l ,mid,p*2 ); if (x >mid) return query(x,y,mid+1,r ,p*2+1); //cout<<" max(L,R)"<<LPos<<' '<<RPos<<endl; return max(query(x,mid,l,mid,p*2),query(mid+1,y,mid+1,r,p*2+1)); } long long update(int key,long long value,int l,int r,int p) { if (key==l && key==r) { data[p].max=max(value,data[p].max); return data[p].max; } else{ int mid = (l+r)/2; //cout<<" "<<l<<','<<mid<<'|'<<mid+1<<','<<r<<endl; if (key<=mid) update(key,value,l ,mid,p*2 ); if (key >mid) update(key,value,mid+1,r ,p*2+1); maintain(p); return data[p].max; //cout<<" max(L,R)"<<LPos<<' '<<RPos<<endl; } } #undef MaxSegmentLength }; SegmentTree Tree; int main() { int n,m;A[0]=0; while(scanf("%d%d",&n,&m)!=EOF){ for(int i=1;i<=n;i++) scanf("%lld",A+i); Tree.build(1,n,Tree.root); for(int i=0;i<m;i++){ char flag,t; long long a,b; scanf("%c%c%lld%lld",&t,&flag,&a,&b); switch(flag){ case 'Q':{ cout<<Tree.query(a,b,1,n,Tree.root)<<endl; break; } case 'U':{ Tree.update(a,b,1,n,Tree.root); break; } } } } return 0; }