Description
在2016年,佳媛姐姐喜欢上了数字序列。因而他经常研究关于序列的一些奇奇怪怪的问题,现在他在研究一个难题
,需要你来帮助他。这个难题是这样子的:给出一个1到n的全排列,现在对这个全排列序列进行m次局部排序,排
序分为两种:1:(0,l,r)表示将区间[l,r]的数字升序排序2:(1,l,r)表示将区间[l,r]的数字降序排序最后询问第q
位置上的数字。
1 <= n, m <= 10^5
Solution
可以二分一个答案,然后把数字分成大于mid和小于mid的两部分,这样就能用线段树区间维护排序操作了
感谢loj的数据
Code
#include <stdio.h>
#include <string.h>
#define rep(i,st,ed) for (int i=st;i<=ed;++i)
#define fill(x,t) memset(x,t,sizeof(x))
const int N=;
int lazy[N<<],c[N<<];
int opt[N][],a[N];
int n,m,pos;
int read() {
int x=,v=; char ch=getchar();
for (;ch<'0'||ch>'9';v=(ch=='-')?(-):(v),ch=getchar());
for (;ch<='9'&&ch>='0';x=x*+ch-'0',ch=getchar());
return x*v;
}
void push_down(int now,int tl,int tr) {
if (lazy[now]==-) return ;
int mid=(tl+tr)>>;
lazy[now<<]=lazy[now<<|]=lazy[now];
c[now<<]=(mid-tl+)*lazy[now];
c[now<<|]=(tr-mid)*lazy[now];
lazy[now]=-;
}
void modify(int now,int tl,int tr,int l,int r,int v) {
if (l>r) return ;
if (tl==l&&tr==r) {
lazy[now]=v;
c[now]=(r-l+)*v;
return ;
}
push_down(now,tl,tr);
int mid=(tl+tr)>>;
if (r<=mid) modify(now<<,tl,mid,l,r,v);
else if (l>mid) modify(now<<|,mid+,tr,l,r,v);
else {
modify(now<<,tl,mid,l,mid,v);
modify(now<<|,mid+,tr,mid+,r,v);
}
c[now]=c[now<<]+c[now<<|];
}
int query(int now,int tl,int tr,int l,int r) {
if (tl==l&&tr==r) return c[now];
push_down(now,tl,tr);
int mid=(tl+tr)>>;
if (r<=mid) return query(now<<,tl,mid,l,r);
else if (l>mid) return query(now<<|,mid+,tr,l,r);
else return query(now<<,tl,mid,l,mid)+query(now<<|,mid+,tr,mid+,r);
}
int solve(int now) {
fill(c,);
fill(lazy,-);
rep(i,,n) modify(,,n,i,i,a[i]>=now);
rep(i,,m) {
int ret=query(,,n,opt[i][],opt[i][]);
if (opt[i][]==) {
modify(,,n,opt[i][],opt[i][]-ret,);
modify(,,n,opt[i][]-ret+,opt[i][],);
// printf("%d %d %d %d\n",opt[i][1],opt[i][2]-ret,opt[i][2]-ret+1,opt[i][2]);
} else {
modify(,,n,opt[i][],opt[i][]+ret-,);
modify(,,n,opt[i][]+ret,opt[i][],);
// printf("%d %d %d %d\n",opt[i][1],opt[i][1]+ret-1,opt[i][1]+ret,opt[i][2]);
}
}
return query(,,n,pos,pos);
}
int main(void) {
n=read(); m=read();
rep(i,,n) a[i]=read();
rep(i,,m) opt[i][]=read(),opt[i][]=read(),opt[i][]=read();
pos=read();
int ans=;
int l=,r=n;
while (l<=r) {
int mid=(l+r)>>;
if (solve(mid)) l=mid+,ans=mid;
else r=mid-;
}
printf("%d\n", ans);
return ;
}