I. Max answer
链接：https://nanti.jisuanke.com/t/38228
思路:
枚举最小值，单调栈确定最小值的边界，用线段树+前缀和维护最小值的左右区间
实现代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1 const ll M = 5e5+;
const ll inf = 1e9;
ll a[M],Li[M],Ri[M],sum[M];
ll lmn[M<<],lmx[M<<],rmn[M<<],rmx[M<<],pre[M],nex[M];
void build(ll l,ll r,ll rt){
if(l == r){
lmn[rt] = nex[l];
lmx[rt] = nex[l];
rmn[rt] = pre[l];
rmx[rt] = pre[l];
return ;
}
ll m = (l + r) >> ;
build(lson); build(rson);
lmn[rt] = min(lmn[rt<<],lmn[rt<<|]);
rmn[rt] = min(rmn[rt<<],rmn[rt<<|]);
lmx[rt] = max(lmx[rt<<],lmx[rt<<|]);
rmx[rt] = max(rmx[rt<<],rmx[rt<<|]);
} ll getlmn(ll L,ll R,ll l,ll r,ll rt){
if(L <= l&&R >= r){
return lmn[rt];
}
ll m = (l + r) >> ;
ll ret = inf;
if(L <= m) ret = min(ret,getlmn(L,R,lson));
if(R > m) ret = min(ret,getlmn(L,R,rson));
return ret;
} ll getrmn(ll L,ll R,ll l,ll r,ll rt){
if(L <= l&&R >= r){
return rmn[rt];
}
ll m = (l + r) >> ;
ll ret = inf;
if(L <= m) ret = min(ret,getrmn(L,R,lson));
if(R > m) ret = min(ret,getrmn(L,R,rson));
return ret;
} ll getlmx(ll L,ll R,ll l,ll r,ll rt){
if(L <= l&&R >= r){
return lmx[rt];
}
ll m = (l + r) >> ;
ll ret = ;
if(L <= m) ret = max(ret,getlmx(L,R,lson));
if(R > m) ret = max(ret,getlmx(L,R,rson));
return ret;
} ll getrmx(ll L,ll R,ll l,ll r,ll rt){
if(L <= l&&R >= r){
return rmx[rt];
}
ll m = (l + r) >> ;
ll ret = ;
if(L <= m) ret = max(ret,getrmx(L,R,lson));
if(R > m) ret = max(ret,getrmx(L,R,rson));
return ret;
} int main()
{
ll n;
scanf("%lld",&n);ll ans = ,flag = ,mid = n+;
for(ll i = ;i <= n;i ++){
scanf("%lld",&a[i]);
if(a[i]>&&flag==) mid = i,flag = ;
ans += a[i]; pre[i] = ans;
}
ans = ;
for(ll i = n;i >= ;i --){
ans += a[i]; nex[i] = ans;
}
build(,n,);
stack<ll>s;
for(ll i = ;i <= n;i ++){
while(s.size()&&a[s.top()]>=a[i]) s.pop();
if(s.empty()) Li[i] = ;
else Li[i] = s.top()+;
s.push(i);
}
while(!s.empty()) s.pop();
for(ll i = n;i >= ;i --){
while(s.size()&&a[s.top()]>=a[i]) s.pop();
if(s.empty()) Ri[i] = n;
else Ri[i] = s.top()-;
s.push(i);
}
while(!s.empty()) s.pop();
ll cnt = ,num,mx=;
for(ll i = ;i <= n;i ++){
if(a[i] >= ){
cnt = a[i];
cnt += getlmx(Li[i],i,,n,)-nex[i];
cnt += getrmx(i,Ri[i],,n,)-pre[i];
mx = max(mx,cnt*a[i]);
//cout<<cnt<<" "<<getlmx(Li[i],i,1,n,1)<<" "<<getrmx(i,Ri[i],1,n,1)<<endl;
}
else{
cnt = a[i];
cnt += getlmn(Li[i],i,,n,)-nex[i];
cnt += getrmn(i,Ri[i],,n,)-pre[i];
mx = max(mx,cnt*a[i]);
//cout<<cnt<<" "<<getlmn(Li[i],i,1,n,1)-nex[i]<<" "<<getrmn(i,Ri[i],1,n,1)-pre[i]<<endl;
}
//cout<<a[i]<<" "<<Li[i]<<" "<<Ri[i]<<" "<<mx<<endl;
}
printf("%lld\n",mx);
}
J. Distance on the tree
链接：https://nanti.jisuanke.com/t/38229
思路;
序列上求任意区间有多少个数小于k
https://www.cnblogs.com/kls123/p/9568553.html
就是这道题扔到树上，一开始想复杂了，还以为是点对的数量。
从根节点向下遍历每次遍历到一条边看作是一次修改，下标为val的点+1
但是这种方法建的主席树是类似权值线段树的，下标和树是没关系的，有关系的是这是第几次修改的，所以在树上应该用root跳
注意 在树上跳的时候表示当前点前后的点时应该用fa[],son[]，而不是+1,-1.
实现代码：
#include<bits/stdc++.h>
using namespace std;
const int M = 3e5+;
int ls[M*],rs[M*],sum[M*],a[M],b[M],root[M];
int cnt1,cnt,head[M],dep[M],siz[M],fa[M],son[M],wt[M],top[M],tid[M],rk[M];
int idx,tot;
struct node{
int w,to,next;
}e[M*]; void add(int u,int v,int c){
e[++cnt1].to=v;e[cnt1].next=head[u];e[cnt1].w=c;head[u]=cnt1;
e[++cnt1].to=u;e[cnt1].next=head[v];e[cnt1].w=c;head[v]=cnt1;
}
void dfs1(int u,int faz,int deep){
dep[u] = deep;
siz[u] = ;
fa[u] = faz;
for(int i = head[u];i ;i=e[i].next){
int v = e[i].to;
if(v != fa[u]){
wt[v] = e[i].w;
dfs1(v,u,deep+);
siz[u] += siz[v];
if(son[u]==-||siz[v]>siz[son[u]])
son[u] = v;
}
}
} void dfs2(int u,int t){
top[u] = t;
tid[u] = tot;
rk[tot] = wt[u];
//cout<<1<<endl;
tot++;
if(son[u] == -) return ;
dfs2(son[u],t);
for(int i = head[u];i;i=e[i].next){
int v = e[i].to;
if(v != son[u]&&v != fa[u])
dfs2(v,v);
}
} void update(int old,int &k,int l,int r,int p){
k = ++idx;
ls[k] = ls[old]; rs[k] = rs[old];
sum[k] = sum[old] + ;
if(l == r) return ;
int mid = (l + r) >> ;
if(p <= mid) update(ls[old],ls[k],l,mid,p);
else update(rs[old],rs[k],mid+,r,p);
} int query(int old,int k,int L,int R,int l,int r){
if(L <= l&&R >= r) return sum[k] - sum[old];
int mid = (l + r) >> ;
int ret = ;
if(L <= mid) ret += query(ls[old],ls[k],L,R,l,mid);
if(R > mid) ret += query(rs[old],rs[k],L,R,mid+,r);
return ret;
} int ask(int x,int y,int l,int r){
int ans = ;
int fx = top[x],fy = top[y];
while(fx != fy){
if(dep[fx] < dep[fy]) swap(fx,fy),swap(x,y);
if(fx == ) ans += query(root[tid[fx]],root[tid[x]],l,r,,cnt);
else ans += query(root[tid[fa[fx]]],root[tid[x]],l,r,,cnt);
x = fa[fx]; fx = top[x];
}
if(x==y) return ans;
if(dep[x] > dep[y]) swap(x,y);
ans += query(root[tid[x]],root[tid[y]],l,r,,cnt);
return ans;
} void dfs(int u,int fa){
update(root[tid[fa]],root[tid[u]],,cnt,wt[u]);
for(int i = head[u];i;i=e[i].next){
int v = e[i].to;
if(v == fa) continue;
dfs(v,u);
}
} int l[M],r[M],x[M],u[M],v[M],w[M];
int Find(int x){
int num = lower_bound(b+,b++cnt,x)-b;
return num;
} int main()
{
int m,n;
scanf("%d%d",&n,&m); tot = ;
memset(son,-,sizeof(son));
for(int i = ;i < n;i ++){
scanf("%d%d%d",&u[i],&v[i],&w[i]);
b[i] = w[i];
}
for(int i = ;i <= m;i ++){
scanf("%d%d%d",&l[i],&r[i],&x[i]);
b[i+n-] = x[i];
}
sort(b+,b+n+m);
cnt = unique(b+,b+n+m)-b;
for(int i = ;i < n;i ++){
int num = Find(w[i]);
add(u[i],v[i],num);
}
dfs1(,,); dfs2(,);dfs(,);
for(int i = ;i <= m;i ++){
int num = Find(x[i]);
printf("%d\n",ask(l[i],r[i],,num));
}
}