HDU5649 DZY Loves Sorting 线段树

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题意：BC 76 div1 1004 有中文题面

然后奉上官方题解：

这是一道良心的基础数据结构题。

我们二分a[k]的值，假设当前是mid，然后把大于mid的数字标为1，不大于mid的数字标为0。然后对所有操作做完以后检查一下a[k]位置上是0还是1。

因为只有两种值，所以操作还是不难做的。只要用一个线段树，支持区间求和、区间赋值即可。

这样要排序一个区间时只要查询一下里面有几个1和几个0，然后把前半段赋值为0，后半段赋值为1即可（降序的话就是反过来）。

复杂度是O(mlog^2n)。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N=1e5+;
int a[N],b[N],T,n,m,k;
int sum[N<<];
int lz[N<<];
int pushup(int rt){
sum[rt]=sum[rt<<]+sum[rt<<|];
}
void pushdown(int rt,int l,int r){
if(lz[rt]!=-){
int mid=(l+r)>>;
sum[rt<<]=lz[rt]*(mid-l+);
sum[rt<<|]=lz[rt]*(r-mid);
lz[rt<<]=lz[rt<<|]=lz[rt];
lz[rt]=-;
}
}
void build(int rt,int l,int r){
lz[rt]=-;
if(l==r){
sum[rt]=b[l];
return;
}
int mid=(l+r)>>;
build(rt<<,l,mid);
build(rt<<|,mid+,r);
pushup(rt);
}
void update(int rt,int l,int r,int x,int y,int t){
if(x<=l&&r<=y){
sum[rt]=t*(r-l+);
lz[rt]=t;
return;
}
int mid=(l+r)>>;
pushdown(rt,l,r);
if(x<=mid)update(rt<<,l,mid,x,y,t);
if(y>mid)update(rt<<|,mid+,r,x,y,t);
pushup(rt);
}
int query(int rt,int l,int r,int x,int y){
if(x<=l&&r<=y)return sum[rt];
int mid=(l+r)>>;
pushdown(rt,l,r);
if(y<=mid)return query(rt<<,l,mid,x,y);
else if(x>mid)return query(rt<<|,mid+,r,x,y);
return query(rt<<,l,mid,x,y)+query(rt<<|,mid+,r,x,y);
}
struct op{
int x,y,t;
}o[N];
bool check(int x){
for(int i=;i<=n;++i)
b[i]=a[i]>x?:;
build(,,n);
for(int i=;i<=m;++i){
int tmp=query(,,n,o[i].x,o[i].y);
if(!o[i].t){
if(o[i].x<=o[i].y-tmp)update(,,n,o[i].x,o[i].y-tmp,);
if(o[i].y-tmp+<=o[i].y)update(,,n,o[i].y-tmp+,o[i].y,);
}
else{
if(o[i].x<=o[i].x+tmp-)update(,,n,o[i].x,o[i].x+tmp-,);
if(o[i].x+tmp<=o[i].y)update(,,n,o[i].x+tmp,o[i].y,);
}
}
return query(,,n,k,k)==;
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
for(int i=;i<=n;++i)
scanf("%d",&a[i]);
for(int i=;i<=m;++i)
scanf("%d%d%d",&o[i].t,&o[i].x,&o[i].y);
scanf("%d",&k);
int l=,r=n;
while(l<r){
int mid=(l+r)>>;
if(check(mid))l=mid+;
else r=mid;
}
printf("%d\n",(l+r)>>);
}
return ;
}