0629今日知识点总结：

T1：

看时间复杂度，我们需要一定的优化。

我们当访问到一个访问过的节点，那么其子树一定被变成 \(0\)，因此，我们可以直接返回。

此外，这里还有一点隐藏的数据结构特点：

对于结构体存邻接表和单独数组存邻接表和vector存时间复杂度不同。

这里记住

1. 开 \(O^2\) 的情况下，结构体时间复杂度低。
2. 如果读入较多，用数组比较好，因为 \(push_back()\) 操作较慢。
3. 如果要遍历图好多遍，用vector比较好。

T2:

换根 \(dp\)：
先考虑如何求 \(x=1\) 时的答案，以为 \(1\) 为根dfs，同时维护一个数据结构用来查询到根路径上有多少个点 \(a_i\) 大于当前点。

然后通过换根dp,记录从 \(fa\) 到 \(x\)时，父亲一侧增加了多少值和当前节点一侧减少了多少值，记录，输出答案 \(O(1)\) 即可。

void dfs1(int x,int fa){
    L[x]=query(w[x]-1);//当前节点小的贡献
    R[x]=query(w[fa]-1);//父亲节点小的贡献
    charu(w[x],-1);     
    for(int i=head[x];i;i=nxt[i]){
        int y=ver[i];
        if(y==fa) continue; 
            dfs1(y,x);
    }
    L[x]-=query(w[x]-1);
    R[x]-=query(w[fa]-1);
    L[x]=w[x]-1-L[x];
}
void dfs2(int x,int fa){
    ans+=query(n)-query(w[x]);
    charu(w[x],1);
    for(int i=head[x];i;i=nxt[i]){
        int y=ver[i];
        if(y==fa) continue;
        res[y]=res[x]+L[y]-R[y];
        dfs2(y,x);
    }
    charu(w[x],-1);
}

T3：

首先需要学会求子序列的个数：

if(!last[a[i]]) dp[i]=dp[i-1]*2+1;
if(last[a[i]]) dp[i]=dp[i-1]*2-dp[last[i]-1];

\(dp[i]\) 表示前 \(i\) 位的方案数， \(last[a[i]]\) 表示最近的与 \(a[i]\) 相同字符的位置，如果第一次出现，则 \(last[i]=0\)。

现在我们考虑矩阵。

设矩阵 \(A\) ，\(A[i][j]\) 表示以 \(i\) 开头，在结尾预支一个 \(j\) 的方案数。
对于一个数 \(i\) 的初始矩阵，对角线的元素和第 \(i\) 行都是 \(1\),我们可以发现两个状态矩阵的合并就是矩阵乘法。

用线段树支持查询和修改，同时运用重载运算符。

线段树部分：

void init(int now,int l,int r){
	if(l==r){
		t[now]=G(s[l]);
		return ;
	}
	rei mid=l+r>>1;
	init(now<<1,l,mid),init(now<<1|1,mid+1,r);
	t[now]=t[now<<1]*t[now<<1|1];
}

void update(int now,int l,int r,int pos){
	if(l==r){
		t[now]=G(s[l]);
		return ;
	}
	rei mid=l+r>>1;
	if(pos<=mid) update(now<<1,l,mid,pos);
	else         update(now<<1|1,mid+1,r,pos);
	t[now]=t[now<<1]*t[now<<1|1];
}

Mx query(int now,int l,int r,int L,int R){
	if(L<=l && r<= R) return t[now];
	rei mid=l+r>>1;
	Mx A;
	A.unit();
	if(L<=mid) A=A*query(now<<1,l,mid,L,R);
	if(R>mid) A=A*query(now<<1|1,mid+1,r,L,R);
	return A;
}

T4:

思路：
先令 \(b_i=d_i-d_{i-1}\) ,那么我们相当于每次选取 \(l<r\),令 \(b_l-1\) , \(b_r+1\) ,代价\((r-l)^2\)令所有 \(b\) 变成 \(0\)。
容易发现最短时间为\(\sum_i\max(b_i,0)\)。

我们需要每次选择的 \(b_l>0,b_r<0\)。
考虑一种贪心策略，遍历\(b_i\)，若有 \(b_i>0\) 将其压入队列。
\(b_i<0\)则:

1. 若使得代价最大，与最靠左的 \(b_l\) 配对。
2. 若使得代价最小，与最靠右的 \(b_l\) 配对。
   可以用交换法证明贪心的正确性。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=3e5+5,mod=1e9+7;
ll n,d[N],s[N],ans_day,min_ans,max_ans;
ll sta[N],l=0,r=1;
void calc1(){
    for(int i=1;i<=n;++i){
		if(s[i]<=0) continue;
		if(l<r) break;
		while(s[i]+s[sta[r]]>=0&&l>=r){
			min_ans=(min_ans+(sta[r]-i)*(sta[r]-i)*abs(s[ sta[r] ]))%mod;
			s[i]+=s[ sta[r] ];
			s[ sta[r] ]=0;
			++r;
		}
		if(s[i]==0 || l<r) continue;
		min_ans=(min_ans+(sta[r]-i)*(sta[r]-i)*s[i])%mod;
		s[ sta[r] ]+=s[i];
		s[i]=0;
	}
	for(int i=1;i<=n;++i){
		if(s[i]<=0) continue;
		min_ans=(min_ans+(n+1-i)*(n+1-i)*s[i])%mod;
		s[i]=0;
	}
}
void calc2(){
    l=0;r=1;
    for(int i=1;i<=n;++i) s[i]=d[i]-d[i-1];
	for(int i=n;i;--i){
		if(s[i]==0) continue;
		if(s[i]<0){
			sta[++l]=i; continue;
		}
		while(s[i]+s[ sta[l] ]>=0 && l>0){
			max_ans=(max_ans+(sta[l]-i)*(sta[l]-i)*abs(s[sta[l]]))%mod;;
			s[i]+=s[ sta[l] ];
			s[sta[l]]=0;--l;
		}
		if(!s[i] || !l) continue;
		max_ans=(max_ans+(sta[l]-i)*(sta[l]-i)*s[i])%mod;
		s[ sta[l] ]+=s[i];
		s[i]=0;
	}
	for(int i=1;i<=n;++i){
		if(s[i]==0) continue;
		max_ans=(max_ans+(n+1-i)*(n+1-i)*s[i])%mod;
		s[i]=0;
	}
}
int main(){
	freopen("road.in","r",stdin);
	freopen("road.out","w",stdout);
	scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%lld",&d[i]);
	for(int i=1;i<=n;++i){
		s[i]=d[i]-d[i-1];
		if(s[i]>0) ans_day+=s[i];
		if(s[i]<0) sta[++l]=i;
	}
    calc1();
    calc2();
    printf("%lld\n%lld\n%lld\n",ans_day,max_ans%mod,min_ans%mod);
    // system("pause");
	return 0;
}