20191026模拟-lhy

lhy的场

「ZJOI2017」线段树

请先思考后再展开

答案的组成需要考虑广义线段树的结构,如果学过zkw可能会很熟悉:定位出$x=[l-1,l-1]和y=[r+1,r+1]$,也就是变成开区间(要将$[0,0]$和$[n+1,n+1]$放进去),那么答案就是【x到lca路径上,作为左孩子时统计右孩子】+【y到lca路径上,作为右孩子时统计左孩子】

考试的时候想到了转成开区间,但对于具体怎么统计不太记得了,就先跳了这题,不过确实也不好写

核心代码很短:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
fo(x,1,rt) val1[ !isleft[x] ][x]--,val1[ !isleft[x] ][ff[x]]++,val2[ !isleft[x] ][x]-=dep[x],val2[ !isleft[x] ][ff[x]]+=dep[x];//小容斥,树上差分
//----------------------------
ll solve(int wt,int u,int x,int lca,int LCA)
{
ll sum1,sum2,ans=0;
if(in(LCA,lca))//LCA在lca子树中
{
sum1=val1[wt][x]-val1[wt][LCA];sum2=val2[wt][x]-val2[wt][LCA];
ans+=sum2+sum1*(dep[u]-2*dep[lca]);
}
else//lca!=LCA
{
sum1=val1[wt][x]-val1[wt][lca];sum2=val2[wt][x]-val2[wt][lca];
if(sz(son[lca]) and in(x,son[lca][wt])) sum1++,sum2+=dep[son[lca][wt]];//想容斥去掉lca,现在不需要了
ans+=sum1*(dep[u]-dep[lca]*2)+sum2;
sum1=val1[wt][lca]-val1[wt][LCA];sum2=val2[wt][lca]-val2[wt][LCA];
if(sz(son[lca]))
{
if(in(x,son[lca][wt])) sum1--,sum2-=dep[son[lca][wt]];//错误地将son[lca][wt]计入答案
else if(in(u,son[lca][wt])) ans-=2;//son[lca][wt]并不需要上去再下来
}
ans+=sum1*(dep[u]+2)-sum2;
}
return ans;
}
//----------------------------
ll ans=0;
if(x!=LCA) ans+=solve(1,u,x,getlca(x,u),LCA);
if(y!=LCA) ans+=solve(0,u,y,getlca(y,u),LCA);
write2(ans);

复杂度瓶颈为求lca,完整code

CF878E Numbers on the blackboard

题意:给出一个长为n的序列,q次询问合并一段区间成一个数的最大值,合并操作为选相邻的两个数$x,y \to x+2y$,$n,q \le 2e5$

请先思考后再展开

首先很明显每个数的系数都是2的次幂,而且除了第一个数是1外至少是2,接下来忽略第一个数

考试的时候只想到了从后往前的做法,然而不太能优化:考虑$[l,r]中的r,如果a_r<0肯定是solve(l,r-1)+2*a_r;否则一定是a_{r-1}+=a_r,solve(l,r-1)$

然后部分分有提示下我想搞出一个从前往后的,根据上面的想法,考虑树形结构,每次加入最后一个数后维护树形结构

然后就自闭了……其实就是想成树形结构后不太会快速维护了……因为看起来势能不明显,改成栈结构就不一样了。

引入块的概念:注意到我们上面序列的理解时,将这个数和上个数合并,那现在从左往右做的话,就是每次不断取出最后面的一个块,如果和非负,合并到上一个块中(需要记录每个块的长度来处理新系数),这样就是维护栈的过程,于是我们得到了一个从左往右而且结构清晰的做法

那我们如此追求从前往后做,究竟是得出了什么性质方便处理区间询问?按右端点排序,对于一个左端点l所在的块(设l及左边是A,l右边是B),这个B一定是不会与后面合并或裂开的,不合并显然,如果裂开成a和b,显然b<0,显然当时就不会把b放到这个块中,所以也不存在

于是二分找到这个块,查询后缀和即可(栈结构,所谓维护前缀和即可),关于原数,我们只关心与0的大小关系,注意到只有非负数会向前累计且乘上系数(至少2),所以负数不会很小,非负数的话如果太大可以永久设置为inf(一旦超过2e9就不会再低于)

$O(nlogn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
const ll MXNUM=2e9;
ll val[N],bin[N];
pr sta[N];int top;ll sum[N];//块的前缀和
ll a[N],b[N];ll getnum(int l,int r){return (b[l]+MOD-b[r+1]*bin[r-l+1]%MOD)*2%MOD;}
vc<pr> qes[N];int ans[N];
void main()
{
int n=qread(),q=qread();fo(i,1,n) a[i]=qread();
bin[0]=1;fo(i,1,n) bin[i]=bin[i-1]*2%MOD;
fd(i,n,1) b[i]=(b[i+1]*2+MOD+a[i])%MOD;
fo(i,1,q) {int l=qread(),r=qread();qes[r].PB(MP(l,i));if(r==1) ans[i]=a[1];}
fo(r,2,n)
{
sta[++top]=MP(r,r);val[top]=a[r]*2;
while(top>1 and val[top]>=0)
{
int ln=sta[top-1].SE-sta[top-1].FR+1;
if((ln>31 and val[top]>0) or (val[top-1]+(val[top]<<ln)>MXNUM)) val[top-1]=MXNUM;
else val[top-1]=val[top-1]+(val[top]<<ln);
top--;sta[top].SE=r;
}
sum[top]=(sum[top-1]+val[top])%MOD;
for(auto qq:qes[r])
{
int l=qq.FR,id=qq.SE,pos=upper_bound(sta+1,sta+top+1,MP(l+1,INF))-sta-1;
ans[id]=(sum[top]-sum[pos]+getnum(l+1,sta[pos].SE)+a[l])%MOD;
}
}
fo(i,1,q) write2((ans[i]+MOD)%MOD);
}

附赠一组数据:

1
2
3
4
5
6
7
8
9
10
11
39 2
-323234955 -13554851 -123440597 472130426 672108688
-653249727 277910975 -828753454 -114968816 -565464233
-306030157 229718280 -93206797 186181819 -12895015
320850407 -996529151 -960614046 571549914 114897911
54330123 -893571971 875707713 -31932276 196887436
89434767 -475230657 -672819122 225392755 -958315585
-954084193 13933650 265536646 -956977269 -123437282
-48757209 -32931396 345935203 -401920040
7 39
10 33

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/174ef833.html
转载请注明出处,谢谢!