Description
在2016年,佳媛姐姐喜歡上了數字序列。因而他經常研究關于序列的一些奇奇怪怪的問題,現在他在研究一個難題
,需要你來幫助他。這個難題是這樣子的:給出一個1到n的全排列,現在對這個全排列序列進行m次局部排序,排
序分為兩種:1:(0,l,r)表示将區間[l,r]的數字升序排序2:(1,l,r)表示将區間[l,r]的數字降序排序最後詢問第q
位置上的數字。
Input
輸入資料的第一行為兩個整數n和m。n表示序列的長度,m表示局部排序的次數。1 <= n, m <= 10^5第二行為n個整
數,表示1到n的一個全排列。接下來輸入m行,每一行有三個整數op, l, r, op為0代表升序排序,op為1代表降序
排序, l, r 表示排序的區間。最後輸入一個整數q,q表示排序完之後詢問的位置, 1 <= q <= n。1 <= n <= 10^5
,1 <= m <= 10^5
Output
輸出資料僅有一行,一個整數,表示按照順序将全部的部分排序結束後第q位置上的數字。
Sample Input
6 3
1 6 2 5 3 4
0 1 4
1 3 6
0 2 4
3
Sample Output
5
題解
ZJOI2017老師講課例題,随手A一下。
二分答案,判斷排序之後的A[q]與mid的關系,
先把原序列中大于mid的數标記為1,否則标記為0。
對01序列進行排序,可以通過線段樹完成計數排序,
需要實作區間求和、區間指派。
最後如果A[q]=1,說明原序列中A[q]>mid ,
否則原序列中A[q] mid 。
求最小的mid滿足排序後的序列中A[q] = 0。
複雜度O (nlog^2n)。
代碼
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#define inf 0x7fffffff
#define N 100005
#define ll long long
int op[N],x[N],y[N],a[N],t[N];
int sum[*N],lazy[*N];
int n,m,Q;
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void update(int k)
{
sum[k]=sum[k*2]+sum[k*2+];
}
void pushdown(int k,int l,int r)
{
if (l==r) return;
int mid=(l+r)>>,t=lazy[k];
lazy[k]=-;lazy[k*2]=t;lazy[k*2+]=t;
sum[k*2]=(mid-l+)*t;sum[k*2+]=(r-mid)*t;
}
void change(int k,int l,int r,int x,int y,int z)
{
if (lazy[k]!=-) pushdown(k,l,r);
if (l==x&&r==y)
{
lazy[k]=z;
sum[k]=(r-l+)*z;
return;
}
int mid=(l+r)>>;
if (y<=mid) change(k*2,l,mid,x,y,z);
if (x>mid) change(k*2+,mid+,r,x,y,z);
if (x<=mid&&y>mid)
{
change(k*2,l,mid,x,mid,z);
change(k*2+,mid+,r,mid+,y,z);
}
update(k);
}
int query(int k,int l,int r,int x,int y)
{
if (lazy[k]!=-) pushdown(k,l,r);
if (l==x&&r==y) return sum[k];
int mid=(l+r)>>;
if (y<=mid) return query(k*2,l,mid,x,y);
if (x>mid) return query(k*2+,mid+,r,x,y);
return query(k*2,l,mid,x,mid)+query(k*2+,mid+,r,mid+,y);
}
bool check(int mid)
{
memset(lazy,-,sizeof(lazy));
memset(sum,,sizeof(sum));
for (int i=;i<=n;i++)
{
t[i]=(a[i]>mid);
if (t[i]) change(,,n,i,i,);
}
for (int i=;i<=m;i++)
{
int num=query(,,n,x[i],y[i]);
if (num==) continue;
if (num==y[i]-x[i]+) continue;
change(,,n,x[i],y[i],);
if (op[i])
{
change(,,n,x[i],x[i]+num-,);
}
else
{
change(,,n,y[i]-num+,y[i],);
}
}
int num=query(,,n,Q,Q);
return !num;
}
int main()
{
n=read();m=read();
for (int i=;i<=n;i++)
{
a[i]=read();
}
for (int i=;i<=m;i++)
{
op[i]=read();x[i]=read();y[i]=read();
}
Q=read();
int l=,r=n;
while (l!=r)
{
int mid=(l+r)>>;
if (check(mid)) r=mid;else l=mid+;
}
cout<<l<<endl;
return ;
}