又不会改了。
可能作为纸张就是这样吧。
A
注意到 A 是一个 0/1 序列，因此存在以下几点性质。
- $length \geq 2$ 的连续段是稳定的。
- 对于不稳定的段，每一次操作实际上就是将其取反。
- 取反后头尾可以和前面存在的连续段合并。
那么就很显然了，每一个不稳定的段需要 \lfloor \frac{len+1}{2} \rfloor 才能归位。
注意头尾永远都不会变，因此不能计入不稳定的段。
至于不稳定的段之后的答案，分两种。
- $len$ 是一个奇数，整个不稳定的段与旁边的段“融为一体”。
- $len$ 是一个偶数，对半开，前面 $\frac{len}{2}$ 不稳定串与前面“融为一体”，后面 $\frac{len}{2}$ 不稳定串与后面“融为一体”。
实现很简单。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=5e5+5;
int n,ans,a[N];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
vector<int>res;
res.push_back(a[1]);
for(int i=2;i<n;i++)
{
if(a[i]!=a[i-1]&&a[i+1]!=a[i])
{
int j=i,cnt=0;
while(j<n&&a[j]!=a[j-1]&&a[j+1]!=a[j])
{
cnt++;
j++;
}
ans=max(ans,(cnt+1)/2);
if(cnt&1)
{
while(cnt--)res.push_back(a[i-1]);
}
else
{
for(int k=1;k<=cnt/2;k++)res.push_back(a[i-1]);
for(int k=1;k<=cnt/2;k++)res.push_back(a[j]);
}
i=j-1;
}
else res.push_back(a[i]);
}
res.push_back(a[n]);
printf("%d\n",ans);
for(auto i:res)printf("%d ",i);
return 0;
}
D
树上有 n 个点，编号为 1 到 n 。在树上有 m 条路径，第 i 条路径从 x_i 到 y_i，且路径有一个权值为 w_i 。
有 q 个询问，每次问题会给出一条路径 u 到 v，要求回答 m 条路径中，和这条路径有公共点的路径的权值和是多少。
首先每一条路径都有一个性质，即由 w 个点和 w-1 条边构成。
一个很妙的trick：将点上 +w_i，边上 -w_i。
这样你会发现就算与某条路径有多个公共点也不会算重。
这样我们只需要树上差分一次，前缀和两次（一次从下往上跑，一次从上往下跑），就可以将 O(1) 算出答案。
实际维护时，很显然我们还是将边上的放到点上维护，注意边界与维护点时的细节。
时间复杂度 O((n+q) \log n ，\log n 是因为倍增求 LCA 带的。
还有为什么有人认为写挂的原因是没有开 __int128 啊。
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
typedef __int128 LL;
int n,m,q;
int h[N],e[N<<1],ne[N<<1],idx;
int d[N],fa[N][20];
LL ds[N],es[N];
void read(LL &x)
{
x=0;
int f=1;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9')
{
x=(x<<3)+(x<<1)+(c^48);
c=getchar();
}
x*=f;
}
void write(LL x)
{
if(x<0)
{
putchar('-');
x=~x+1;
}
if(x>9)write(x/10);
putchar(x%10^48);
}
void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;}
void dfs(int u,int father)
{
d[u]=d[father]+1;
fa[u][0]=father;
for(int j=1;j<=19;j++)fa[u][j]=fa[fa[u][j-1]][j-1];
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(j==father)continue;
dfs(j,u);
}
}
int LCA(int a,int b)
{
if(d[a]<d[b])swap(a,b);
for(int i=19;~i;i--)
{
if(d[fa[a][i]]>=d[b])a=fa[a][i];
}
if(a==b)return a;
for(int i=19;~i;i--)
{
if(fa[a][i]!=fa[b][i])
{
a=fa[a][i];
b=fa[b][i];
}
}
return fa[a][0];
}
void dfs2(int u)
{
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(j==fa[u][0])continue;
dfs2(j);
ds[u]+=ds[j];
es[u]+=es[j];
}
}
void dfs3(int u,int father)
{
ds[u]+=ds[father];
es[u]+=es[father];
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(j==father)continue;
dfs3(j,u);
}
}
int main()
{
freopen("soong.in","r",stdin);
freopen("soong.out","w",stdout);
memset(h,-1,sizeof h);
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<n;i++)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
dfs(1,0);
while(m--)
{
int a,b;
LL c;
scanf("%d%d",&a,&b);
read(c);
int lca=LCA(a,b);
if(lca==a)
{
ds[b]+=c;
ds[fa[lca][0]]-=c;
es[b]-=c;
es[lca]+=c;
}
else if(lca==b)
{
ds[a]+=c;
ds[fa[lca][0]]-=c;
es[a]-=c;
es[lca]+=c;
}
else
{
ds[a]+=c;
ds[b]+=c;
ds[lca]-=c;
ds[fa[lca][0]]-=c;
es[a]-=c;
es[b]-=c;
es[lca]+=2*c;
}
}
dfs2(1);
dfs3(1,0);
while(q--)
{
int a,b;
scanf("%d%d",&a,&b);
int lca=LCA(a,b);
if(lca==a)write(ds[b]-ds[fa[lca][0]]+es[b]-es[lca]);
else if(lca==b)write(ds[a]-ds[fa[lca][0]]+es[a]-es[lca]);
else write(ds[a]+ds[b]-ds[fa[lca][0]]-ds[lca]+es[a]+es[b]-2*es[lca]);
puts("");
}
return 0;
}