P2824 [HEOI2016/TJOI2016]排序
题目大意
这个难题是这样子的:给出一个 \(1\) 到 \(n\) 的排列,现在对这个排列序列进行 \(m\) 次局部排序,排序分为两种:
0 l r
表示将区间 \([l,r]\) 的数字升序排序1 l r
表示将区间 \([l,r]\) 的数字降序排序
注意,这里是对下标在区间 \([l,r]\) 内的数排序。
最后询问第 \(q\) 位置上的数字。
分析
离线的写法还是蛮巧妙的。
由于将一个普通的序列排序很慢,是需要nlogn
的时间,所以我们试着把它转化为对01
序列的排序。
我们先来考虑这个问题,如何在logn
的时间完成对01
序列的排序。
我们可以利用线段树,用区间求和和区间赋值完成排序动作。我们假设对区间[l,r]
,其中1
的个数为cnt
。
- 对升序排列,则只需要将
[l,r-cnt]
赋0
,将[r-cnt+1,r]
区间赋1
。 - 对降序排列,则只需要将
[l,l+cnt-1]
赋1
,将[l+cnt,r]
区间赋0
。
接下来,我们说一说如何利用这来解决我们当前这个问题。
一个二分的办法。我们二分答案。我们将原序列中大于等于mid
的值,全部赋值为1
,小于的全部赋值为0
。然后进行操作,如果最后q
位置上是1
的话,说明这个点是可以做答案的。
非常巧妙,其实我们就是二分了答案的范围。
- 如果此时的
mid>ans
,则在排序中,我们的ans
一定排到他对应的位置去时就是个0
。 - 如果此时的
mid<=ans
,则在排序中,我们的ans
一定排到他对应的位置去时就是个1
。
AC_code
#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false); cin.tie(0), cout.tie(0)
using namespace std;
const int N = 1e5 + 10;
struct Node
{
int l,r;
int cnt,cov;
}tr[N<<2];
struct Query
{
int op,l,r;
}OP[N];
int n,m,q;
int p[N];
void pushup(int u)
{
tr[u].cnt = tr[u<<1].cnt + tr[u<<1|1].cnt;
}
void build(int u,int l,int r,int x)
{
tr[u] = {l,r,0,-1};
if(l==r)
{
tr[u].cnt = (p[l]>=x?1:0);
return ;
}
int mid = l + r >> 1;
build(u<<1,l,mid,x),build(u<<1|1,mid+1,r,x);
pushup(u);
}
void pushdown(int u)
{
auto &root = tr[u],&left = tr[u<<1],&right = tr[u<<1|1];
if(root.cov!=-1)
{
left.cov = root.cov;left.cnt = root.cov*(left.r - left.l + 1);
right.cov = root.cov;right.cnt = root.cov*(right.r - right.l + 1);
root.cov = -1;
}
}
void modify(int u,int l,int r,int k)
{
if(tr[u].l>r||tr[u].r<l) return ;
if(l<=tr[u].l&&tr[u].r<=r)
{
tr[u].cov = k;
tr[u].cnt = k*(tr[u].r - tr[u].l + 1);
return ;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
modify(u<<1,l,r,k),modify(u<<1|1,l,r,k);
pushup(u);
}
int query(int u,int l,int r)
{
if(tr[u].r<l||tr[u].l>r) return 0;
if(l<=tr[u].l&&tr[u].r<=r) return tr[u].cnt;
pushdown(u);
return query(u<<1,l,r) + query(u<<1|1,l,r);
}
bool check(int mid)
{
build(1,1,n,mid);
for(int i=1;i<=m;i++)
{
auto [op,l,r] = OP[i];
int cnt = query(1,l,r);
if(!op)
{
modify(1,r-cnt+1,r,1);
modify(1,l,r-cnt,0);
}
else
{
modify(1,l,l+cnt-1,1);
modify(1,l+cnt,r,0);
}
}
return query(1,q,q);
}
int main()
{
ios;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>p[i];
for(int i=1;i<=m;i++)
{
int op,l,r;cin>>op>>l>>r;
OP[i] = {op,l,r};
}
cin>>q;
int l = 1,r = n;
while(l<r)
{
int mid = l + r + 1>> 1;
if(check(mid)) l = mid;
else r = mid - 1;
}
cout<<l<<'\n';
return 0;
}
标签:cnt,int,P2824,mid,序列,TJOI2016,HEOI2016,区间,排序
From: https://www.cnblogs.com/aitejiu/p/16863036.html