P11453 [USACO24DEC] Deforestation S
閑聊：多測一定要清空！！！
以及，聽說本題有九倍經驗，主要針對差分約束。
本題的做法很多，最主要的一個是差分約束。這里我們介紹另一種做法——并查集+樹狀數組。（雖然這個做法有點……難評，但我認為它最大的優勢是快，我現在是896ms，第二面榜）
首先本題值域太大了，我們要先對位置進行離散化（查詢的區間和樹的位置都離散化）。接著我們可以對原來的 \(n\) 棵樹的位置排序（雖然這沒必要）。最后我們把原問題轉化為最少保留多少棵樹。
然后我們就得到了一坨形似 CSP-S 2024 T2 的東西。我們按右端點從小到大排序，然后分別處理每個區間。
這里就體現本題的貪心標簽了：對于一個區間而言，如果當前它的限制還未被滿足，盡量往右邊選擇保留的樹一定是不劣的，因為它的上一個區間已經選樹完成了不用管，但是下一個區間沒考慮完，越往右選樹，越有可能使這棵樹貢獻到下面的區間。
或者說，如果你該區間的選樹方案里存在一個靠右的樹未被選擇，顯然你把它選上，并去掉最靠左邊的樹，這樣既能滿足該區間的約束，下面的區間要選的樹也有可能減少，何樂而不為呢？
這樣我們的大體思路就有了：離散化+區間排序+枚舉區間求貢獻。
但是如果從右往左直接掃的話，經過構造有可能會T飛（本人沒試過，如有不對還請斧正）。這時我就想起來了一個套路：用并查集維護最靠右的未被選樹的位置。具體來說，我們用 \(fa_i\) 表示 \(i\) 左側最靠近 \(i\) 的沒被選樹的位置。初始時 \(fa_i=i\)。
這個套路還蠻常見的，但總之當 \(i\) 位置選上樹后，我們令 \(fa_i=i-1\)，查找某個點前一個未被選樹的位置時，直接跑正常的路徑壓縮即可。
至于樹狀數組，這個主要是用來判斷該區間是否已經滿足限制用的。當我們加入一個位置的全部樹時，就讓當前這個離散化位置在樹狀數組上加上該位置樹的個數，進入下一個區間時直接正常區間查詢即可。
由于我們最多會種 \(n\) 棵樹，最多有 \(m\) 個約束區間，樹狀數組的修改和查找是 \(O(\log n)\) 的，所以總時間復雜度 \(O(Tn \log n)\)。
其他問題請看代碼。
代碼：
P11453
#include<cstdio>
#include<algorithm>
using namespace std;
inline int read(){
int x=0,f=1;char c=getchar();
while(c<48){
if(c=='-') f=-1;
c=getchar();
}
while(c>47) x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
const int N=1e5+5;
int T,n,m,pos[N],b[N],fa[N],tr[N],num[N];
struct Nahida{
int l,r,num;
}q[N];
inline void INIT(){
for(int i=1;i<=n;i++){
fa[i]=i,tr[i]=0,num[i]=0;
}
}
inline int lowbit(int x){
return x&(-x);
}
inline bool cmp(Nahida x,Nahida y){
return (x.r!=y.r?x.r<y.r:x.l<y.l);
}
inline void add(int x,int k){
while(x<=n){
tr[x]+=k;
x+=lowbit(x);
}
}
inline int query(int x){
int ans=0;
while(x){
ans+=tr[x];
x-=lowbit(x);
}
return ans;
}
inline int FIND(int x){
return (x==fa[x]?x:fa[x]=FIND(fa[x]));
}
signed main(){
T=read();
while(T--){
n=read(),m=read();
INIT();//多測一定要檢查你該清空的數組是否全部清空
//多測記得清空！！！
for(int i=1;i<=n;i++){
pos[i]=read();
b[i]=pos[i];
}
for(int i=1;i<=m;i++){
q[i].l=read(),q[i].r=read(),q[i].num=read();
}
//離散化
sort(b+1,b+n+1);sort(pos+1,pos+n+1);
int len=unique(b+1,b+n+1)-b-1;
for(int i=1;i<=n;i++){
pos[i]=lower_bound(b+1,b+len+1,pos[i])-b;
num[pos[i]]++;
//剛才題解里沒講到一個問題，就是一些樹的位置可能會重復，所以我們開個桶數組，記錄某個位置的樹有多少棵
}
for(int i=1;i<=m;i++){
q[i].l=lower_bound(b+1,b+len+1,q[i].l)-b;
q[i].r=upper_bound(b+1,b+len+1,q[i].r)-b-1;
/*
我離散化的時候沒有選擇把查詢端點也一起扔進去離散化，而是在找第一個大于等于左端點的樹的位置
和最后一個小于右端點的樹的位置，這樣我們相當于是把兩側沒有樹的無用區間忽略掉了
在此同時進行了一個離散化
*/
}
sort(q+1,q+m+1,cmp);//根據右端點從小到大排序
int ans=0;
for(int i=1;i<=m;i++){
int l=q[i].l,r=q[i].r;
int dq=query(r)-query(l-1);
//dq:當前區間已經有了多少棵樹
if(dq>=q[i].num){//當前區間已經種夠了，就不用種了
continue;
}
ans+=q[i].num-dq;
//否則就要種這么多棵樹
while(dq<q[i].num){
//nxt:更具體地說，指的是還沒有選樹的最靠右的某個位置，這個位置上可以有多棵樹
int nxt=FIND(r);
add(nxt,num[nxt]);//注意這里可能有多棵樹
fa[nxt]=nxt-1;
dq+=num[nxt];//用剛種的樹的數量更新dq
}
}
//ans記錄的是最少留多少樹，轉換成最多砍多少棵樹
printf("%d\n",n-ans);
}
return 0;
}
浙公網安備 33010602011771號