YbtOJ#752-最优分组【笛卡尔树,线段树】
正題
題目鏈接:http://www.ybtoj.com.cn/problem/752
題目大意
nnn個人,每個人有cic_ici?和did_idi?分別表示這個人所在的隊伍的最少/最多人數。
然后要求將這些人分成編號連續的若干隊使得隊伍最多,并且求分隊方案數。
1≤n≤1061\leq n\leq 10^61≤n≤106
解題思路
陰間題目…
為了方便計算先定義一個結構體(包含答案和方案數)和加法運算表示取最大值/相同加方案數作為答案。
設fif_ifi?表示以第iii個作為末尾的答案,首先did_idi?就相當于限制了一個后綴的范圍,所以可以先用單調隊列算出leftileft_ilefti?表示根據ddd的限制從iii能選到的最左位置?1-1?1。
然后cic_ici?的限制很陰間,因為它的限制顯然不是一個連續的范圍。
考慮到一個l~rl\sim rl~r的轉移的ccc限制只由這個區間最大的cic_ici?來限制,所以可以考慮在笛卡爾樹上做。這樣其實加個數據結構可以輕松做到O(nlog?2n)O(n\log^2 n)O(nlog2n),但是這樣過不了,還得優化。
分類討論一下,我們現在考慮一個在右邊的iii和一個在左邊的jjj,我們已經處理好了左邊的答案,要用它來更新右邊的。
然后這里一次的復雜度是左右區間的最小長度,和啟發式合并類似時間復雜度O(nlog?n)O(n\log n)O(nlogn)
上面這四個情況的都是在一個區間里的,而且是按順序出現的,需要注意的時候第二種情況是不能暴力枚舉的,所以我們需要二分出這個情況區間的末尾
然后總共的時間復雜度就是O(nlog?n)O(n\log n)O(nlogn)的了,細節有點多,比如建笛卡爾樹的時候還要用ststst表查區間最大之類的。
code
#pragma GCC optimize(2) %:pragma GCC optimize(3) %:pragma GCC optimize("Ofast") %:pragma GCC optimize("inline") #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<cctype> #define ll long long using namespace std; const ll N=1e6+10,P=1e9+7,nul=-1e9+6; struct node{ll f,g;node(ll ff=0,ll gg=0){f=ff;g=gg;return;} }; node operator+(node x,node y){if(x.f>y.f)return node(x.f,x.g);else if(x.f<y.f)return node(y.f,y.g);return node(x.f,(x.g+y.g)%P); } node plu(node x) {return node(x.f+1,x.g);} ll read() {ll x=0,f=1; char c=getchar();while(!isdigit(c)) {if(c=='-')f=-f;c=getchar();}while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();return x*f; } ll n,c[N],d[N],left[N],st[N][20],lg[N]; deque<ll > q;node f[N]; struct SegTree{node w[N<<2],lazy[N<<2];void Downdata(ll x,ll L,ll R){if(lazy[x].f==nul)return;ll mid=(L+R)>>1;w[x*2]=w[x*2]+lazy[x];w[x*2+1]=w[x*2+1]+lazy[x]; lazy[x*2]=lazy[x*2]+lazy[x];lazy[x*2+1]=lazy[x*2+1]+lazy[x];lazy[x].f=nul;return;}void Change(ll x,ll L,ll R,ll l,ll r,node p){if(l>r||l<0)return;if(L==l&&R==r){w[x]=w[x]+p;lazy[x]=lazy[x]+p;return;}ll mid=(L+R)>>1;Downdata(x,L,R);if(r<=mid)Change(x*2,L,mid,l,r,p);else if(l>mid)Change(x*2+1,mid+1,R,l,r,p);else Change(x*2,L,mid,l,mid,p),Change(x*2+1,mid+1,R,mid+1,r,p);w[x]=w[x*2]+w[x*2+1];}void Set(ll x,ll L,ll R,ll pos,node p){if(L==R){w[x]=p;return;}ll mid=(L+R)>>1;Downdata(x,L,R);if(pos<=mid)Set(x*2,L,mid,pos,p);else Set(x*2+1,mid+1,R,pos,p);w[x]=w[x*2]+w[x*2+1];}node Ask(ll x,ll L,ll R,ll l,ll r){if(l>r||l<0)return node(nul,nul);if(L==l&&R==r)return w[x];ll mid=(L+R)>>1;Downdata(x,L,R);if(r<=mid)return Ask(x*2,L,mid,l,r);if(l>mid)return Ask(x*2+1,mid+1,R,l,r);return Ask(x*2,L,mid,l,mid)+Ask(x*2+1,mid+1,R,mid+1,r);} }T; ll Ask(ll l,ll r){ll z=lg[r-l+1];ll x=st[l][z],y=st[r-(1<<z)+1][z];return (c[x]>=c[y])?x:y; } void solve(ll L,ll R){if(L==R){f[L]=f[L]+T.Ask(1,0,n,L,L);T.Set(1,0,n,L,f[L]);return;}ll x=Ask(L+1,R);solve(L,x-1);ll l=x,r=R;while(l<=r){ll mid=(l+r)>>1;if(left[mid]>=L)r=mid-1;else l=mid+1;}ll pos=r;l=max(x,L+c[x]);r=min(min(R,x+c[x]),pos);node tmp=T.Ask(1,0,n,L,l-c[x]);ll p=l-c[x]+1;for(ll i=l;i<=r;i++){f[i]=f[i]+plu(tmp);if(p<x)tmp=tmp+f[p],p++;}tmp=T.Ask(1,0,n,L,x-1);if(r+1>=x)T.Change(1,0,n,r+1,pos,plu(tmp));for(ll i=pos+1;i<=R;i++){if(left[i]>=x)break;tmp=T.Ask(1,0,n,left[i],min(i-c[x],x-1));f[i]=f[i]+plu(tmp);}solve(x,R);return; } signed main() {freopen("schooldays.in","r",stdin);freopen("schooldays.out","w",stdout);n=read();for(ll i=1;i<=n;i++){c[i]=read();d[i]=read();ll &l=left[i];l=left[i-1];while(!q.empty()&&d[q.back()]>=d[i])q.pop_back();q.push_back(i);while(i-l>d[q.front()]){l++;if(q.front()==l)q.pop_front();}st[i][0]=i;}for(ll i=2;i<=n;i++)lg[i]=lg[i>>1]+1;for(ll j=1;(1<<j)<=n;j++)for(ll i=1;i+(1<<j)-1<=n;i++){ll x=st[i][j-1],y=st[i+(1<<j-1)][j-1];st[i][j]=(c[x]>=c[y])?x:y;}for(int i=0;i<(N<<2);i++)T.lazy[i]=node(nul,0),T.w[i]=node(-1e9,0);for(ll i=1;i<=n;i++)f[i]=node(nul,nul);f[0]=node(0,1);solve(0,n);if(f[n].f<=0)return 0&puts("-1");printf("%lld %lld\n",f[n].f,f[n].g);return 0; }總結
以上是生活随笔為你收集整理的YbtOJ#752-最优分组【笛卡尔树,线段树】的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 空手套白狼什么意思 空手套白狼的含义
- 下一篇: 最终幻想4攻略 最终幻想4攻略简单解析