<\/span><\/h2>\n\u5f88\u597d\u73a9\u7684\u65b9\u5f0f<\/p>\n
\u9996\u5148\uff0c\u6211\u4eec\u8003\u8651dp\uff0c\u7528f[i]\u8868\u793a\u5230\u7b2ci\u4f4d\u65f6\u7684\u6700\u957f\u957f\u5ea6<\/p>\n
\u6240\u4ee5\u8fd9\u4e2a\u65f6\u5019\u4ed6\u8fde\u63a5\u4e0b\u4e00\u4f4d\u7684\u7b26\u53f7\u662f\u56fa\u5b9a\u7684<\/p>\n
\u8fd9\u6837\u6211\u4eec\u5c31\u53ef\u4ee5\u5206\u4e09\u7c7b\uff1a<\/p>\n
\u5982\u679c\u662f=\uff0c\u5c31\u5f00\u4e00\u4e2a\u6876\u8bb0\u5f55\u4e00\u4e0b\u503c\u4e3a\u8fd9\u4e2a\u662f\u7684\u5f53\u524d\u6700\u4f18\u89e3<\/p>\n
\u5982\u679c\u662f<\uff0c\u6211\u4eec\u53ef\u4ee5\u63a8\u5165\u4e00\u4e2a\u4e0b\u4e00\u4f4d\u662f\u5c0f\u4e8e\u53f7\u7684\u7ebf\u6bb5\u6811\uff0c\u4ee5\u6743\u503c\u4e3a\u4e0b\u8868\uff0c\u7ef4\u62a4f\u503c<\/p>\n
\u7136\u540e\u4e0b\u6b21\u66f4\u65b0f\u7684\u65f6\u5019\uff0c\u53d6\u51fa\u5408\u6cd5\u533a\u95f4\u7684\u6700\u5927\u7684\u503c\u5c31\u597d\u4e86<\/p>\n
\u5982\u679c\u662f>\uff0c\u540c\u7406\u53ef\u4ee5\u7ef4\u62a4\u4e00\u4e2a\u4e0b\u4e00\u4f4d\u662f\u5c0f\u4e8e\u53f7\u7684\u7ebf\u6bb5\u6811<\/p>\n
\u8fd9\u6837\u5c31\u53ef\u4ee5\u505a\u5230\u65f6\u95f4\u590d\u6742\u5ea6O(nlogn)\u4e86<\/p>\n
#include<map>\r\n#include<cmath>\r\n#include<queue>\r\n#include<cstdio>\r\n#include<cstring>\r\n#include<iostream>\r\n#include<algorithm>\r\nusing namespace std;\r\n#define inf 1000000007\r\n#define ll long long\r\n#define N 1000010\r\ninline int rd()\r\n{\r\n\tint x=0,f=1;char ch=getchar();\r\n\twhile(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}\r\n\twhile(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}\r\n\treturn x*f;\r\n}\r\nint n,k,nn,a[N],op[N],f[N],ans;\r\nstruct segtr\r\n{\r\n\t#define ls p<<1\r\n\t#define rs p<<1|1\r\n\tint mx[N<<2];\r\n\tvoid xg(int p,int l,int r,int x,int v)\r\n\t{\r\n\t\tif(l==r){mx[p]=v;return;}\r\n\t\tint mid=l+r>>1;\r\n\t\tx<=mid?xg(ls,l,mid,x,v):xg(rs,mid+1,r,x,v);\r\n\t\tmx[p]=max(mx[ls],mx[rs]);\r\n\t}\r\n\tint fd(int p,int l,int r,int L,int R)\r\n\t{\r\n\t\tif(L>R) return 0;\r\n\t\tif(l==L&&R==r) return mx[p];\r\n\t\tint mid=l+r>>1;\r\n\t\tif(R<=mid) return fd(ls,l,mid,L,R);\r\n\t\tif(L>mid) return fd(rs,mid+1,r,L,R);\r\n\t\treturn max(fd(ls,l,mid,L,mid),fd(rs,mid+1,r,mid+1,R));\r\n\t}\r\n}tr[2];\r\nint ji[N];\r\nint main()\r\n{\r\n\tn=rd();k=rd();\r\n\tfor(int i=1;i<=n;i++) a[i]=rd(),nn=max(a[i],nn);\r\n\tchar ch[5];\r\n\tfor(int i=1;i<=k;i++)\r\n\t{\r\n\t\tscanf(\"%s\",ch);\r\n\t\tif(ch[0]=='>') op[i]=0;\r\n\t\telse if(ch[0]=='<') op[i]=1;\r\n\t\telse op[i]=2;\r\n }\r\n\tfor(int i=1,tt;i<=n;i++)\r\n\t{\r\n\t\ttt=max(tr[0].fd(1,1,nn,a[i]+1,nn),tr[1].fd(1,1,nn,1,a[i]-1));\r\n\t\tf[i]=max(tt,ji[a[i]])+1;\r\n\t\tans=max(ans,f[i]);\r\n\t\ttt=op[(f[i]-1)%k+1];\r\n\t\tif(tt==2) ji[a[i]]=max(f[i],ji[a[i]]);\r\n\t\telse tr[tt].xg(1,1,nn,a[i],f[i]);\r\n\t}\r\n\tprintf(\"%d\\n\",ans);\r\n\treturn 0;\r\n}<\/pre>\n <\/p>\n","protected":false},"excerpt":{"rendered":"
2090: [Poi2010]Monotonicity 2 Time Limit:\u00a030 Sec […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[5,10],"class_list":["post-306","post","type-post","status-publish","format-standard","hentry","category-bzoj","tag-dp","tag-10"],"_links":{"self":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/306","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=306"}],"version-history":[{"count":2,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/306\/revisions"}],"predecessor-version":[{"id":308,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/306\/revisions\/308"}],"wp:attachment":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=306"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=306"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=306"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}