思路:
宋文杰的题解很详细.
一开始每个点30s,结果在OJ上一共30s...
也就是说原来莫队是能过的,结果我无悬念TLE.
莫队怎么做我就不说了.(貌似官方正解就是莫队...)
莫队很暴力,因为没有利用一个题目中的性质:就是数据随机生成!
询问随不随机意义是不大的.
但是如果询问很特殊,我们就可以用科学的方法去处理:
(1)任意两个区间不互相包含.这种情况我们将区间随便排个序就能发现总移动次数是O(n)的.
(2)任意两个区间要么互相包含,要么不相交.这样就会形成一棵树.我们利用启发式合并,插入次数就为O(nlogn).
但是随机数据显然没有这种性质.
那么唯一可能有比较优秀的性质的就是随机数列了.
考虑一种朴素算法:
将所有询问离线按照右端点从小到大排序.
从前向后依次加入右端点,令fi表示当前以i为起点的后缀的答案,那么朴素来看,如果当前加入的是n,那么f1−fn−1都需要更新.
但是有很多冗余的更新.
例如我们考虑所有大于an的数,不妨令ai,aj>an,ai>aj,i<j,那么如果我们能够维护一个后缀的答案,我们就只需更新fj就可以了.
于是我们发现了某些单调性.
我们利用数据结构维护后缀的答案,那么只需更新一些点就行了.
那么我们的任务就是找到,对于n之前的数,一个均>an的递减序列,一个均<an的递增序列.然后我们就拿序列中的东西暴力更新答案.
然而由于是随机数据,序列中的元素个数是O(logn)级别的.
这样总时间复杂度就是O(qlogn+nlog2n).
具体去看宋文杰的题解.
(另外此题要求结果>0 23333)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 | #include<cstdio>#include<cctype>#include<cstring>#include<iostream>#include<algorithm>using namespace std;#define N 100010#define Q 100010int n,q,a[N];struct Interval{ int l,r,lab; bool operator<(const Interval&B)const{return r<B.r;}}S[N];int re[Q];inline void mini(int&x,int y){if(x>y)x=y;}struct SegmentTree{ int A[262144],M; inline void Init(int _siz){ for(M=1;M<(_siz+2);M<<=1); memset(A,0x3f,sizeof A); } inline void modify(int x,int d){ for(x+=M;x;x>>=1)mini(A[x],d); } inline int query(int tl,int tr){ int re=~0U>>1; for(tl+=M-1,tr+=M+1;tl^tr^1;tl>>=1,tr>>=1){ if(~tl&1)mini(re,A[tl^1]); if(tr&1)mini(re,A[tr^1]); } return re; }}Seg;int preless[N],premore[N],small[N][30],big[N][30],stk[N],top;int main(){ //freopen("tt.in","r",stdin); scanf("%d%d",&n,&q); register int i,j,k; for(i=1;i<=n;++i)scanf("%d",&a[i]); for(i=1;i<=q;++i) scanf("%d%d",&S[i].l,&S[i].r),S[i].lab=i; sort(S+1,S+q+1); Seg.Init(n); for(i=1;i<=n;++i){ while(top&&a[stk[top]]>=a[i])--top; preless[i]=stk[top]; stk[++top]=i; } top=0; for(i=1;i<=n;++i){ while(top&&a[stk[top]]<=a[i])--top; premore[i]=stk[top]; stk[++top]=i; } for(i=1;i<=n;++i){ if(premore[i]){ big[i][++big[i][0]]=premore[i]; j=big[i][1]; while(1){ bool find=0; for(k=1;k<=small[j][0];++k)if(a[small[j][k]]>a[i]){find=1;break;} if(find)big[i][++big[i][0]]=(j=small[j][k]);else break; } } if(preless[i]){ small[i][++small[i][0]]=preless[i]; j=small[i][1]; while(1){ bool find=0; for(k=1;k<=big[j][0];++k)if(a[big[j][k]]<a[i]){find=1;break;} if(find)small[i][++small[i][0]]=(j=big[j][k]);else break; } } } j=1; for(i=1;i<=n;++i){ for(k=1;k<=small[i][0];++k)Seg.modify(small[i][k],a[i]-a[small[i][k]]); for(k=1;k<=big[i][0];++k)Seg.modify(big[i][k],a[big[i][k]]-a[i]); for(;j<=q&&S[j].r==i;++j)re[S[j].lab]=Seg.query(S[j].l,S[j].r); } for(i=1;i<=q;++i)printf("%d\n",re[i]); return 0;} |