【学习笔记】ARC159

D - LIS 2

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

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

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

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

E - Difference Sum Query

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

首先，根据aibi\\frac{a_i}{b_i}bi​ai​​的范围不难得出新的区间长度不会超过原长度的23\\frac{2}{3}32​，因此Xi≤log⁡NX_i\\le \\log NXi​≤logN。

然后，根据{Xi}\\{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";}
}