想了一会怎么处理区间排序。
但是发现很难实现,但是区间覆盖还是比较拿手的。
貌似二分答案,然后排序转覆盖就可以了?
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<vector>
#include<algorithm>
#define gc getchar()
#define ll long long
#define eps 1e-8
#define ld long double
#define ull unsigned long long
using namespace std;
const int N=1e5+5,M=12e5+5;
template<class o>
inline void qr(o &x)
{
x=0;char c=gc;int f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
x*=f;
}
template<class o>
void qw(o x)
{
if(x<0)putchar('-'),x=-x;
if(x/10)qw(x/10);
putchar(x%10+48);
}
int bz,a[N];
struct SGT{bool ex;int lz,s,l,r;}t[N<<3];
inline void update(int p){t[p].ex=t[p<<1].ex|t[p<<1|1].ex;t[p].s=t[p<<1].s+t[p<<1|1].s;}
inline void pushdown(int p)
{
if(t[p].lz!=-1)
{
t[p<<1].ex=t[p<<1].lz=t[p].lz;
t[p<<1].s=(t[p<<1].r-t[p<<1].l+1)*t[p].lz;
t[p<<1|1].ex=t[p<<1|1].lz=t[p].lz;
t[p<<1|1].s=(t[p<<1|1].r-t[p<<1|1].l+1)*t[p].lz;
t[p].lz=-1;
}
}
void build(int p,int l,int r)
{
t[p].l=l,t[p].r=r;t[p].lz=-1;
if(l==r){t[p].s=t[p].ex=a[l]>=bz;return ;}
int mid=l+r>>1;
build(p<<1,l,mid);build(p<<1|1,mid+1,r);
update(p);
}
void change(int p,int l,int r,int L,int R,int lz)
{
if(L>R)return ;
if(L<=l&&R>=r){t[p].lz=lz;t[p].ex=lz;t[p].s=(r-l+1)*lz;return ;}
int mid=l+r>>1;pushdown(p);
if(L<=mid)change(p<<1,l,mid,L,R,lz);
if(R>mid)change(p<<1|1,mid+1,r,L,R,lz);
update(p);
}
int query(int p,int l,int r,int L,int R)
{
if(L<=l&&R>=r)return t[p].s;
int mid=l+r>>1,val=0;pushdown(p);
if(L<=mid)val+=query(p<<1,l,mid,L,R);
if(R>mid)val+=query(p<<1|1,mid+1,r,L,R);
return val;
}
bool query(int p,int l,int r,int pos)
{
if(!t[p].ex)return 0;
if(l==r)return t[p].ex;
int mid=l+r>>1;pushdown(p);
if(pos<=mid)return query(p<<1,l,mid,pos);
return query(p<<1|1,mid+1,r,pos);
}
int n,m,q;
struct Query{int l,r,op;}Q[N];
bool check(int mid)
{
bz=mid;
build(1,1,n);
for(int i=1;i<=m;i++)
{
int l=Q[i].l,r=Q[i].r,sum=query(1,1,n,l,r);
if(Q[i].op)change(1,1,n,l,l+sum-1,1),change(1,1,n,l+sum,r,0);
else change(1,1,n,l,r-sum,0),change(1,1,n,r-sum+1,r,1);
}
return query(1,1,n,q);
}
int main()
{
qr(n);qr(m);
for(int i=1;i<=n;i++)qr(a[i]);
for(int i=1;i<=m;i++)qr(Q[i].op),qr(Q[i].l),qr(Q[i].r);
qr(q);
int l=1,r=n;
while(l<r)
{
int mid=l+r+1>>1;
if(check(mid))l=mid;
else r=mid-1;
}
qw(l);puts("");
return 0;
}
最后一次更新于2020-04-17
0 条评论