題目描述

在2016年，佳媛姐姐喜歡上了數(shù)字序列。因而他經(jīng)常研究關(guān)于序列的一些奇奇怪怪的問(wèn)題，現(xiàn)在他在研究一個(gè)難題，需要你來(lái)幫助他。這個(gè)難題是這樣子的：給出一個(gè)1到n的全排列，現(xiàn)在對(duì)這個(gè)全排列序列進(jìn)行m次局部排序，排序分為兩種：1:(0,l,r)表示將區(qū)間[l,r]的數(shù)字升序排序2:(1,l,r)表示將區(qū)間[l,r]的數(shù)字降序排序最后詢問(wèn)第q位置上的數(shù)字。

輸入輸出格式

輸入格式：

輸入數(shù)據(jù)的第一行為兩個(gè)整數(shù)n和m。n表示序列的長(zhǎng)度，m表示局部排序的次數(shù)。1 <= n, m <= 10^5第二行為n個(gè)整數(shù)，表示1到n的一個(gè)全排列。接下來(lái)輸入m行，每一行有三個(gè)整數(shù)op, l, r, op為0代表升序排序，op為1代表降序排序, l, r 表示排序的區(qū)間。最后輸入一個(gè)整數(shù)q，q表示排序完之后詢問(wèn)的位置, 1 <= q <= n。1 <= n <= 10^5，1 <= m <= 10^5

輸出格式：

輸出數(shù)據(jù)僅有一行，一個(gè)整數(shù)，表示按照順序?qū)⑷康牟糠峙判蚪Y(jié)束后第q位置上的數(shù)字。

輸入輸出樣例

輸入樣例#1：
6 3 1 6 2 5 3 4 0 1 4 1 3 6 0 2 4 3 輸出樣例#1：
5

說(shuō)明

河北省選2016第一天第二題。原題的時(shí)限為6s，但是洛谷上是1s，所以洛谷的數(shù)據(jù)中，對(duì)于30%的數(shù)據(jù)，有 n,m<=1000,對(duì)于100%的數(shù)據(jù)，有 n,m<=30000

?

?

?

　　首先先聲明一下，方法與Drench大佬的差不多，此篇題解填了一些解釋，讓代碼更容易理解。（P.S.：我的代碼不知道為啥在主站會(huì)T第10個(gè)點(diǎn)，在大牛分站交過(guò)了，能有大佬想到一些優(yōu)化的方法當(dāng)然是更好，這題解主要是介紹思路和代碼含義）

SOLUTION：

First：主體思路：二分答案+線段樹(shù)操作

Second：代碼完成思路

　　1.讀入，存儲(chǔ)數(shù)值

　　2.二分第Q個(gè)值的答案

　　3.線段樹(shù)的操作

　　　　1)建樹(shù) 2)進(jìn)行m次操作 3)找到第q個(gè)點(diǎn)二分答案

　　4.二分left 和 right的更改

Third：線段樹(shù)操作方法及能實(shí)現(xiàn)的原因

　　1.二分出q，建樹(shù)時(shí)大于等于q葉子節(jié)點(diǎn)為1，反之為0，然后利用線段樹(shù)處理的sum（和）。

　　2.對(duì)于第i步修改操作中，區(qū)間l-r中的和及大于等于q的個(gè)數(shù)(1)，r-l+1為區(qū)間數(shù)的個(gè)數(shù)，求差就是小于q的個(gè)數(shù)(0)。

　　3.求出l-r區(qū)間num0與num1個(gè)數(shù)后，若從小到大，則將l-(l+num0-1)賦值為0，(l+num0-r)賦值為1

　　 ? 反之，則將l-(l+num1-1)賦值為1，(l+num1-r)賦值為0

　　4.上述步驟重復(fù)m次后，就可以去查詢第Q個(gè)數(shù)，如果為1說(shuō)明二分出來(lái)的q大于等于答案，如果為0說(shuō)明二分出來(lái)的q小于q

?

下面就是我的代碼了，代碼中有一些注釋：

//It is coded by Ning_Mew on 10.17 #include<cstdio> #include<iostream> #include<cmath> #include<algorithm> #include<cstring> using namespace std; int read(){//讀入優(yōu)化int x=0;char ch=getchar();while(ch<'0'||ch>'9')ch=getchar();while(ch>='0'&&ch<='9')x=(x*10)+ch-'0',ch=getchar();return x; } int n,m,q,top=0,tail,mid; struct Operation{int type,l,r; }ope[100000+10];//儲(chǔ)存更改操作 struct Node{int l,r,sum,lazy; }node[400000+10];//線段樹(shù)儲(chǔ)存 int a[100000+10];//儲(chǔ)存每個(gè)值 void build(int num,int nl,int nr){//建樹(shù)if(nl==nr){node[num].l=nl; node[num].r=nr;if(a[nl]>=mid)node[num].sum=1;else node[num].sum=0;//對(duì)應(yīng)Third中的第一點(diǎn)return;}int nmid=(nl+nr)/2;build(num*2,nl,nmid);build(num*2+1,nmid+1,nr);node[num].l=nl; node[num].r=nr;node[num].sum=(node[num*2].sum+node[num*2+1].sum);return; } void pushdown(int num,int nl,int nr){//下放lazy操作if(node[num].lazy!=-1){node[num*2].lazy=node[num].lazy;node[num*2+1].lazy=node[num].lazy;//因?yàn)閘azy是將這個(gè)節(jié)點(diǎn)中的數(shù)全部更改為0或1，所以lazy是直接被覆蓋而不是+=node[num*2].sum=node[num].lazy*(node[num*2].r-node[num*2].l+1);node[num*2+1].sum=node[num].lazy*(node[num*2+1].r-node[num*2+1].l+1);//同樣因?yàn)槭侨桓?#xff0c;所以直接覆蓋node[num].lazy=-1;}return; } int count(int num,int nl,int nr,int ql,int qr){//求區(qū)間和if(qr<nl||nr<ql)return 0;if(ql<=nl&&nr<=qr){return node[num].sum;}pushdown(num,nl,nr);int nmid=(nl+nr)/2;return count(num*2,nl,nmid,ql,qr)+count(num*2+1,nmid+1,nr,ql,qr); } void change(int num,int nl,int nr,int ql,int qr,int add){//區(qū)間更改if(qr<nl||nr<ql||ql>qr)return;if(ql<=nl&&nr<=qr){node[num].sum=add*(node[num].r-node[num].l+1);//被防止了lazy的點(diǎn)本身應(yīng)已被更改，下次就只用下放lazy了node[num].lazy=add;return;}pushdown(num,nl,nr);int nmid=(nl+nr)/2;change(num*2,nl,nmid,ql,qr,add);change(num*2+1,nmid+1,nr,ql,qr,add);node[num].sum=node[num*2].sum+node[num*2+1].sum;//兩個(gè)兒子節(jié)點(diǎn)已更改所以更新此節(jié)點(diǎn)sum值return; } bool judge(){//檢查q值build(1,1,n);for(int i=1;i<=4*n+1;i++)node[i].lazy=-1;for(int i=1;i<=m;i++){int ll=ope[i].l,rr=ope[i].r;int num1=count(1,1,n,ll,rr),num0;num0=rr-ll+1-num1;if(ope[i].type==0){//對(duì)應(yīng)Third 3點(diǎn)change(1,1,n,ll,ll+num0-1,0);change(1,1,n,ll+num0,rr,1);}else{change(1,1,n,ll,ll+num1-1,1);change(1,1,n,ll+num1,rr,0);}}if(count(1,1,n,q,q))return true;//1-->truereturn false;//0-->false } int main(){n=read();m=read();for(int i=1;i<=n;i++){a[i]=read();}for(int i=1;i<=m;i++){ope[i].type=read();ope[i].l=read();ope[i].r=read();}q=read();top=0;tail=n+1;do{mid=(top+tail)/2;if(judge()){top=mid;}else {tail=mid;}}while(top<tail-1);cout<<top; return 0; }

題解就寫(xiě)到這啦，好好理解還是不難的～

轉(zhuǎn)載于:https://www.cnblogs.com/Ning-Mew/p/7684935.html

總結(jié)

以上是生活随笔為你收集整理的【题解】 [HEOI2016]排序题解 （二分答案，线段树）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。