BZOJ1175 : [Balkan2007]The stairways of Saharna
The of
2023-09-11 14:15:04 时间
杨氏图表,维护若干个单调不下降队列。
每次新加入一个数时,先考虑第一个队列:
如果可以放在最后,则放在最后。
否则找到最小的可以替换的替换掉,再将替换的数放入第二个队列,以此类推。
最后$ans_i=\sum_{j=1}^i t_j$。
时间复杂度$O(n^2\log n)$。
#include<cstdio> #define N 5005 int n,i,x,t[N];unsigned char q[N][N]; void up(int p,int x){ if(x>=q[p][t[p]]){q[p][++t[p]]=x;return;} int l=1,r=t[p],mid,u; while(l<=r)if(q[p][mid=(l+r)>>1]>x)r=(u=mid)-1;else l=mid+1; up(p+1,q[p][u]),q[p][u]=x; } int main(){ scanf("%d",&n); for(i=1;i<=n;i++)scanf("%d",&x),up(1,x); for(i=1;;i++){ printf("%d\n",t[i]+=t[i-1]); if(t[i]==n)return 0; } }
相关文章
- 如何修正导入模型的旋转? How do I fix the rotation of an imported model?
- How to get the MouseEvent coordinates for an element that has CSS3 Transform?
- ANNOUNCEMENT: Deprecating the cursor_sharing = ‘SIMILAR’
- [Typescript] Tips: Decode URL search params at the type level with ts-toolbelt
- [Redux-Observable && Unit testing] Testing the output of epics
- [Angular 2] Rendering an Observable Date with the Async and Date Pipes
- [服务器时区问题]PHP Warning: strftime(): It is not safe to rely on the system's timezone set
- [转]HDFS Metadata Directories Explained - An overview of files and configurations under the HDFS meta-directory
- [React] Use the useReducer Hook and Dispatch Actions to Update State (useReducer, useMemo, useEffect)
- [TypeScript] Deeply mark all the properties of a type as read-only in TypeScript
- [NPM] npm check to update the dependencies
- 【Codeforces Round #426 (Div. 2) B】The Festive Evening
- 成功解决ValueError: Number of passed names did not match number of header fields in the file
- 成功解决bs4__init__.py:181: UserWarning: No parser was explicitly specified, so I'm using the best avai
- 简洁代码的艺术【The Art of Clean Code】
- What are the types of sampling in hive ?
- [TroubleShootin]The backup set holds a backup of a database other than the existing 'xxdb' database.
- 兔子--Calling startActivity() from outside of an Activity context requires the FLAG_ACTIVITY_NEW_TASK
- 转载:Introducing the software testing ice-cream cone (anti-pattern)
- 2018浙江省赛(ACM) The 15th Zhejiang Provincial Collegiate Programming Contest Sponsored by TuSimple
- Docker学习问题记录:denied: requested access to the resource is denied