思維題殺我！現場\(^*2600\)的狀壓DP都會做，\(^*2400\)的思維題就不會了，看來是wtcl/ll
洛谷題目頁面傳送門 & CodeForces題目頁面傳送門
給定\(2\)個\(1\sim n\)的排列\(a,b\)，\(a\)上某些位置會存在炸彈，對于某些位置有炸彈的\(a\)，維護一個集合，初始為空，從左往右掃描整個排列\(a\)，每到一個位置上就將此位置上的數壓進集合，若此位置有炸彈就把集合中最大的數彈出，我們稱最終集合中最大的元素為\(a\)的結果，\(\forall i\in[0,n)\)，求若在\(\forall j\in[1,i],b_i\)這些位置放下炸彈，結果是多少，
\(n\in\left[1,3\times10^5\right]\)，
顯然，依次算每個結果的話，第\(i\)次被彈出的集合是第\(i+1\)次被彈出的集合的子集，即今朝被彈出，永遠就不會復活了，可以推出這\(n\)個結果非嚴格單調遞減，于是我們可以two-pointers，維護目前最大的沒有被彈出的數\(now\)，初始時\(now=n\)，每次算答案時不停地令\(now=now-1\)直到\(now\)沒有被彈出，難點在于如何快速判斷\(now\)是否被彈出，
如果真就一直在想\(now\)被彈出的充要條件，恭喜你，你被魔法殺死了，不難發現一個性質：無論何時，只要你正在考慮判斷\(now\)是否被彈出，那么一定所有\(>now\)的數已經確認被彈出了（因為如果不是那樣，\(now\)自減的程序就會在某個\(>now\)的數處停下），于是我們所考慮的\(now\)被彈出，其實等價于所有\(\geq now\)的數都被彈出，這個東西的充要條件看上去容易探索一點（然鵝的確是這樣），
下面我們來探索所有\(\geq now\)的數都被彈出的充要條件，考慮每個\(\geq now\)的數\(a_x\)，顯然對于每個在\(a_x\)右邊且\(\geq now\)的數\(a_y\)（包括\(a_x\)自己），彈出它們的炸彈在\(a_y\)右邊（包括\(a_y\)位置上），結合\(a_y\)在\(a_x\)右邊可以得到彈出它們的炸彈一定在\(a_x\)右邊（包括\(a_x\)位置上），于是我們得到了所有在\(a_x\)右邊且\(\geq now\)的數（包括\(a_x\)自己）都被彈出的一個很弱的必要條件：\(a_x\)右邊的炸彈（包括\(a_x\)位置上）數量不低于在\(a_x\)右邊且\(\geq now\)的數（包括\(a_x\)自己）的數量，充分性顯然不滿足，
不過，如果將\(\forall x(a_x\geq now)\)，所有在\(a_x\)右邊且\(\geq now\)的數（包括\(a_x\)自己）都被彈出的這么多必要條件合并起來，得到所有\(\geq now\)的數都被彈出的一個必要條件：\(\forall x(a_x\geq now)\)，\(a_x\)右邊的炸彈（包括\(a_x\)位置上的）數量不低于在\(a_x\)右邊且\(\geq now\)的數（包括\(a_x\)自己）的數量，你會發現這個條件似乎很強，于是我們試圖證明它的充分性，然后真就證出來了！
充分性證明（感性）：找到\(a_x=n\)，顯然，\(a_x\)右邊（包括\(a_x\)位置上）的最左邊的炸彈與\(a_x\)匹配，于是我們可以想象將這個炸彈扔掉，并將\(a_x\)扔出排列，兩邊挨緊形成一個新的\(1\sim n-1\)的排列，\(a_x\)左邊所有\(\geq now\)的數右邊\(\geq now\)的數（包括自己）數量\(-1\)，右邊的炸彈（包括自己位置上）數量\(-1\)；\(a_x\)右邊、炸掉\(a_x\)的炸彈左邊（包括炸彈位置上）所有\(\geq now\)的數，右邊\(\geq now\)的數（包括自己）的數量不變，由于\(a_x\)與炸彈之間沒有炸彈，所以它們右邊的炸彈（包括自己位置上）數量至少剩\(a_x\)原來右邊炸彈（包括自己位置上）的數量\(-1\)；炸彈右邊所有\(\geq now\)的數右邊\(\geq now\)的數（包括自己）的數量、炸彈（包括自己位置上）數量都沒變，由此看來條件依然滿足，于是原證明題可以轉化為一個規模\(-1\)的證明題，可以用數學歸納法加以證明，
有了這個結論，接下來就好辦了，設\(a_i\)右邊\(\geq now\)的數（包括\(a_i\)自己）有\(grt_i\)個，右邊的炸彈（包括\(a_i\)位置上）有\(bmb_i\)個，那么\(\forall x(a_x\geq now)\)，\(a_x\)右邊的炸彈（包括\(a_x\)位置上的）數量不低于在\(a_x\)右邊且\(\geq now\)的數（包括\(a_x\)自己）的數量，可以寫成\(\forall x(a_x\geq now),bmb_x\geq grt_x\)，即\(\forall x(a_x\geq now),bmb_x-grt_x\geq0\)，于是我們需要維護\(\forall i\in[1,n],bmb_i-grt_i\)，判斷\(now\)是否被彈出時只需判斷全域最小值是否\(\geq0\)，每當\(now=now-1\)時（初始\(now=n\)時也要）就將位置\(\left(a^{-1}\right)_{now}\)上的\(bmb_{\left(a^{-1}\right)_{now}}-grt_{\left(a^{-1}\right)_{now}}\)激活（即今后算進全域最小值，激活之前懶標記可以幫忙保存\(bmb_{\left(a^{-1}\right)_{now}}-grt_{\left(a^{-1}\right)_{now}}\)）并令\(\forall i\in\left[1,\left(a^{-1}\right)_{now}\right],grt_i=grt_i+1\)，每當新增一個炸彈\(b_x\)就令\(\forall i\in[1,b_x],bmb_i=bmb_i+1\)，這只需要單點修改、區間增加、全域查詢最小值的線段樹即可實作，
下面是AC代碼：
#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=300000;
int n;//排列長度
int a[N+1]/*排列*/,b[N+1]/*炸彈添加順序*/;
int pos[N+1];//pos[i]為數i在a中的位置
struct segtree{//線段樹
struct node{int l,r,mn_dif/*此節點表示的區間內bmb[i]-grt[i]的最小值*/,lz/*藍標記*/;}nd[N<<2];
#define l(p) nd[p].l
#define r(p) nd[p].r
#define mn_dif(p) nd[p].mn_dif
#define lz(p) nd[p].lz
void bld(int l=1,int r=n,int p=1){//建樹
l(p)=l;r(p)=r;mn_dif(p)=inf;/*一開始都是未激活狀態*/lz(p)=0;
if(l==r)return;
int mid=l+r>>1;
bld(l,mid,p<<1);bld(mid+1,r,p<<1|1);
}
void init(){bld();}//初始化
void sprup(int p){mn_dif(p)=min(mn_dif(p<<1),mn_dif(p<<1|1));}//上傳節點資訊
void sprdwn(int p){//下傳懶標記
if(lz(p)){
mn_dif(p<<1)+=lz(p);mn_dif(p<<1|1)+=lz(p);
lz(p<<1)+=lz(p);lz(p<<1|1)+=lz(p);
lz(p)=0;
}
}
void on(int x,int p=1){//激活位置x
if(l(p)==r(p)){mn_dif(p)=lz(p)/*之前的bmb[l(p)]-grt[l(p)]保存在lz(p)里*/;return;}
sprdwn(p);
int mid=l(p)+r(p)>>1;
on(x,p<<1|(x>mid));
sprup(p);
}
void add(int l,int r,int v,int p=1){//區間增加
if(l<=l(p)&&r>=r(p)){mn_dif(p)+=v;lz(p)+=v;return;}
sprdwn(p);
int mid=l(p)+r(p)>>1;
if(l<=mid)add(l,r,v,p<<1);
if(r>mid)add(l,r,v,p<<1|1);
sprup(p);
}
int _mn_dif(){return mn_dif(1);}//全域最小值
}segt;
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i],pos[a[i]]=i;
for(int i=1;i<=n;i++)cin>>b[i];
int now=n;//初始now=n
cout<<now<<" ";//不放炸彈時
segt.init();
segt.on(pos[n]);
segt.add(1,pos[n],-1);//增加一個>=now的數
for(int i=1;i<n;i++){
segt.add(1,b[i],1);//增加一個炸彈
while(segt._mn_dif()>=0/*now被彈出*/){
now--;
segt.on(pos[now]);
segt.add(1,pos[now],-1);//增加一個>=now的數
}
cout<<now<<" ";
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/51094.html
標籤：C++
上一篇：2020年3月21日Benelux Algorithm Programming Contest 2019
下一篇：如何動態宣告一個指標陣列