外贸网站建设制作教程,个人网站域名备案步骤,个性定制网站,wordpress大前端dux-plus正题
题目链接:https://www.luogu.com.cn/problem/CF1039E 题目大意
给出nnn个数的序列#xff0c;mmm次询问至少将这个序列分成多少段才能满足每一段的和不超过w−qiw-q_iw−qi。 1≤n,m≤105,1≤w,ai≤1091\leq n,m\leq 10^5,1\leq w,a_i\leq 10^91≤n,m≤105,1≤w,ai…正题
题目链接:https://www.luogu.com.cn/problem/CF1039E 题目大意
给出nnn个数的序列mmm次询问至少将这个序列分成多少段才能满足每一段的和不超过w−qiw-q_iw−qi。
1≤n,m≤105,1≤w,ai≤1091\leq n,m\leq 10^5,1\leq w,a_i\leq 10^91≤n,m≤105,1≤w,ai≤109 解题思路
考虑暴力的做法我们可以每次走到必须要分段时才分段显然是正确的。
根据w−qiw-q_iw−qi从小到大来做设tit_iti表示以iii为左端点时最长能分到的区间长度tit_iti那么我们从iii就能直接到达itiit_iiti。
那么我们从111出发一直往右跳看跳的次数就可以了这个和[HNOI2010]弹飞绵羊很像考虑用LCTLCTLCT去维护。
不过这个tit_iti是可能每次都在改变的所以不能只靠这样来做但是注意到iii每次会直接跳过ti−1t_i-1ti−1个位置我们不需要统计全局的值。
所以我们考虑根号分治对于一个TnT\sqrt nTn我们当ti≤Tt_i\leq Tti≤T时我们在LCTLCTLCT上条当tiTt_iTtiT时我们直接暴力跳。
同样的我们不需要去维护这些TTT的tit_iti而是到达这些位置时直接二分下一个位置即可。
用一个堆去存ti≤Tt_i\leq Tti≤T的位置以方便更改。
时间复杂度O(nnlogn)O(n\sqrt n\log n)O(nnlogn) code
#includecstdio
#includecstring
#includealgorithm
#includequeue
#includestack
#includecmath
#define mp(x,y) make_pair(x,y)
using namespace std;
const int N1e510,Q230;
int n,m,w,a[N],t[N],ans[N];
int f[N][19],g[N][19],lg[N];
pairint,int q[N];
priority_queuepairint,int h;
struct LCT{int t[N][2],siz[N],fa[N];stackint s;bool r[N];bool Nroot(int x){return fa[x](t[fa[x]][0]x||t[fa[x]][1]x);}bool Direct(int x){return (t[fa[x]][1]x);}void PushUp(int x){siz[x]siz[t[x][0]]siz[t[x][1]]1;return;}void PushR(int x){swap(t[x][0],t[x][1]);r[x]^1;return;}void PushDown(int x){if(r[x]){PushR(t[x][0]);PushR(t[x][1]);r[x]0;}return;}void Rotate(int x){int yfa[x],zfa[y];int xsDirect(x),ysDirect(y);int wt[x][xs^1];t[x][xs^1]y;t[y][xs]w;if(Nroot(y))t[z][ys]x;if(w)fa[w]y;fa[y]x;fa[x]z;PushUp(y);PushUp(x);return;}void Splay(int x){int yx;s.push(y);while(Nroot(y))yfa[y],s.push(y);while(!s.empty())PushDown(s.top()),s.pop();while(Nroot(x)){int yfa[x];if(!Nroot(y))Rotate(x);else if(Direct(x)Direct(y))Rotate(y),Rotate(x);else Rotate(x),Rotate(x);}return;}void Access(int x){for(int y0;x;yx,xfa[x])Splay(x),t[x][1]y,PushUp(x);return;}void MakeRoot(int x){Access(x);Splay(x);PushR(x);return;}void Link(int x,int y){Access(x);fa[x]y;return;}void Cut(int x,int y){Access(x);Splay(y);fa[x]t[y][1]0;PushUp(y);return;}int FindRoot(int x){Access(x);Splay(x);PushDown(x);while(t[x][0])xt[x][0],PushDown(x);Splay(x);return x;}
}T;
int MIX(int l,int r){if(rn)return 1e97;int zlg[r-l1];int xmax(g[l][z],g[r-(1z)1][z]);int ymin(f[l][z],f[r-(1z)1][z]);return x-y;
}
int nxts(int x,int w){int lx,rn;while(lr){int mid(lr)1;if(MIX(x,mid)w)lmid1;else rmid-1;}return l;
}
int main()
{scanf(%d%d%d,n,w,m);for(int i1;in;i)scanf(%d,a[i]),f[i][0]g[i][0]a[i];for(int j1;(1j)n;j)for(int i1;i(1j)-1n;i){f[i][j]min(f[i][j-1],f[i(1j-1)][j-1]);g[i][j]max(g[i][j-1],g[i(1j-1)][j-1]);}for(int i2;in;i)lg[i]lg[i1]1;for(int i1;in1;i)T.siz[i]1;for(int i1;in;i){t[i]1,T.Link(i,it[i]);h.push(mp(-MIX(i,i1),i));}for(int i1;im;i)scanf(%d,q[i].first),q[i].secondi;sort(q1,q1m);reverse(q1,q1m);for(int i1;im;i){int xw-q[i].first;while(!h.empty()-h.top().firstx){int ph.top().second;h.pop();T.Cut(p,pt[p]);t[p];if(t[p]Q){T.Link(p,pt[p]);h.push(mp(-MIX(p,pt[p]),p));}else t[p]-1;}int now1,sum0;while(nown1){if(t[now]-1)nownxts(now,x),sum;else{T.Access(now);T.Splay(now);sumT.siz[now]-1;nowT.FindRoot(now);}}ans[q[i].second]sum;}for(int i1;im;i)printf(%d\n,ans[i]-1);return 0;
}
