【学习笔记】ARC159

D - LIS 2

因为没有让你求方案数，所以还是比较好做的。

如果每一个连续段都退化成一个点，那么答案就是直接求$LIS$。

否则，假设我们选了一些连续段把它们拼起来形成答案，显然我们有$r_{i+1}\ge l_i$，否则这两段不能同时存在；并且其中一段不能包含另一段，否则可以把另一段删去。那么，如果$l_{i+1}>r_i$，答案显然就是两段的长度加起来；如果$l_{i+1}\ge r_i$，那么中间那一段重复的部分不管它，答案是$r_{i+1}-l_i+1$。

用线段树维护就做完了。复杂度$O(n\log n)$。

E - Difference Sum Query

非常好的谜题。但是我不会。

首先，根据$\frac{a_i}{b_i}$的范围不难得出新的区间长度不会超过原长度的$\frac{2}{3}$，因此$X_i\le \log N$。

然后，根据 { X i } \{X_i\} {Xi​}的构造过程，我们可以建立一颗二叉树，那么一个点的值就是它的深度。显然$i$和$i+1$之间是存在祖先关系的，因此问题转化为从$l$走到$l+1,...,r$过程中经过的路径长度。

做到这一步，感觉非常不可做。我们需要非常神奇的结论：假设让$r$重新走回$l$，那么答案就是$[l,r]$之间的点组成的虚树的边的数目乘$2$。这非常好理解，因为上述过程恰好就是做了一遍$DFS$。今天思路实在是非常混乱，不过我们还是尝试证明一下这个结论。事实上我们只需要用到：因为是二叉搜索树，所以子树内编号是连续的，因此进入一个子树后会把会把子树内能走的点走完，出去后就再也进不来了。

那么我们只要求出虚树点的数目即可。显然只需要求$l,r$路径上的编号不在$[l,r]$之间的点的数目，复杂度$O(\log n)$。

就这样吧。今日状态不佳。

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define inf 0x3f3f3f3f
using namespace std;
ll n,m,Q,a[105],b[105];
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=0;i<m;i++)cin>>a[i]>>b[i];cin>>Q;while(Q--){ll c,d;cin>>c>>d;ll l=1,r=n;ll numc=0,depc=0,t=0;while(1){ll M=(l*a[t]+r*b[t])/(a[t]+b[t]);if(M==c)break;if(M<c){numc++,l=M+1;}else r=M-1;t=(t+1)%m;depc++;}l=1,r=n;ll numd=0,depd=0;t=0;while(1){ll M=(l*a[t]+r*b[t])/(a[t]+b[t]);if(M==d)break;if(M>d){numd++,r=M-1;}else l=M+1;t=(t+1)%m;depd++;}ll res=2*(numc+numd+d-c)-depc-depd;cout<<res<<"\n";}
}

F - Good Division

最近只会抄$\text{std}$了，算了摆了

首先一眼真 不难看出序列合法的充要条件是不存在绝对众数。

然后似乎也没有什么特别好的思路，不妨还是尝试一下当确定绝对众数为$v$的情形，并且我们用总方案数减去不合法的方案数。那么将$(a_{2i-1},a_{2i})$看成一个权值在$[-1,1]$之间的数（记作$b_i$），我们需要对后缀和$>0$的位置求和。

让我们跳出这个$dp$。考虑对于固定的$v$，如果对位置$i$造成影响，那么一定存在$j<i$，使得$S_j<S_i$。分析可知，这样的$i$不会超过$cn{t}_v$个。

同时对于一个$j$，我们还要知道它会对那些$v$造成贡献。显然这样的$j$也不会超过$cn{t}_v$个。

那么将这些信息预处理出来即可。注意还是要写离散化。

复杂度$O(n\log n)$。

没什么状态就写一下代码吧

反思：这道题做了两个下午才$A$掉，说明自己的代码能力还是不够（或者说想得还是不够）。应该引起重视。

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define inf 0x3f3f3f3f
using namespace std;
const int N=2e6+5;
const int mod=998244353;
int n,a[N],cnt[N],*f[N];
int bit[N*2],len,dp[N];
vector<pair<int,int>>G[N];
vector<pair<int,int>>maj[N];
vector<pair<int,int>>maj2[N];
vector<int>lsh[N];
int qry(int v,int x){int tot(0);for(;x;x-=x&-x)tot=(tot+f[v][x])%mod;return tot;
}
void upd(int v,int x,int y){for(;x<=2*cnt[v];x+=x&-x)f[v][x]=(f[v][x]+y)%mod;
}
int get(int x,int y){return lower_bound(lsh[x].begin(),lsh[x].end(),y)-lsh[x].begin()+1;
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=2*n;i++)cin>>a[i],cnt[a[i]]++;//fixedfor(int i=1;i<=2*n;i++)f[i]=bit+len,len+=2*cnt[i]+1;for(int i=1;i<=n;i++){if(a[2*i-1]==a[2*i]){G[a[2*i-1]].pb({i,1});}else{G[a[2*i-1]].pb({i,0});G[a[2*i]].pb({i,0});}}//fixedfor(int i=1;i<=2*n;i++){int sumnow=0,sumpre=0,pos=0,sumval=-n;for(auto x:G[i]){while(sumnow-1>sumpre&&pos+1<x.fi)sumnow--,pos++,maj[pos].pb({i,sumnow}),lsh[i].pb(sumnow);sumnow-=x.fi-pos-1;//全是-1sumpre=min(sumpre,sumnow);pos=x.fi;if((sumnow+=x.se)>sumpre)maj[x.fi].pb({i,sumnow}),lsh[i].pb(sumnow);sumval+=1+x.se;}while(sumnow-1>sumpre&&pos+1<=n)sumnow--,pos++,maj[pos].pb({i,sumnow}),lsh[i].pb(sumnow);reverse(G[i].begin(),G[i].end());sumnow=0,sumpre=0,pos=n+1;for(auto x:G[i]){while(sumnow-1>sumpre&&pos-1>x.fi)sumnow--,pos--,maj2[pos-1].pb({i,sumval-sumnow}),lsh[i].pb(sumval-sumnow);sumnow-=pos-x.fi-1;sumpre=min(sumpre,sumnow);pos=x.fi;if((sumnow+=x.se)>sumpre){maj2[pos-1].pb({i,sumval-sumnow}),lsh[i].pb(sumval-sumnow);}}while(sumnow-1>sumpre&&pos-1>=1)sumnow--,pos--,maj2[pos-1].pb({i,sumval-sumnow}),lsh[i].pb(sumval-sumnow);sort(lsh[i].begin(),lsh[i].end());lsh[i].erase(unique(lsh[i].begin(),lsh[i].end()),lsh[i].end());}//fixedint sumpre=1;for(int i=0;i<=n;i++){dp[i]=sumpre;for(auto x:maj[i]){dp[i]=(dp[i]-qry(x.fi,get(x.fi,x.se)-1))%mod;}for(auto x:maj2[i]){upd(x.fi,get(x.fi,x.se),dp[i]);}if(i)sumpre=(sumpre+dp[i])%mod;}cout<<(dp[n]+mod)%mod<<"\n";
}