推荐在我的博客 上浏览。 顺便征集友链qwq
高二T3
最简单的三层for循环肯定会吧，我自己现场出数据在1000以内都可过。
优化：考虑计算逆序对，在数值范围内建立树状数组：
int ask(int x) { if(x<1) return 0; int ans=0; while(x) ans+=c[x], x-=x&-x; return ans; } void add(int p, int x) { while(p<=N-5) c[p]+=x, p+=p&-p; } int main() { int n=read(); ll ans=0; for(int i=1; i<=n; i++) a[i]=read(); for(int i=n; i; i--) { b[a[i]]=ask(a[i]-1); add(a[i], 1); } for(int i=1; i<=n; i++) for(int j=i+1; j<=n; j++) if(a[i]>a[j]) ans+=b[a[j]]; printf("%lld", ans); return 0; }
如上述代码，我们求出了在某个数ai之后比它小的数的数量，我们用一个数组bi记录下来，就只需要两层循环了。
优化++：但上述方式只能得90分，正解应该是再统计一遍ai之前比它大的数的数量ci，那么显然有：
以ai为中间数的“弱点”的个数=bi*ci，累加即可。
#include<iostream> #include<cstdio> using namespace std; const int N=1000005; typedef long long ll; inline int read() { int t=0, f=0; char c; while(!isdigit(c=getchar())) f|=(c=='-'); do t=(t<<3)+(t<<1)+c-'0'; while(isdigit(c=getchar())); return f? -t:t; } int a[N], b[N], t_post[N], t_pre[N]; int ask(int x, int t[]) { if(x<1) return 0; int ans=0; while(x) ans+=t[x], x-=x&-x; return ans; } void add(int p, int x, int t[]) { while(p<=N-5) t[p]+=x, p+=p&-p; } int main() { int n=read(), zd=0; ll ans=0; for(int i=1; i<=n; i++) a[i]=read(), zd=max(zd, a[i]); for(int i=n; i; i--) { b[a[i]]=ask(a[i]-1, t_post); //统计在ai之后比它小的数的数量 add(a[i], 1, t_post); } for(int i=1; i<=n; i++) { ans+=(ll)(ask(zd, t_pre)-ask(a[i], t_pre))*b[a[i]]; add(a[i], 1, t_pre); } printf("%lld", ans); return 0; }
高一T5
对于1-3个点，可以看出就是求区间最大值，对于100000规模的数据暴力扫过就好了，为什么没有人拿分呢qwq
对于4-6个点，我们可以根据深度dep将深度大的节点拉到与深度低的节点的同一深度，沿途更新答案。
若同深度之后两节点重合，则答案显然，不然则同时将两节点向上拉（赋值为自身父亲的值），更新答案。
zky的40分代码（1,4,5,6）：
#include<cstdio> #include<iostream> #include<vector> #include<cstring> using namespace std; const int maxn = 1000005; int n, m, k, rt, ans, flag, from, to; int f[maxn], val[maxn]; int deep[maxn]; inline int read() { int t=0, f=0; char c; while(!isdigit(c=getchar())) f|=(c=='-'); do t=(t<<3)+(t<<1)+c-'0'; while(isdigit(c=getchar())); return f? -t:t; } void deal(int x, int y) { int t = deep[x] > deep[y] ? x : y, s = x == t ? y : x; while(deep[t] > deep[s]) ans = max(ans, val[t]), t = f[t]; while(s != t) ans = max(ans, max(val[t], val[s])), t = f[t], s = f[s]; } int main(void) { n=read(), m=read(), k=read(); rt=read(), rt=read(); deep[rt] = 1; rt=read(), rt=read(); for(int i = 2; i <= k; ++i) { int b=read(); for(int j = 1; j <= b; ++j) { int x=read(); f[x]=read(); val[x]=read(); deep[x] = i; } } while(m--) { from=read(), to=read(); ans = 0; deal(from, to); printf("%d\n", ans); } }正解：树上倍增，仿照LCA的倍增求法，fa[i][j]代表i的2^j辈祖先，zd[i][j]则代表i到它的2^j辈祖先路径上最长边的边权，则有 $$ fa[x][i]=fa[fa[x][i-1]][i-1] $$ $$ zd[x][i]=max(zd[x][i-1], zd[fa[x][i-1]][i-1]); $$
正解代码：
#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1000005, INF=0x3f3f3f3f;
int dep[N], fa[N][25], zd[N][25], t;
inline int read()
{
int t=0, f=0; char c;
while(!isdigit(c=getchar())) f|=(c=='-');
do t=(t<<3)+(t<<1)+c-'0';
while(isdigit(c=getchar()));
return f? -t:t;
}
int Solve(int x, int y)
{
if(x==y) return 0;
if(dep[x]<dep[y]) swap(x, y);
int ans=0;
for(int i=t; i>=0; i--) if(dep[fa[x][i]]>=dep[y])
ans=max(ans, zd[x][i]), x=fa[x][i];
if(x==y) return ans;
for(int i=t; i>=0; i--) if(fa[x][i]!=fa[y][i])
ans=max(ans, max(zd[x][i], zd[y][i])), x=fa[x][i], y=fa[y][i];
return max(ans, max(zd[x][0], zd[y][0]));
}
int main()
{
int n=read(), m=read(), k=read(), x, y;
t=log(n)/log(2);
while(k--) if(y=read())
while(y--)
{
x=read(), fa[x][0]=read(), zd[x][0]=read();
dep[x]=dep[fa[x][0]]+1;
for(int i=1; i<=t; i++)
fa[x][i]=fa[fa[x][i-1]][i-1],
zd[x][i]=max(zd[x][i-1], zd[fa[x][i-1]][i-1]);
}
while(m--) printf("%d\n", Solve(read(), read()));
return 0;
}
