网站开发试验报告,网站关键词推广工具,网站设计旅行社新闻内容,铁常乐个人网站正题
题目链接:https://www.luogu.com.cn/problem/AT4439 题目大意
给出1∼n1\sim n1∼n的排列aaa。求一个字典序最小的010101串sss满足将000对应位置按顺序取出成为序列AAA#xff0c;剩下的成为序列BBB。
要求AAA和BBB的前缀最大值个数相同。 1≤n≤21051\leq n\leq 2\ti…正题
题目链接:https://www.luogu.com.cn/problem/AT4439 题目大意
给出1∼n1\sim n1∼n的排列aaa。求一个字典序最小的010101串sss满足将000对应位置按顺序取出成为序列AAA剩下的成为序列BBB。
要求AAA和BBB的前缀最大值个数相同。
1≤n≤2×1051\leq n\leq 2\times 10^51≤n≤2×105 解题思路
首先对于前缀最大值来说在排列aaa中的前缀最大值肯定在A/BA/BA/B中也是前缀最大值。
而假设我们序列AAA和BBB中都存在一个前缀最大值是在aaa中没有出现过的那么显然这两个值前面比它大的值都在另一个序列中所以我们交换这两个值时A/BA/BA/B的前缀最大值个数都减少了111。
所以如果存在一组解A/BA/BA/B中存在一个序列的所有前缀最大值都是aaa中原来的最大值。
那么接着考虑假设我们做到一个状态A/BA/BA/B中目前最大值个数为na/nbn_a/n_bna/nb后面还有ccc个原来aaa序列中的最大值BBB需要用kkk个剩下ppp个都是新的最大值那么如果有解就有等式 nac−knbkp⇒na−nbc2kpn_ac-kn_bkp\Rightarrow n_a-n_bc2kpnac−knbkp⇒na−nbc2kp 而左边的式子是定值所以我们只需要考虑右边式子的取值范围。
然后对于序列BBB目前最后一个数是mbm_bmb设旧最大值数权为222其他数的权值111。我们就需要考虑后面是否存在一个mbm_bmb开始的上升序列的权值和为na−nbcn_a-n_bcna−nbc。
而因为权值只有111和222所以我们用数据结构维护一下奇偶的最大答案即可。
由于他要求字典序最小我们无法确定AAA是全是旧的最大值还是BBB全是旧的最大值所以我们两种情况都需要判断。
时间复杂度O(nlogn)O(n\log n)O(nlogn) code
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N2e510;
int n,s,a[N],od[N],ans[N],f[N][2];
struct SegTree{int w[N2];void Change(int x,int L,int R,int pos,int val){if(LR){w[x]val;return;}int mid(LR)1;if(posmid)Change(x*2,L,mid,pos,val);else Change(x*21,mid1,R,pos,val);w[x]max(w[x*2],w[x*21]);}int Ask(int x,int L,int R,int l,int r){lmax(l,L);rmin(r,R);if(lr)return w[0];if(LlRr)return w[x];int mid(LR)1;if(rmid)return Ask(x*2,L,mid,l,r);if(lmid)return Ask(x*21,mid1,R,l,r);return max(Ask(x*2,L,mid,l,mid),Ask(x*21,mid1,R,mid1,r));}
}T[2];
bool check(int p,int x){if(x0)return 0;return T[x1].Ask(1,1,n,p,n)x;
}
int main()
{scanf(%d,n);int maxs0;for(int i1;in;i){scanf(%d,a[i]);if(a[i]maxs)od[i]1,s,maxsa[i]; }memset(T[1].w,0xcf,sizeof(T[1].w));for(int in;i1;i--){int p!od[i];for(int j0;j2;j){f[i][j]T[j^p].Ask(1,1,n,a[i]1,n)1od[i];T[j].Change(1,1,n,a[i],f[i][j]);}}int A0,B0,ma0,mb0;for(int i1;in;i){s-od[i];T[0].Change(1,1,n,a[i],T[0].w[0]);T[1].Change(1,1,n,a[i],T[1].w[0]);if(check(max(ma,a[i]),Bs-A-(a[i]ma))||check(mb,As-B(a[i]ma)))ans[i]0,A(a[i]ma),mamax(ma,a[i]);else ans[i]1,B(a[i]mb),mbmax(mb,a[i]);}if(A!B)return puts(-1)0;for(int i1;in;i)putchar(ans[i]0);return 0;
}
