代做机械设计的网站,网站上传文件不存在,在线编辑图片的网站有哪些,dede发布网站正题
题目链接:http://www.ybtoj.com.cn/problem/752 题目大意 nnn个人#xff0c;每个人有cic_ici和did_idi分别表示这个人所在的队伍的最少/最多人数。
然后要求将这些人分成编号连续的若干队使得队伍最多#xff0c;并且求分队方案数。 1≤n≤1061\leq n\leq 10^61≤…正题
题目链接: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(nlog2n)O(n\log^2 n)O(nlog2n)但是这样过不了还得优化。
分类讨论一下我们现在考虑一个在右边的iii和一个在左边的jjj我们已经处理好了左边的答案要用它来更新右边的。
leftiLleft_iLleftiL且imidcmidi midc_{mid}imidcmid此时可以先不管leftleftleft了只需要考虑后面那个而且注意到每次iii移动一格后jjj会多一个取值位置所以我们维护一个记录区间最优答案的线段树。然后先用线段树查询出第一个满足条件的iii的答案然后后面每次加一个答案就好了 然后这里一次的复杂度是左右区间的最小长度和启发式合并类似时间复杂度O(nlogn)O(n\log n)O(nlogn)leftiLleft_iLleftiL且i≥midcmidi\geq midc_{mid}i≥midcmid此时对于所有的iiijjj的取值范围都是[L,mid−1][L,mid-1][L,mid−1]直接拿线段树查出最大的答案然后向右边区间修改就好了。L≤leftimidL\leq left_imidL≤leftimid这个好像只能对于每个iii用线段树暴力查询。但是可以注意到对于每个iii从头到尾只会到一次这种情况所以时间复杂度还是O(nlogn)O(n\log n)O(nlogn)的lefti≥midleft_i\geq midlefti≥mid这个向右边分治的时候会解决不需要这里统计
上面这四个情况的都是在一个区间里的而且是按顺序出现的需要注意的时候第二种情况是不能暴力枚举的所以我们需要二分出这个情况区间的末尾
然后总共的时间复杂度就是O(nlogn)O(n\log n)O(nlogn)的了细节有点多比如建笛卡尔树的时候还要用ststst表查区间最大之类的。 code
#pragma GCC optimize(2)
%:pragma GCC optimize(3)
%:pragma GCC optimize(Ofast)
%:pragma GCC optimize(inline)
#includecstdio
#includecstring
#includealgorithm
#includequeue
#includecctype
#define ll long long
using namespace std;
const ll N1e610,P1e97,nul-1e96;
struct node{ll f,g;node(ll ff0,ll gg0){fff;ggg;return;}
};
node operator(node x,node y){if(x.fy.f)return node(x.f,x.g);else if(x.fy.f)return node(y.f,y.g);return node(x.f,(x.gy.g)%P);
}
node plu(node x)
{return node(x.f1,x.g);}
ll read() {ll x0,f1; char cgetchar();while(!isdigit(c)) {if(c-)f-f;cgetchar();}while(isdigit(c)) x(x1)(x3)c-48,cgetchar();return x*f;
}
ll n,c[N],d[N],left[N],st[N][20],lg[N];
dequell q;node f[N];
struct SegTree{node w[N2],lazy[N2];void Downdata(ll x,ll L,ll R){if(lazy[x].fnul)return;ll mid(LR)1;w[x*2]w[x*2]lazy[x];w[x*21]w[x*21]lazy[x]; lazy[x*2]lazy[x*2]lazy[x];lazy[x*21]lazy[x*21]lazy[x];lazy[x].fnul;return;}void Change(ll x,ll L,ll R,ll l,ll r,node p){if(lr||l0)return;if(LlRr){w[x]w[x]p;lazy[x]lazy[x]p;return;}ll mid(LR)1;Downdata(x,L,R);if(rmid)Change(x*2,L,mid,l,r,p);else if(lmid)Change(x*21,mid1,R,l,r,p);else Change(x*2,L,mid,l,mid,p),Change(x*21,mid1,R,mid1,r,p);w[x]w[x*2]w[x*21];}void Set(ll x,ll L,ll R,ll pos,node p){if(LR){w[x]p;return;}ll mid(LR)1;Downdata(x,L,R);if(posmid)Set(x*2,L,mid,pos,p);else Set(x*21,mid1,R,pos,p);w[x]w[x*2]w[x*21];}node Ask(ll x,ll L,ll R,ll l,ll r){if(lr||l0)return node(nul,nul);if(LlRr)return w[x];ll mid(LR)1;Downdata(x,L,R);if(rmid)return Ask(x*2,L,mid,l,r);if(lmid)return Ask(x*21,mid1,R,l,r);return Ask(x*2,L,mid,l,mid)Ask(x*21,mid1,R,mid1,r);}
}T;
ll Ask(ll l,ll r){ll zlg[r-l1];ll xst[l][z],yst[r-(1z)1][z];return (c[x]c[y])?x:y;
}
void solve(ll L,ll R){if(LR){f[L]f[L]T.Ask(1,0,n,L,L);T.Set(1,0,n,L,f[L]);return;}ll xAsk(L1,R);solve(L,x-1);ll lx,rR;while(lr){ll mid(lr)1;if(left[mid]L)rmid-1;else lmid1;}ll posr;lmax(x,Lc[x]);rmin(min(R,xc[x]),pos);node tmpT.Ask(1,0,n,L,l-c[x]);ll pl-c[x]1;for(ll il;ir;i){f[i]f[i]plu(tmp);if(px)tmptmpf[p],p;}tmpT.Ask(1,0,n,L,x-1);if(r1x)T.Change(1,0,n,r1,pos,plu(tmp));for(ll ipos1;iR;i){if(left[i]x)break;tmpT.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);nread();for(ll i1;in;i){c[i]read();d[i]read();ll lleft[i];lleft[i-1];while(!q.empty()d[q.back()]d[i])q.pop_back();q.push_back(i);while(i-ld[q.front()]){l;if(q.front()l)q.pop_front();}st[i][0]i;}for(ll i2;in;i)lg[i]lg[i1]1;for(ll j1;(1j)n;j)for(ll i1;i(1j)-1n;i){ll xst[i][j-1],yst[i(1j-1)][j-1];st[i][j](c[x]c[y])?x:y;}for(int i0;i(N2);i)T.lazy[i]node(nul,0),T.w[i]node(-1e9,0);for(ll i1;in;i)f[i]node(nul,nul);f[0]node(0,1);solve(0,n);if(f[n].f0)return 0puts(-1);printf(%lld %lld\n,f[n].f,f[n].g);return 0;
}
