给你一个序列，让你求一个区间中最大值和最小值相差不过k的最长连续序列的长度 线段树版本：
#include <stdio.h> #include <string.h> #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 inline int MAX(int a,int b) {return a>b?a:b;} inline int MIN(int a,int b) {return a>b?b:a;} const int N=100005; int ql[N],qr[N]; int Max[N<<2]; int Min[N<<2]; //int sum[N<<2]; void push(int rt) { Max[rt]=MAX(Max[rt<<1] ,Max[rt<<1|1]); Min[rt]=MIN(Min[rt<<1] ,Min[rt<<1|1]); // sum[rt]=sum[rt<<1]+sum[rt<<1|1]; } void build(int l,int r,int rt) { if(l==r) { scanf("%d",&Max[rt]); Min[rt]=Max[rt]; return; } int m=(l+r)>>1; build(ls); build(rs); push(rt); } int query(int L,int R,int l,int r,int rt)//区间最大值 { if(L<=l&&r<=R) return Max[rt]; int m=(l+r)>>1; int ret=0; if(L<=m) ret=MAX(ret,query(L,R,ls)); if(R>m) ret=MAX(ret,query(L,R,rs)); return ret; } int query1(int L,int R,int l,int r,int rt)//区间最小值 { if (L<=l&&r<=R) return Min[rt]; int m=(l+r)>>1; int ret=0x3f3f3f3f; if(L<=m) ret=MIN(ret,query1(L,R,ls)); if(R>m) ret=MIN(ret,query1(L,R,rs)); return ret; } //int query2(int L,int R,int l,int r,int rt)//区间最小值 //{ // if (L<=l&&r<=R) // { // return sum[rt]; // } // int m=(l+r)>>1; // int ret=0; // if (L<=m) // ret+=query(L,R,ls); // if (R>m) // ret+=query(L,R,rs); // return ret; //} int main() { int n,k; scanf("%d%d",&n,&k); build(1,n,1); int i,j,ans,t; ans=t=0; for(i=j=1;j<=n;i++) { if(j<i) j=i; while(j<=n&&(query(i,j,1,n,1)-query1(i,j,1,n,1)<=k)) ++j; if(j-i>ans) ans=j-i,ql[0]=i,qr[0]=j-1,t=1; else if(j-i==ans) ql[t]=i,qr[t++]=j-1; } printf("%d %d\n",ans,t); for(i=0;i<t;i++) printf("%d %d\n",ql[i],qr[i]); }Multiset版本
#include<cstdio> #include<set> int a[100100],c[100100]; using namespace std; multiset<int> s; int main() { int n,k;scanf("%d%d",&n,&k);int l=0,ma=0,t=0; for(int i=0;i<n;i++) { scanf("%d",&a[i]); s.insert(a[i]); while(*s.rbegin()-*s.begin()>k) s.erase(s.find(a[l++]));//注意这里不能是s.erase(a[l++]);这样会删除全部a[l++]这个元素 if(i-l+1>ma){ma=i-l+1;t=0;c[t++]=l;} else if(i-l+1==ma) c[t++]=l; } printf("%d %d\n",ma,t); for(int i=0;i<t;i++) printf("%d %d\n",c[i]+1,c[i]+ma); }双端队列版本：(待续)
