我单推这些题（
P2824 [HEOI2016/TJOI2016]排序
两种做法应该都是很好的方法。
二分
时间复杂度 \(O(n\log^2 n)\)。
二分答案后赋权值为 \(0/1\)，有很优美的性质。
二分答案 \(mid\)，我们把原排列中大于等于 \(mid\) 的数都标记为 \(1\)，小于 \(mid\) 的都标记为 \(0\)。然后对于每个操作我们就将 \(01\) 序列排个序。最后如果第 \(p\) 个位子仍是 \(1\) 的话就是可行的。
太懒了并没有写
DS
时间复杂度 \(O(n\log n)\)。
考虑 ODT 的维护，可以把区间排序操作类比为区间染色。
然后对于区间分裂合并直接开权值线段树分裂合并即可。
时间复杂度证明即线段树分裂合并复杂度（
很好写 这是好的（
Code
const int N=4e5+5,logN=20;
int n,m,rt[N],nw=1,a[N];
struct range{
int l,r,v;
range(int L,int R=-1,int V=0):l(L),r(R),v(V){}
bool operator < (range x) const{return l<x.l;}
};
set<range> qaq;
#define IT set<range>::iterator
struct SGT{
#define mid ((l+r)>>1)
#define xl (ls[x])
#define xr (rs[x])
int sum[N*logN],ls[N*logN],rs[N*logN],st[N],tp,cnt;
inline int newnode(){
if(tp) return st[tp--];
return ++cnt;
}
inline void pushup(int x){sum[x]=sum[xl]+sum[xr];}
inline void del(int x){sum[x]=xl=xr=0;st[++tp]=x;}
inline int insert(int x,int l,int r,int k,int v){
if(!x) x=newnode();
if(l==r){sum[x]+=v;return x;}
if(k<=mid) xl=insert(xl,l,mid,k,v);
else xr=insert(xr,mid+1,r,k,v);
pushup(x);return x;
}
inline int merge(int x,int y,int l,int r){
if(!x||!y) return x|y;
if(l==r){sum[x]+=sum[y];del(y);return x;}
xl=merge(xl,ls[y],l,mid);xr=merge(xr,rs[y],mid+1,r);
pushup(x);return x;
}
inline void split(int x,int &y,int l,int r,int k){
if(!x) return ;y=newnode();
if(k>sum[xl]) split(xr,rs[y],mid+1,r,k-sum[xl]);
else xr^=rs[y]^=xr^=rs[y];
if(k<sum[xl]) split(xl,ls[y],l,mid,k);
pushup(x);pushup(y);return ;
}
inline int kth(int x,int l,int r,int k){
if(l==r) return l;
if(sum[xl]>=k) return kth(xl,l,mid,k);
return kth(xr,mid+1,r,k-sum[xl]);
}
inline int query(int x,int l,int r,int L,int R){
if(L<=l&&r<=R) return sum[x];
ll res=0;
if(mid>=L) res+=query(xl,l,mid,L,R);
if(mid<R) res+=query(xr,mid+1,r,L,R);
return res;
}
}T;
// ---------- SGT ---------- //
inline IT split(int pos){
IT tmp=qaq.lower_bound(range(pos));
if(tmp!=qaq.end()&&tmp->l==pos) return tmp;
--tmp;int l=tmp->l,r=tmp->r,v=tmp->v;
if(!v) T.split(rt[l],rt[pos],1,n,pos-l);
else T.split(rt[l],rt[pos],1,n,r-pos+1),rt[l]^=rt[pos]^=rt[l]^=rt[pos];
qaq.erase(tmp);qaq.insert(range(l,pos-1,v));
return qaq.insert(range(pos,r,v)).first;
}
inline void assign(int l,int r,int op){
IT R=split(r+1),L=split(l),nw=L;++nw;
while(nw!=R) T.merge(rt[l],rt[nw->l],1,n),++nw;
qaq.erase(L,R);qaq.insert(range(l,r,op));
}
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
rd(n);rd(m);
for(re i=1;i<=n;++i){
rd(a[i]);rt[i]=T.insert(rt[i],1,n,a[i],1);qaq.insert(range(i,i,0));
}
qaq.insert(range(n+1,n+1,0));
for(re i=1;i<=m;++i){
int op,l,r;rd(op);rd(l);rd(r);
assign(l,r,op);
}
rd(m);
for(IT nw=qaq.begin();nw!=qaq.end();++nw){
if(nw->r-nw->l+1<m) m-=nw->r-nw->l+1;
else{
wr(T.kth(rt[nw->l],1,n,nw->v?nw->r-nw->l+2-m:m));puts("");break;
}
}
return 0;
}
// ---------- Main ---------- //
CF1559D Mocha and Diana
很好的贪心题。
令 \(A\) 图连通块个数不小于 \(B\) 图。
我们证明 \(B\) 图最后连通块个数为 \(1\)。
若 \(A\) 连通块数量大于 \(1\)，若此时无法操作，考虑到 \(A\) 图中连通块 \(a\), \(b\)。
对于 \(a\)，\(b\) 中的点，他们在 \(B\) 图中一定连通。
那么考虑到 \(A\) 中所有连通块，可发现 \(B\) 全连通，即连通块数量为 \(1\)。
由此贪心分析可知，随意加可行边即可。
因此 D1 就可以直接暴力枚举点对加边即可，时间复杂度 \(O(n^2\alpha(n))\)。
优化贪心。
考虑一个中心点 \(s\)。
我们先让所有点与 \(s\) 尝试连边。
然后连完后令 \(A\) 图中与 \(s\) 不连通的点集为 \(L\)，\(B\) 图中与 \(s\) 不连通的点集为 \(R\)。
显然 \(L\cap R=\varnothing\)。
考虑 \(l\in L\) 和 \(r\in R\)。
由定义有 \(A\) 图中 \(l\) 与 \(s\) 不连通，\(r\) 与 \(s\) 连通，\(B\) 图相反。
那么任意 \(l\) 与 \(r\) 都可连边。
然后只要随意配对完 \(L\) 或 \(R\) 就行了，此时一幅图变成一个连通块。
时间复杂度 \(O(n\alpha(n))\)。
Code
const int N=1e5+5;
int n,m1,m2,fa1[N],fa2[N],ans,qaq[N][2],l[N],r[N],cnt1,cnt2;
inline int find1(int x){return fa1[x]==x?x:fa1[x]=find1(fa1[x]);}
inline void merge1(int x,int y){fa1[find1(x)]=find1(y);}
inline int find2(int x){return fa2[x]==x?x:fa2[x]=find2(fa2[x]);}
inline void merge2(int x,int y){fa2[find2(x)]=find2(y);}
// ---------- ---------- //
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
// ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
rd(n);rd(m1);rd(m2);
for(re i=1;i<=n;++i) fa1[i]=fa2[i]=i;
for(re i=1;i<=m1;++i){
int x,y;rd(x);rd(y);merge1(x,y);
}
for(re i=1;i<=m2;++i){
int x,y;rd(x);rd(y);merge2(x,y);
}
for(re i=2;i<=n;++i)
if(find1(i)!=find1(1)&&find2(i)!=find2(1)) qaq[++ans][0]=i,qaq[ans][1]=1,merge1(i,1),merge2(i,1);
for(re i=2;i<=n;++i)
if(find1(i)!=find1(1)) l[++cnt1]=i,merge1(i,1);
else if(find2(i)!=find2(1)) r[++cnt2]=i,merge2(i,1);
wr(ans+min(cnt1,cnt2));puts("");
for(re i=1;i<=ans;++i) wr(qaq[i][0]),putchar(' '),wr(qaq[i][1]),puts("");
for(re i=1;i<=min(cnt1,cnt2);++i) wr(l[i]),putchar(' '),wr(r[i]),puts("");
return 0;
}
// ---------- Main ---------- //