首页 > 代码库 > bzoj4491 我也不知道题目名字是什么

bzoj4491 我也不知道题目名字是什么

2024-10-16 06:31:02   203人阅读

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

 

正解：线段树。

线段树傻逼题，维护$8$个标记即可。

 

 1 //It is made by wfj_2048~ 2 #include <algorithm> 3 #include <iostream> 4 #include <cstring> 5 #include <cstdlib> 6 #include <cstdio> 7 #include <vector> 8 #include <cmath> 9 #include <queue>10 #include <stack>11 #include <map>12 #include <set>13 #define N (100010)14 #define ls (x<<1)15 #define rs (x<<1|1)16 #define il inline17 #define RG register18 #define ll long long19 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)20 21 using namespace std;22 23 struct data{ int mx,mn,lmx,rmx,lmn,rmn,L,R; }t[4*N];24 25 int a[N],n,Q;26 27 il int gi(){28     RG int x=0,q=1; RG char ch=getchar();29     while ((ch<‘0‘ || ch>‘9‘) && ch!=‘-‘) ch=getchar();30     if (ch==‘-‘) q=-1,ch=getchar();31     while (ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-48,ch=getchar();32     return q*x;33 }34 35 il void pushup(RG data &x,RG data l,RG data r,RG int h,RG int t,RG int mid){36     x.mx=max(l.mx,r.mx); if (l.R<=r.L) x.mx=max(x.mx,l.rmx+r.lmx);37     x.mn=max(l.mn,r.mn); if (l.R>=r.L) x.mn=max(x.mn,l.rmn+r.lmn);38     x.lmx=(l.mx==mid-h+1 && l.R<=r.L) ? l.mx+r.lmx : l.lmx;39     x.rmx=(r.mx==t-mid && l.R<=r.L) ? r.mx+l.rmx : r.rmx;40     x.lmn=(l.mn==mid-h+1 && l.R>=r.L) ? l.mn+r.lmn : l.lmn;41     x.rmn=(r.mn==t-mid && l.R>=r.L) ? r.mn+l.rmn : r.rmn;42     x.L=l.L,x.R=r.R; return;43 }44 45 il void build(RG int x,RG int l,RG int r){46     if (l==r){47     t[x].mx=t[x].mn=t[x].lmx=t[x].rmx=t[x].lmn=t[x].rmn=1;48     t[x].L=t[x].R=a[l]; return;49     }50     RG int mid=(l+r)>>1; build(ls,l,mid),build(rs,mid+1,r);51     pushup(t[x],t[ls],t[rs],l,r,mid); return;52 }53 54 il data query(RG int x,RG int l,RG int r,RG int xl,RG int xr){55     if (xl<=l && r<=xr) return t[x]; RG int mid=(l+r)>>1;56     if (xr<=mid) return query(ls,l,mid,xl,xr);57     else if (xl>mid) return query(rs,mid+1,r,xl,xr);58     else{59     RG data res;60     pushup(res,query(ls,l,mid,xl,mid),query(rs,mid+1,r,mid+1,xr),xl,xr,mid);61     return res;62     }63 }64 65 il int find(RG int l,RG int r){66     RG data res=query(1,1,n,l,r);67     return max(res.mx,res.mn);68 }69 70 il void work(){71     n=gi(); for (RG int i=1;i<=n;++i) a[i]=gi();72     build(1,1,n); Q=gi();73     for (RG int i=1,l,r;i<=Q;++i)74     l=gi(),r=gi(),printf("%d\n",find(l,r));75     return;76 }77 78 int main(){79     File("substring");80     work();81     return 0;82 }

 

bzoj4491 我也不知道题目名字是什么


联系
我们