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
s o l u t i o n solution solution:
這題有兩種做法，複雜度與思路都不同，但都是比較經典的做法。
做法①：
想法比較暴力
初始對每個點開一棵權值線段樹
每次詢問的時候，把 [ l , r ] [l,r] [l,r]兩端的塊分裂，再把區間内所有的線段樹合并
最後暴力查詢一下，用 s e t set set維護所有的塊
複雜度？
可以發現，我們建立的塊是 O ( n ) O(n) O(n)的
那麼我們合并以及分裂的操作涉及的塊不難發現也是 O ( n ) O(n) O(n)的
總複雜度 O ( n l o g n ) O(nlogn) O(nlogn)
分裂的時候還要分塊的種類，本人使用了 m a p map map
代碼細節較複雜。
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i = j;i <= k;++i)
#define repp(i,j,k) for(int i = j;i >= k;--i)
#define rept(i,x) for(int i = linkk[x];i;i = e[i].n)
#define P pair<int,int>
#define Pil pair<int,ll>
#define Pli pair<ll,int>
#define Pll pair<ll,ll>
#define pb push_back
#define pc putchar
#define mp make_pair
#define file(k) memset(k,0,sizeof(k))
#define ll long long
#define hash Hash
#define fr first
#define se second
#define IT set<P>::iterator
int rd()
{
int num = 0;char c = getchar();bool flag = true;
while(c < '0'||c > '9') {if(c == '-') flag = false;c = getchar();}
while(c >= '0' && c <= '9') num = num*10+c-48,c = getchar();
if(flag) return num;else return -num;
}
int n,m;
int a[101000];
set<P>h;
set<P>::iterator it;
map<P,int>hash;
map<P,int>op;
namespace tree
{
stack<int>st;
int cnt_id = 0;
struct Tree{int ls,rs,num;}tr[10100000];
int New(){int x;if(!st.empty()) x=st.top(),st.pop();else x=++cnt_id;return x;}
void free(int x){tr[x].ls = tr[x].rs = tr[x].num = 0;st.push(x);}
void update(int rt){tr[rt].num = tr[tr[rt].ls].num + tr[tr[rt].rs].num;}
void build(int &rt,int l,int r,int v)
{
rt = New();tr[rt].num++;
if(l == r) return;
int mid = l+r>>1;
if(v <= mid) build(tr[rt].ls,l,mid,v);
else build(tr[rt].rs,mid+1,r,v);
}
int merge(int x,int y)
{
if(!x) return y;
if(!y) return x;
int t = New();
tr[t].ls = merge(tr[x].ls,tr[y].ls);
tr[t].rs = merge(tr[x].rs,tr[y].rs);
tr[t].num = tr[tr[t].ls].num + tr[tr[t].rs].num;
free(x);free(y);
return t;
}
void split1(int &x,int y,int k)
{//分裂出前k大
x = New();
if(k > tr[tr[y].rs].num) split1(tr[x].ls,tr[y].ls,k-tr[tr[y].rs].num),swap(tr[x].rs,tr[y].rs);
else if(k == tr[tr[y].rs].num) swap(tr[x].rs,tr[y].rs);
else split1(tr[x].rs,tr[y].rs,k);
update(x);update(y);
}
void split2(int &x,int y,int k)
{//分裂出前k小
x = New();
if(k > tr[tr[y].ls].num) split2(tr[x].rs,tr[y].rs,k-tr[tr[y].ls].num),swap(tr[x].ls,tr[y].ls);
else if(k == tr[tr[y].ls].num) swap(tr[x].ls,tr[y].ls);
else split2(tr[x].ls,tr[y].ls,k);
update(x);update(y);
}
int query(int rt,int l,int r,int k)
{//第k小
if(l == r) return l;
int mid = l+r>>1;
if(k <= tr[tr[rt].ls].num) return query(tr[rt].ls,l,mid,k);
else return query(tr[rt].rs,mid+1,r,k-tr[tr[rt].ls].num);
}
}using namespace tree;
IT fuckit(IT it,int l,int r)
{
int _l = it->fr,_r = it->se,to,_rt = hash[mp(_l,_r)],_op = op[mp(_l,_r)];
//_l l r _r -> [_l,l-1] [l,_r]
if(_op == 1) split1(to,_rt,l-_l); else split2(to,_rt,l-_l);
hash[mp(_l,l-1)] = to; op[mp(_l,l-1)] = _op;
hash[mp(l,_r) ] = _rt; op[mp(l,_r) ] = _op;
hash.erase(mp(_l,_r)); op.erase(mp(_l,_r));
h.erase(h.lower_bound(mp(_l,_r))); h.insert(mp(_l,l-1)); h.insert(mp(l,_r));
it = h.lower_bound(mp(l,_r));
return it;
}
int work(int k,int l,int r)
{
int tmp = tree::New();
while(1)
{
it = h.lower_bound(mp(l,0));
if(it == h.end() || it->second > r) break;
tmp = tree::merge(tmp,hash[(*it)]);
hash.erase(mp(it->first,it->second));
op.erase(mp(it->fr,it->se));
h.erase(it);
}//合并所有子區間
it = h.lower_bound(mp(l,0));
if((it == h.end() || it->first > r) && it != h.begin())
{
it--;
if(it->first < l && it->second > r) it = fuckit(it,l,r);
else it++;
}
if(it != h.end() && it->first <= r)
{
int to;
int _op = op[mp(it->fr,it->se)],_l = it->fr,_r = it->se,_rt = hash[mp(_l,_r)];
if(_op == 1) split1(to,_rt,r-_l+1);
else split2(to,_rt,r-_l+1);
hash[mp(r+1,_r)] = _rt; op[mp(r+1,_r)] = _op;
op.erase(mp(_l,_r)); hash.erase(mp(_l,_r));
h.insert(mp(r+1,_r)); h.erase(it);
tmp = tree::merge(tmp,to);
}//處理右端區間
it = h.lower_bound(mp(l,0));
if(it == h.begin());
else
{
it--;
if(it->second >= l)
{
if(it->second > r) it = fuckit(it,l,r);
int to;
int _l = it->fr,_r = it->se,_op = op[mp(_l,_r)],_rt = hash[mp(_l,_r)];
if(_op == 1) split2(to,_rt,_r-l+1);
else split1(to,_rt,_r-l+1);
hash[mp(_l,l-1)] = _rt; op[mp(_l,l-1)] = _op;
op.erase(mp(_l,_r)); hash.erase(mp(_l,_r));
h.insert(mp(_l,l-1)); h.erase(it);
tmp = tree::merge(tmp,to);
}
}//處理左端區間
h.insert(mp(l,r)); op[mp(l,r)] = k; hash[mp(l,r)] = tmp;
}
void init()
{
n = rd();m = rd();
rep(i,1,n) a[i] = rd();
rep(i,1,n) h.insert(mp(i,i)),tree::build(hash[mp(i,i)],1,n,a[i]);
rep(i,1,m)
{
int k = rd(),l = rd(),r = rd();
work(k,l,r);
}
int pl = rd();
for(it = h.begin();it != h.end();it++) if(pl >= it->fr && pl <= it->se) break;
int _rt = hash[mp(it->fr,it->se)],_op = op[mp(it->fr,it->se)],l = it->fr,r = it->se;
printf("%d\n",tree::query(hash[mp(it->fr,it->se)],1,n, _op?r-pl+1:pl-l+1 ));
}
int main()
{
init();
return 0;
}
做法②：
直接對數字排序不好維護。
對01的排序非常好維護
考慮二分
二分一個答案 m i d mid mid後把 ≥ m i d \geq mid ≥mid的值設為1， < m i d <mid <mid的值設為0，剩下維護的操作就隻涉及區間修改，區間和查詢了
複雜度 O ( n l o g 2 n ) O(nlog^2n) O(nlog2n)
代碼簡短
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i = j;i <= k;++i)
#define repp(i,j,k) for(int i = j;i >= k;--i)
#define rept(i,x) for(int i = linkk[x];i;i = e[i].n)
#define P pair<int,int>
#define Pil pair<int,ll>
#define Pli pair<ll,int>
#define Pll pair<ll,ll>
#define pb push_back
#define pc putchar
#define mp make_pair
#define file(k) memset(k,0,sizeof(k))
#define ll long long
#define ls rt<<1
#define rs rt<<1|1
int rd()
{
int num = 0;char c = getchar();bool flag = true;
while(c < '0'||c > '9') {if(c == '-') flag = false;c = getchar();}
while(c >= '0' && c <= '9') num = num*10+c-48,c = getchar();
if(flag) return num;else return -num;
}
int n,m;
int a[101000],b[101000];
int num[401000],det[401000];
struct data{int op,l,r;}q[101000];
void pushdown(int rt,int l,int r)
{
int mid = l+r>>1;
if(det[rt] == 1)
num[ls] = mid-l+1,
num[rs] = r-mid,
det[ls] = det[rs] = 1,
det[rt] = 0;
else if(det[rt] == 2) num[ls] = num[rs] = 0,det[ls] = det[rs] = 2,det[rt] = 0;
}
void build(int rt,int l,int r)
{
if(l == r)
{
num[rt] = b[l];
return;
}
int mid = l+r>>1;
build(ls,l,mid);build(rs,mid+1,r);
det[rt] = 0;num[rt] = num[ls] + num[rs];
}
int query(int rt,int l,int r,int x,int y)
{
if(y < l || x > r) return 0;
if(x <= l && r <= y) return num[rt];
int mid = l+r>>1;
pushdown(rt,l,r);
return query(ls,l,mid,x,y)+query(rs,mid+1,r,x,y);
}
void change(int rt,int l,int r,int x,int y,int v)
{
if(x <= l && r <= y)
{
det[rt] = 2-v;
num[rt] = (r-l+1) * v;
return;
}
pushdown(rt,l,r);
int mid = l+r>>1;
if(mid >= x) change(ls,l,mid,x,y,v);
if(mid < y) change(rs,mid+1,r,x,y,v);
num[rt] = num[ls] + num[rs];
}
void work()
{
build(1,1,n);
rep(i,1,m)
{
int op = q[i].op,l = q[i].l,r = q[i].r;
int num1 = query(1,1,n,l,r);
if(op == 1)
{
if(num1>0) change(1,1,n,l,l+num1-1,1);
if(l+num1<=r) change(1,1,n,l+num1,r,0);
}
else
{
if(r-num1>=l) change(1,1,n,l,r-num1,0);
if(num1>0) change(1,1,n,r-num1+1,r,1);
}
}
}
int main()
{
n = rd();m = rd();
rep(i,1,n) a[i] = rd();
rep(i,1,m) q[i].op = rd(),q[i].l = rd(),q[i].r = rd();
int k = rd();
int l = 0,r = n+1;
while(l+1<r)
{
int mid = l+r>>1;
rep(i,1,n) b[i] = a[i] > mid;
work();
if(query(1,1,n,k,k) == 1) l = mid;
else r = mid;
}
printf("%d\n",r);
return 0;
}
![UVALive 7141 BombX[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)