恩欧挨批模拟式题-50
水博客太快乐了
有好几场模拟赛的博客没有写，原因是前段时间认为写博客貌似没有什么用，不如用写博客的时间去看看一些奇奇怪怪的题和其他知识点。
然而事实证明水博客还是很有必要的。
考场
发现 \(T1\) 貌似很好写，和一道叫弹飞绵羊的题很像，只不过被搬到了树上，然而弹飞绵羊是一道分块的题。。。
被树剖困惑了很久，结果发现其实只要倍增一下即可。。。
然而浪费了两个多小时。
之后剩下一个多小时，感觉可以 \(T2 \ T3\) 还有好多部分分，于是选择先写 \(T2\) ，本来想先写暴力，再想正解，然而样例锅了。。。多了一个换行，写了好几种暴力（其中包含多正解起有启发的方法），发现输出的都是相同的错误答案，才发现问题，结果写完暴力只剩十分多钟了，没时间搞 \(T3\) 了，只能坐等出分。
分数
预估 ： \(t1 \ 100pts \ + \ t2 \ 20pts \ + \ t3 \ 0pts \ = \ 120pts\)
实际 ： \(t1 \ 100pts \ + \ t2 \ 20pts \ + \ t3 \ 0pts \ = \ 120pts\)
题解
A. 第零题
首先，对于每个点，很容易求出从它开始向上走（显然一个栈就可以了，对吧！？ ^_^），走到哪里会死，为了快速查询，不难想到讲这个数组倍增一下，即 \(p_{u, i}\) 表示从点 \(u\) 向上走，死 \(2^i\) 次后的位置。
对于每次询问 \(s, t\)，首先找到这两个点的 \(lca\) ，然后倍增求出从 \(s\) 走到 \(lca\) 会死多少次。但是从 \(s\) 死到 \(lca\) 不一定刚好会在 \(lca\) 处死亡，而是在链 \((s, lca)\) 上 \(lca\) 下方的某一个点 \(u\) 处，接着要从 \(lca\) 走向 \(t\) ，不妨先在链 \((lca, t)\) 上先找到一个点 \(v\) ，使得从 \(u\) 走到 \(lca\) 再走到 \(v\) 刚好死亡（显然也可以倍增来求），接着只要从 \(v\) 走到 \(t\) 即可。
从上往下走很麻烦，此时有一个性质，从 \(u\) 走到 \(v\) 的死亡次数与从 \(v\) 走到 \(u\) 的死亡次数相同，这个很好证明（相信从明的您一定会的，对吧！？ ^_^），随便画一画就出来了。。。这样就把从上往下走转变成了从下往上走。。。
大概就这样？也没什么细节要注意的。。。
时间复杂度 : \(O(n\log n)\)
code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define t first
#define w second
const int N=2e5+10;
inline int read(){
int f=1, x=0; char ch=getchar();
while(!isdigit(ch)) { if(ch=='-') f=-1; ch=getchar(); }
while(isdigit(ch)) { x=x*10+ch-48; ch=getchar(); }
return f*x;
}
int n, k, m;
vector<pair<int, int> > l[N];
int fa[N][21], plc[N][21], dep[N], stk[N], top, l1;
ll dis[N];
void dfs1(int u, int f1, int dis1){
dep[u]=dep[f1]+1; dis[u]=dis[f1]+dis1; fa[u][0]=f1; stk[++top]=u;
int ul=l1;
while(dis[u]-dis[stk[l1+1]]>=k&&l1<top) ++l1;
if(dis[u]-dis[stk[l1]]>=k) plc[u][0]=stk[l1];
for(pair<int, int> v : l[u])
if(v.t!=f1) dfs1(v.t, u, v.w);
l1=ul; --top;
}
void dfs2(int u){
for(int i=1; i<20; ++i){
plc[u][i]=plc[plc[u][i-1]][i-1];
fa[u][i]=fa[fa[u][i-1]][i-1];
}
for(pair<int, int> v : l[u])
if(v.t!=fa[u][0]) dfs2(v.t);
}
inline int lca(int u, int v){
if(dep[u]<dep[v]) u^=v, v^=u, u^=v;
for(int i=19; ~i; --i)
if(dep[fa[u][i]]>=dep[v]) u=fa[u][i];
if(u==v) return u;
for(int i=19; ~i; --i)
if(fa[u][i]!=fa[v][i]) u=fa[u][i], v=fa[v][i];
return fa[u][0];
}
inline int solve(int u, int v){
int Lca=lca(u, v), ans=0, ul, v1=v;
for(int i=19; ~i; --i)
if(dep[plc[u][i]]>=dep[Lca]) ans+=1<<i, u=plc[u][i];
ul=k-(dis[u]-dis[Lca]);
for(int i=19; ~i; --i)
if(dis[fa[v1][i]]-dis[Lca]>=ul) v1=fa[v1][i];
if(dis[v1]-dis[Lca]>=ul) ++ans;
for(int i=19; ~i; --i)
if(dep[plc[v][i]]>=dep[v1]) ans+=1<<i, v=plc[v][i];
return ans;
}
int main(void){
n=read(), k=read(); int x, y, z;
for(int i=1; i<n; ++i){
x=read(), y=read(), z=read();
l[x].push_back(make_pair(y, z));
l[y].push_back(make_pair(x, z));
}
dfs1(1, 0, 0); dfs2(1);
m=read();
while(m--){
x=read(), y=read();
printf("%d\n", solve(x, y));
}
return 0;
}
B. 第负一题
一道阴间友善的分治题。。。
对于分治区间，求出跨过当前区间中点的答案和，对于每左区间的点 \(i\) ，不难求出 \(l_{i,0}\ l_{i,1｝\) 分别表示 \([i,mid]\) ，选不选 \(mid\) 的答案。同理，对于每个友区间的点 \(j\) ，也不难求出 \(r_{i,0}\ r_{i,1}\) ，分别表示 \([mid+1,r]\) ，选不选 \(mid+1\) 的答案。
若要合并一个区间，对于 \([i,j]\) ，则答案显然是 \(max(l_{i,0}+r_{j,0}, l_{i,1}+r_{j,0}, l_{i,0}+r_{j,1})\)。
不妨设 \(L_{i}=max(0, l_{i,1}-l_{i,0}),\ R_{i}=max(0, r_{i,1}-r_{i,0})\) 。
则答案可以表示成 ： \(l_{i,0}+r_{j,0}+max(L_{i},R_{j})\) 。
发现对于区间 \([i,j]\) \(l_{i,0}\) 与 \(r_{j,0}\) 一定会被记录到答案中，而 \(L_{i}\) 若对区间 \([i,j]\) 有贡献，当且仅当 \(L_i > R_j\) ， \(R_j\) 同理，因此将 \(L\) 与 \(R\) 放在一起排序后统计即可。
code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
const ll N=2e5+10, INF=0x3f3f3f3f3f3f3f3f, mod=998244353;
inline int read(){
int f=1, x=0; char ch=getchar();
while(!isdigit(ch)) { if(ch=='-') f=-1; ch=getchar(); }
while(isdigit(ch)) { x=x*10+ch-48; ch=getchar(); }
return f*x;
}
int n, top, a[N];
ll ans, f[N][2][2];
pair<ll, int > stk[N];
void solve(int l, int r){
if(l==r) { (ans+=a[l])%=mod; return; }
int mid=(l+r)>>1, numl=0, numr=0;
solve(l, mid); solve(mid+1, r); top=0;
f[mid+1][1][1]=a[mid+1]; f[mid+1][0][0]=0;
f[mid+1][1][0]=f[mid+1][0][1]=-INF;
for(int i=mid+2; i<=r; ++i){
f[i][1][0]=max(f[i-1][1][0], f[i-1][1][1]); f[i][1][1]=f[i-1][1][0]+a[i];
f[i][0][0]=max(f[i-1][0][0], f[i-1][0][1]); f[i][0][1]=f[i-1][0][0]+a[i];
(ans+=max(f[i][0][1], f[i][0][0])*(mid-l+1)%mod)%=mod;
}
f[mid][1][1]=a[mid]; f[mid][0][0]=0;
f[mid][1][0]=f[mid][0][1]=-INF;
for(int i=mid-1; i>=l; --i){
f[i][1][0]=max(f[i+1][1][0], f[i+1][1][1]); f[i][1][1]=f[i+1][1][0]+a[i];
f[i][0][0]=max(f[i+1][0][0], f[i+1][0][1]); f[i][0][1]=f[i+1][0][0]+a[i];
(ans+=max(f[i][0][1], f[i][0][0])*(r-mid)%mod)%=mod;
}
for(int i=l; i<=r; ++i)
stk[++top]=make_pair(max(max(f[i][1][1], f[i][1][0])-max(f[i][0][1], f[i][0][0]), 0ll), i);
sort(stk+1, stk+1+top);
for(int i=1; i<=top; ++i){
if(stk[i].se<=mid){
(ans+=stk[i].fi*numr%mod)%=mod;
++numl;
}else{
(ans+=stk[i].fi*numl%mod)%=mod;
++numr;
}
}
}
int main(void){
n=read();
for(int i=1; i<=n; ++i) a[i]=read();
solve(1, n); printf("%lld\n", ans);
return 0;
}
C. 第负二题
毒瘤出的阴间题凭什么让我一个阳间人来做？？？
居然有四个人场切。。。
然而后来数据被加强了。。。
首先对于 \(i\) 来说，考虑一个答案 \(k\) 成立需满足那些条件。
不难发现需要存在一个中心在 \(i\) 这一行的菱形满足其对角线长度为 \(2k-1\) 。
设中心为 \(mid\) ，则需满足 ：
\(\forall j \in [i-k+1,i+k-1], \ mid+(k-|j-i|-1) \le r_i \& mid-(k-|j-i|-1) \ge l_i\)
也就是 ：
\(min(r_j-(k-|j-i|-1)) \ge max(l_j+(k-|j-i|-1))\)
由于数据被加强了，卡掉了 \(RMQ\) 带 \(\log\)的做法（不知道四毛子能不能过？？），只能用单调队列维护最大值最小值（所以需要四个单调队列。。。）。
不难发现 \(ans_i \in [ans_{i-1}-1, ans_{i-1}+1]\)，于是直接枚举即可。
一堆细节。。。麻烦。。。
code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=5e6+10, mod=998244353, INF=0x3f3f3f3f;
typedef unsigned long long u64;
inline u64 read(){
u64 f=1, x=0; char ch=getchar();
while(!isdigit(ch)) { if(ch=='-') f=-1; ch=getchar(); }
while(isdigit(ch)) { x=x*10+ch-48; ch=getchar(); }
return f*x;
}
u64 xorshift128p(u64 &A, u64 &B) {
u64 T = A, S = B;
A = S;
T ^= T << 23;
T ^= T >> 17;
T ^= S ^ (S >> 26);
B = T;
return T + S;
}
void gen(int n, int L, int X, int Y, u64 A, u64 B, int l[], int r[]) {
for (int i = 1; i <= n; i ++) {
l[i] = xorshift128p(A, B) % L + X;
r[i] = xorshift128p(A, B) % L + Y;
if (l[i] > r[i]) swap(l[i], r[i]);
}
}
int n;
u64 A, B, X, Y, L;
int l[N], r[N];
int q1[N], q2[N], q3[N], q4[N], l1, r1, l2, r2, l3, r3, l4, r4, f[N];
ll ans;
inline void add(int p){
while(l1<=r1&&l[q1[r1]]-q1[r1]<=l[p]-p) --r1;
while(l2<=r2&&r[q2[r2]]+q2[r2]>=r[p]+p) --r2;
q1[++r1]=p, q2[++r2]=p;
}
inline void add1(int p){
while(l3<=r3&&l[q3[r3]]+q3[r3]<=l[p]+p) --r3;
while(l4<=r4&&r[q4[r4]]-q4[r4]>=r[p]-p) --r4;
q3[++r3]=p, q4[++r4]=p;
}
inline bool chk(int i, int k, int op){
int L1=-INF, R1=INF;
if(l1<=r1) L1=l[q1[l1]]-q1[l1]+k+i-1;
if(l2<=r2) R1=r[q2[l2]]+q2[l2]-k-i+1;
if(l3<=r3) L1=max(L1, l[q3[l3]]+q3[l3]+k-i-1);
if(l4<=r4) R1=min(R1, r[q4[l4]]-q4[l4]-k+i+1);
for(int j=1; j<=op; ++j){
L1=max(L1, l[i+k-j]-(i+k-j)+i+k-1);
R1=min(R1, r[i+k-j]+(i+k-j)-i-k+1);
}
return L1<=R1;
}
signed main(void){
freopen("sample.in", "r", stdin);
freopen("wrong.out", "w", stdout);
n=read(); L=read(), X=read(), Y=read(), A=read(), B=read();
gen(n, L, X, Y, A, B, l, r);
l1=l2=l3=l4=1; f[1]=1;
for(int i=2; i<=n; ++i){
while(q1[l1]<i&&l1<=r1) ++l1;
while(q2[l2]<i&&l2<=r2) ++l2;
f[i]=f[i-1]+1; add1(i-1);
for(int j=2; j; --j){
if(chk(i, f[i], j)){
for(int k=j; k; --k) add(i+f[i]-k);
break;
}else{
--f[i];
while(l3<=r3&&q3[l3]<=i-f[i]) ++l3;
while(l4<=r4&&q4[l4]<=i-f[i]) ++l4;
}
}
}
ll mul=1;
for(int i=1; i<=n; ++i){
(ans+=1ll*mul*f[i]%mod)%=mod;
(mul*=3)%=mod;
}
printf("%lld\n", ans);
return 0;
}