A

发现操作相当于花费 $x$ 消掉一个 $0$ 的连续段，或者是花费 $y$ 将两个连续段拼起来，显然如果使用了拼接操作就会拼到只剩一个，所以直接判断即可。

B

打表发现在 $n$ 较大的时候是个等差数列，小范围暴力即可。

一个比较有理有据的做法是首先考虑我们先将集合转化为 $\{0,4,9,49\}$ 考虑，然后我们为了保证不重，必须限制 $4$ 的个数 $\leq 8$ 个，并且如果取了 $4$，那么为了去重也只能取 $\leq 4$ 个 $9$，没有取 $4$ 就可以取 $\leq \gcd(49,9)=9$ 个。剩下的用 $0$ 和 $49$ 填充即可。

通过整体平移让某一个出现 $0$ 是很不错的套路，可以直接少考虑一个维度。

C

必然是容斥原理。我们去枚举多少行多少列是相同颜色的，设 $f(i,j)$ 表示 $i$ 行 $j$ 列每行每列相同颜色的方案数，答案就是：

$$ \sum_{i=0}^n \sum_{j=0}^n [i+j \neq 0](-1)^{i+j+1}\binom n i\binom n j f(i,j) $$

其中：

$$ \begin{aligned} f(i,j) = \begin{cases} 3^{n(n-j)} \times 3^j ,&i=0\\ 3^{(n-i)n} \times 3^i, &j=0\\ 3^{(n-i)(n-j)} \times 3,& \text{otherwise} \end{cases} \end{aligned} $$

接下来考虑如何优化：首先 $i=0$ 和 $j=0$ 的情况比较平凡，我们只需要考虑算：

$$ -3\sum_{i=1}^n (-1)^i\binom n i\sum_{j=1}^n (-1)^{j}\binom n j 3^{(n-i)(n-j)} $$

对后面用二项式定理，后面的式子等价于 $(3^{n-i}-1)^n-3^{(n-i)n}$，就可以 $O(n \log n)$ 计算了。

同时算多个 $n$ 的答案感觉可以卷积。。不错以后出了。

D

首先要直观理解一下在图上怎么走路的：你从 $(u,v)$ 可以走到 $(u,w)$满足树 $2$ 上有边 $(v,w)$，树 $1$ 同理。

主要是要观察到一个性质：两棵树起点确定，长度为 $x,y$ 的环能组合出长度为 $x+y$ 的环，方案是 $\binom {x+y} x$。

所以我们对树分开处理，只需要对于每棵树处理出长度 $=i$ 的环的个数就行了（在环上每个点都要贡献一次），如果我们现在求 $1$ 号点的环个数，可以将这个点设为根，然后设 $f_{i,j}$ 表示从 $i$ 开始的长度为 $j$ 的环的数量。

考虑写出生成函数 $F_i = \sum_{j} f_{i,j}x^j$，考虑如何用生成函数的形式刻画转移：

首先我们可以算出 $G_i$ 表示经过 $i$ 一次的情况，显然有 $G_i = x^2\sum{v \in son_i} F_{v}$，$x^2$ 是因为要走回来，那么就可以得到 $F_i = \sum_{j \geq 0} G_i^j = \frac{1}{1-G_i}$，所以多项式求逆就可以求出来了。

但是因为要求出所有点的答案，所以我们要考虑换根：实际上就是去掉/加入一些子树，先修改 $G$ 再修改 $F$ 即可。

这样复杂度是 $O(nk \log k)$ 的，但是由于 $k$ 很小并且 NTT 常数巨大跑不过 $O(nk^2)$ 的做法。

官方题解给的做法是用那个 dp 套在点分治上，也是很妙的，对这种类似路径条数和连通块的问题我们可以考虑点分治每次只 dp 分治区域内所有的点。

E

先考虑如果全局询问怎么做：

因为是排列，限制可以拆成 $r-l = mx-mn$，并且我们发现一定有 $r-l \leq mx-mn$，也就是 $r \leq mx-mn+l$，所以我们枚举右端点，线段树维护所有左端点的 $mx-mn+l$，每次如果存在合法的区间值一定是最小值 $r$，记录最小值个数即可，维护单调栈每次更新即可。

这个题是要对一个子区间全部做，相当于要维护历史贡献信息：对于这种题我们线段树上记一个值专门用来存答案，每次更新完右端点的操作后我们在根打一个答案标记，答案标记下传到某个儿子当且仅当这个点儿子的最小值和父亲的最小值相等，并且一定要在加法下传后再下传（因为前面的加法标记都是应该加完后判断的），然后查询就区间查询和就好了。

建议看代码意会一下。。这个东西感觉是可以扩展的，好多利用线段树枚举左端点维护右端点的题都可以改改做了。核心思想还是每次修改前肯定先处理完标记再下传，那么统计答案的标记优先级一定小于修改的标记。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 3e5 + 5;

int mn[MAXN<<2],cnt[MAXN<<2],tag[MAXN<<2];
LL res[MAXN<<2],tag2[MAXN<<2];
#define lc ((x)<<1)
#define rc ((x)<<1|1)

inline void pushup(int x){
    mn[x] = std::min(mn[lc],mn[rc]);cnt[x] = 0;
    if(mn[x] == mn[lc]) cnt[x] += cnt[lc];
    if(mn[x] == mn[rc]) cnt[x] += cnt[rc];
}

inline void cover(int x,int d){
    mn[x] += d;tag[x] += d;
}

inline void cover2(int x,int mn,int d){
    if(::mn[x] != mn) return;
    res[x] += 1ll*cnt[x]*d;tag2[x] += d;
}// 注意这个标记是后打的 所以最后pushdown这个标记

inline void pushdown(int x){
    if(tag[x]){
        cover(lc,tag[x]);
        cover(rc,tag[x]);
        tag[x] = 0;
    }
    if(tag2[x]){
        cover2(lc,mn[x],tag2[x]);
        cover2(rc,mn[x],tag2[x]);
        tag2[x] = 0;
    }
}

inline void modify(int x,int l,int r,int L,int R,int d){
    if(l == L && r == R){
        cover(x,d);return;
    }
    int mid = (l + r) >> 1;pushdown(x);
    if(R <= mid) modify(lc,l,mid,L,R,d);
    else if(L > mid) modify(rc,mid+1,r,L,R,d);
    else modify(lc,l,mid,L,mid,d),modify(rc,mid+1,r,mid+1,R,d);
    pushup(x);
}

inline void build(int x,int l,int r){
    if(l == r){
        mn[x] = l;cnt[x] = 1;
        return;
    }
    int mid = (l + r) >> 1;
    build(lc,l,mid);build(rc,mid+1,r);
    pushup(x);
}

inline LL query(int x,int l,int r,int L,int R){
    if(l == L && r == R) return res[x];
    int mid = (l + r) >> 1;pushdown(x);
    if(R <= mid) return query(lc,l,mid,L,R);
    if(L > mid) return query(rc,mid+1,r,L,R);
    return query(lc,l,mid,L,mid)+query(rc,mid+1,r,mid+1,R);
}

int a[MAXN];
int n;
int stk1[MAXN],stk2[MAXN],tp1,tp2;
// 后缀加
std::vector<P> G[MAXN];
LL ans[MAXN];

int main(){
    scanf("%d",&n);
    FOR(i,1,n) scanf("%d",a+i);
    int q;scanf("%d",&q);
    FOR(i,1,q){
        int l,r;scanf("%d%d",&l,&r);
        G[r].pb(MP(l,i));
    }
    build(1,1,n);
    // 1=min,2 = max
    // r-l = mx-mn
    // r = mx-mn+l
    FOR(i,1,n){
        while(tp1 && a[stk1[tp1]] <= a[i]){// max
            modify(1,1,n,stk1[tp1-1]+1,stk1[tp1],-a[stk1[tp1]]);
            --tp1;
        }
        while(tp2 && a[stk2[tp2]] >= a[i]){// min
            modify(1,1,n,stk2[tp2-1]+1,stk2[tp2],a[stk2[tp2]]);
            --tp2;
        }
        modify(1,1,n,stk1[tp1]+1,i,a[i]);
        modify(1,1,n,stk2[tp2]+1,i,-a[i]);
        stk1[++tp1] = i;stk2[++tp2] = i;
        cover2(1,mn[1],1);
        for(auto x:G[i]) ans[x.se] = query(1,1,n,x.fi,i);
    }
    FOR(i,1,q) printf("%lld\n",ans[i]);
    return 0;
}