CF1450D Rating Compression

重要性质除了k1之外(这里的答案是如果初始数组就是个排列就是1否则就是0)剩余的答案是一些0加上一些1也就是000011111这一类。感性理解一下当k变大时压缩数组就会变小原数组中较小的值不会消失只有大的值会消失而这正是符合要求的然后考虑为什么 k1 需要特判因为它的要求特殊没有操作保证原序列是排列即可与后面答案无关联也就与该性质无关。线段树和ST表都可以但是线段树必须不能#define int long long因为n不小并且线段树常熟巨大所以你如果还将时间复杂度乘二的话你就会Time limit exceeded on test 10不嘻嘻。代码(求赞)#includebits/stdc.h using namespace std; const int N3e55; int T,n,cnt0,a[N],vis[N],ans[N]; struct node{ int mi; }; node tree[4*N]; void pushup(int p){ tree[p].mimin(tree[p1].mi,tree[p1|1].mi); } void update(int p,int l,int r,int x,int k){ if(lr){ tree[p].mik; return; } int mid(lr)1; if(xmid) update(p1,l,mid,x,k); else update(p1|1,mid1,r,x,k); pushup(p); } int query(int p,int l,int r,int L,int R){ if(LlrR) return tree[p].mi; int mid(lr)1; int resINT_MAX;//写的LLONG_MIN糖完了 if(Lmid) resmin(res,query(p1,l,mid,L,R)); if(midR) resmin(res,query(p1|1,mid1,r,L,R)); return res; } bool check(int x,int k){ for(int i1;in-k1;i) vis[i]0; for(int i1;in-k1;i){ int xquery(1,1,n,i,ik-1); vis[x]; if(vis[x]1) return false; } for(int i1;in-k1;i){ if(vis[i]!1){ return false; } } return true; } int main(){ scanf(%d,T); while(T--){ cnt0; scanf(%d,n); for(int i1;in;i){ scanf(%d,a[i]); vis[a[i]]; if(vis[a[i]]1){ cnt; } update(1,1,n,i,a[i]); } if(cntn) ans[1]1; int l1,rn1; while(l1r){ int mid(lr)1; if(check(n,mid)) rmid; else lmid; } for(int in;ir;i--) ans[i]1; for(int i1;in;i){ printf(%d,ans[i]); ans[i]vis[i]0; } printf(\n); } return ~(-1); }