首页 > 代码库 > 【BZOJ4491】我也不知道题目名字是什么 [线段树]
【BZOJ4491】我也不知道题目名字是什么 [线段树]
4491: 我也不知道题目名字是什么
Time Limit: 10 Sec Memory Limit: 512 MBSubmit: 315 Solved: 173
[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
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
6
5
6
4
HINT
N,Q<=50000
Solution
直接上线段树，记录一下一个区间内：左边最长，右边最长，整体最优。再分一下不下降和不上升即可。
Code
1 #include<iostream> 2 #include<string> 3 #include<algorithm> 4 #include<cstdio> 5 #include<cstring> 6 #include<cstdlib> 7 #include<cmath> 8 #include<queue> 9 using namespace std; 10 11 const int ONE = 500005;12 const int INF = 2147483640;13 14 int n,Q;15 int x,y;16 int a[ONE];17 18 struct power19 {20 int len;21 int Lval, Rval;22 int Lup,Ldn, Rup,Rdn;23 int Maxup, Maxdn;24 25 friend power operator +(power a, power b)26 {27 power A;28 A.len = a.len + b.len;29 A.Lval = a.Lval; A.Rval = b.Rval;30 31 A.Lup = a.Lup; if(a.Lup == a.len && a.Rval <= b.Lval) A.Lup += b.Lup;32 A.Ldn = a.Ldn; if(a.Ldn == a.len && a.Rval >= b.Lval) A.Ldn += b.Ldn;33 34 A.Rup = b.Rup; if(b.Rup == b.len && a.Rval <= b.Lval) A.Rup += a.Rup;35 A.Rdn = b.Rdn; if(b.Rdn == b.len && a.Rval >= b.Lval) A.Rdn += a.Rdn;36 37 A.Maxup = max(a.Maxup, b.Maxup);38 A.Maxdn = max(a.Maxdn, b.Maxdn);39 40 if(a.Rval <= b.Lval) A.Maxup = max(A.Maxup, a.Rup+b.Lup);41 if(a.Rval >= b.Lval) A.Maxdn = max(A.Maxdn, a.Rdn+b.Ldn);42 43 return A;44 }45 }Node[ONE];46 47 int get()48 { 49 int res=1,Q=1;char c; 50 while( (c=getchar())<48 || c>57 ) 51 if(c==‘-‘)Q=-1; 52 res=c-48; 53 while( (c=getchar())>=48 && c<=57 ) 54 res=res*10+c-48; 55 return res*Q;56 }57 58 void Build(int i,int l,int r)59 {60 if(l == r)61 {62 Node[i].Lval = Node[i].Rval = a[l];63 Node[i].len = 1;64 Node[i].Lup = Node[i].Rup = Node[i].Ldn = Node[i].Rdn = 1;65 Node[i].Maxup = Node[i].Maxdn = 1;66 return; 67 }68 69 int mid = l+r>>1;70 Build(i<<1, l,mid); Build(i<<1|1, mid+1,r);71 Node[i] = Node[i<<1] + Node[i<<1|1];72 }73 74 power Query(int i,int l,int r,int L,int R)75 {76 if(L==l && r==R) return Node[i];77 int mid = l+r>>1;78 if(mid+1 > R) return Query(i<<1, l,mid,L,R);79 else if(L > mid) return Query(i<<1|1, mid+1,r,L,R);80 else return Query(i<<1, l,mid,L,mid) + Query(i<<1|1, mid+1,r,mid+1,R); 81 }82 83 int main() 84 {85 n = get();86 for(int i=1; i<=n; i++) a[i] = get();87 Build(1,1,n);88 89 Q = get();90 while(Q--)91 {92 x = get(); y = get();93 power res = Query(1,1,n,x,y);94 printf("%d\n", max(res.Maxup, res.Maxdn) );95 }96 }
【BZOJ4491】我也不知道题目名字是什么 [线段树]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。