BZOJ 4491: 我也不知道題目名字是什么

4491: 我也不知道題目名字是什么

Time Limit:?10 Sec??Memory Limit:?512 MB
Submit:?278??Solved:?154
[Submit][Status][Discuss]

Description

給定一個序列A[i]，每次詢問l,r，求[l,r]內最長子串，使得該子串為不上升子串或不下降子串

Input

第一行n，表示A數組有多少元素
接下來一行為n個整數A[i]
接下來一個整數Q，表示詢問數量
接下來Q行，每行2個整數l，r

Output

對于每個詢問，求[l,r]內最長子串，使得該子串為不上升子串或不下降子串

Sample Input

9
1 2 3 4 5 6 5 4 3
5
1 6
1 7
2 7
1 9
5 9

Sample Output

6
6
5
6
4
//樣例解釋
五個詢問分別對應
[1,6][1,6][2,6][1,6][6,9]

HINT

N,Q<=50000

Source

By 一個讀錯題的沙茶

分析：

其實就是一個很經典的思想...

既然是最長的不下降子串，也就是連續的，那么我們就差分一下，這樣就轉化成最長的大于等于0的連續子串...線段樹維護前后綴和區間最長就好了...

其實寫這道題主要目的是記錄一下某只智障(我...)的事跡...

交上去怎么都TLE，然后要了數據，發現可以跑出來答案還是對的...但是跑得極其慢.....大概就是100s估計也跑不出來...

然后請來RYC小盆友來查錯...我說我再怎么也不能把線段樹寫成$O(N^2)$的吧...剛說完一秒鐘YSQ小盆友指了query的這一行...

inline M query(int l,int r,int tr){if(tree[tr].l==r&&tree[tr].r==r)return tree[tr];

　　

我寫成了$tree[tr].l==r$感覺自己要上天....QwQ~~~

代碼：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;const int maxn=50000+5;int n,m,a[maxn],A[maxn];struct SegmentTree{struct M{int l,r,len,lmax,rmax,mmax;}tree[maxn<<2];inline M merge(M a,M b){M res;res.l=a.l,res.r=b.r,res.len=a.len+b.len;res.lmax=a.len==a.lmax?a.len+b.lmax:a.lmax;res.rmax=b.len==b.rmax?b.len+a.rmax:b.rmax;res.mmax=max(a.rmax+b.lmax,max(a.mmax,b.mmax));return res;}inline void build(int l,int r,int tr){tree[tr].l=l;tree[tr].r=r;tree[tr].len=r-l+1;if(l==r){if(a[l]>=0)tree[tr].lmax=tree[tr].rmax=tree[tr].mmax=1;elsetree[tr].lmax=tree[tr].rmax=tree[tr].mmax=0;return;}int mid=(l+r)>>1;build(l,mid,tr<<1),build(mid+1,r,tr<<1|1);tree[tr]=merge(tree[tr<<1],tree[tr<<1|1]);}inline M query(int l,int r,int tr){if(tree[tr].l==r&&tree[tr].r==r)return tree[tr];int mid=(tree[tr].l+tree[tr].r)>>1;if(r<=mid)return query(l,r,tr<<1);else if(l>mid)return query(l,r,tr<<1|1);elsereturn merge(query(l,mid,tr<<1),query(mid+1,r,tr<<1|1));}}tr1,tr2;signed main(void){scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&A[i]);for(int i=1;i<n;i++) a[i]=A[i+1]-A[i];tr1.build(1,n-1,1);for(int i=1,j=n;i<j;i++,j--) swap(A[i],A[j]);for(int i=1;i<n;i++) a[i]=A[i+1]-A[i];tr2.build(1,n-1,1);scanf("%d",&m);for(int i=1,l,r;i<=m;i++){scanf("%d%d",&l,&r);if(l==r) puts("1");else printf("%d\n",max(tr1.query(l,r-1,1).mmax+1,tr2.query(n-r+1,n-l,1).mmax+1));}return 0;
}

　　

---

By NeighThorn