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
這道題這是太神了,在zcg學長的推薦下寫了這道題,思路就是二分答案和線段樹進行驗證,對于這顆線段樹,每次二分的時候重建立樹,每個葉子節點的值為a[pos]是否大于二分出來的那個數,如果大于等于的話為1,否則為0.那麼操作0就代表把區間[l,r]裡面的1全部放到這個區間的後面,而操作1則是放到前面,用線段樹維護sum值再用lazy标記就好了
code:
#include <bits/stdc++.h>
#define MAXN 100005
using namespace std;
int Judge,a[MAXN],n,m,p,Ans;
template<typename _t>
inline _t read(){
_t x=0;
int f=1;
char ch=getchar();
for(;ch>'9'||ch<'0';ch=getchar())if(ch=='-')f=-f;
for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+(ch^48);
return x*f;
}
struct node{
node *ls,*rs;
int sum,set,l,r;
inline int __ls(){return ls?ls->sum:0;}
inline int __rs(){return rs?rs->sum:0;}
void Maintain(){
sum=__ls()+__rs();
}
void push_down(){
if(set==-1)return;
int m=l+r>>1;
if(ls){
ls->set=set;
ls->sum=(m-l+1)*set;
}
if(rs){
rs->set=set;
rs->sum=(r-m)*set;
}
set=-1;
}
node(){
ls=rs=NULL;
sum=0;set=-1;
}
}*root;
void build(node *&o,int l,int r){
if(!o)o=new node();
o->l=l;o->r=r;
o->set=-1;
if(l==r){
o->sum=(a[l]>=Judge);
return;
}
int m=l+r>>1;
build(o->ls,l,m);
build(o->rs,m+1,r);
o->Maintain();
}
void Update(node *o,int l,int r,int val){
if(l>r)return;
o->push_down();
if(l<=o->l&&o->r<=r){
o->set=val;
o->sum=val*(o->r-o->l+1);
return;
}
int m=o->l+o->r>>1;
if(l<=m)Update(o->ls,l,r,val);
if(m<r)Update(o->rs,l,r,val);
o->Maintain();
}
int Query(node *o,int l,int r){
o->push_down();
if(l<=o->l&&o->r<=r)return o->sum;
int m=o->l+o->r>>1,ans=0;
if(l<=m)ans+=Query(o->ls,l,r);
if(m<r)ans+=Query(o->rs,l,r);
return ans;
}
struct Operation{
int op,l,r;
void init(){
op=read<int>();
l=read<int>();
r=read<int>();
}
}c[MAXN];
int main(){
n=read<int>();m=read<int>();
int maxn = -0x3f3f3f3f;
for(int i=1;i<=n;i++)a[i]=read<int>(),maxn=max(maxn,a[i]);
for(int i=1;i<=m;i++)c[i].init();
p=read<int>();
int l=1,r=maxn;
while(l<=r){
Judge=l+r>>1;
build(root,1,n);
for(int i=1;i<=m;i++){
if(c[i].op==0){
int sum = Query(root,c[i].l,c[i].r);
Update(root,c[i].r-sum+1,c[i].r,1);
Update(root,c[i].l,c[i].r-sum,0);
}
else{
int sum = Query(root,c[i].l,c[i].r);
Update(root,c[i].l+sum,c[i].r,0);
Update(root,c[i].l,c[i].l+sum-1,1);
}
}
int ans = Query(root,p,p);
if(ans)Ans=Judge,l=Judge+1;
else r=Judge-1;
}
printf("%d\n",Ans);
}