CF Round 622 div2#
A.简单模拟
B.数学##
题意：
某人A参加一个比赛，共n人参加，有两轮，给定这两轮的名次x,y，总排名记为两轮排名和x+y，此值越小名次越前，并且对于与A同分者而言，A名次在最末，求A最好名次和最坏名字。
分析：
我们先考虑最坏怎么来
最劣的时候就是尽可能多的人总分与A相同
那么对于和为x+y的有序数对组合有x+y-1个，除去自己就是x+y-2个，而第一名位置是1，所以最劣位置是x+y-1,取min（x+y-1,n)即使最劣位置
而对于最优位置，x+y<=n,从上面那个组对的方式衍生开来，每队后面一个元素+1即可
而大于n，emmm...小数据找下规律吧，网上很多解释都有一定的瑕疵，我感觉多半是个结论。
AC代码
#include<iostream>
#include<cstring>
using namespace std;
#define INF 1e10+5
#define MAXN 105
#define MINN -105
typedef long long int LL;
void solve()
{
int n,x,y,ans1=1,ans2;
cin>>n>>x>>y;
ans2=min(n,x+y-1);
if(x+y>n)
{
ans1=min(n,x+y-n+1);
}
cout<<ans1<<" "<<ans2<<endl;
}
int main()
{
int t;
cin>>t;
for(int i=0;i<t;i++)
{
solve();
}
return 0;
}
C1&C2.分治，单调栈##
c2相对于c1而言n的数据扩大了（n≤5000001）
题意
Berland要起摩天大厦了。所有的摩天大厦都在高速公路附近建。发展商买了 nnn 块地准备建 nnn 栋摩天大厦，一块地一栋。
当规划一间摩天大厦的时候，建筑师要考虑一些条件。
第一，因为每栋摩天大厦有不同的用途，所以每栋摩天大厦都有自己的层数限制，也就是说，这栋摩天大厦的高度不能超过给定的值 mim_imi。
第二，根据城市的建设规则，一栋摩天大厦不能同时在左右有比它高的摩天大厦。
如果规范地表示，让我们把地编上一个编号从 111 到 nnn。那么如果在第 iii 块地的摩天大厦有 aia_iai 层，那么我们需要保证 1≤ai≤mi1 \le a_i \le m_i1≤ai≤mi。另外，这里不可以有整数 jjj 和 kkk 满足 j<i<kj < i < kj<i<k 并且 aj>ai<aka_j > a_i < a_kaj>ai<ak。第 j,kj, kj,k 块地并不需要与第 iii 块地相邻。
发展商想要使得每块地上摩天大厦的楼层数之和最大。也请帮他找出在任意一个最优状况中每个摩天大厦的高度。也就是，要让建筑师考虑的条件都符合，而且要使得每块地上摩天大厦的楼层数之和最大。
分析
题目无非就是维护一个单峰序列，使得他的序列和最大。
那么我们不妨从左往右处理一个单调栈s[i]，用来记录各个上升点对于的位置，用l[i]来记录以i为峰自左到右的总和。而用lst[i]记录对于i而言，到之前的某个位置lst[i]之间都是需要被削小成a[i]
那么就有关系l[i]=l[lst[i]]+(i-lst[i])*a[i];
那么每次i入栈之时无非就拿栈顶元素与a[i]比较，如果大，记录lst，入栈，否则一直出栈。
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define INF 1e10+5
#define MAXN 500050
#define MINN -105
typedef long long int LL;
int main()
{
LL n;
LL a[MAXN],l[MAXN],r[MAXN],lst[MAXN],s[MAXN];
LL curmaxn=0,index=0;
LL tp=0;
memset(l,0,sizeof(l));
memset(r,0,sizeof(r));
cin>>n;
memset(lst,0,sizeof(lst));
s[0]=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
while(a[s[tp]]>a[i]&&tp)tp--;
lst[i]=s[tp];
s[++tp]=i;
}
for(int i=1;i<=n;i++)l[i]=l[lst[i]]+(i-lst[i])*a[i];
reverse(a+1,a+n+1);
tp=0;
for(int i=1;i<=n;i++)
{
lst[i]=0;
while(a[s[tp]]>a[i]&&tp)tp--;
lst[i]=s[tp];
s[++tp]=i;
}
for(int i=1;i<=n;i++)r[i]=r[lst[i]]+(i-lst[i])*a[i];
reverse(r+1,r+n+1);
for(int i=1;i<=n;i++)
if(l[i]+r[i+1]>=curmaxn)
{
index=i;
curmaxn=l[i]+r[i+1];
}
reverse(a+1,a+n+1);
for(int i=index+2;i<=n;i++)
a[i]=min(a[i-1],a[i]);
for(int i=index-1;i>=1;i--)
a[i]=min(a[i+1],a[i]);
for(int i=1;i<=n;i++)
cout<<a[i]<<" ";
return 0;
}
