A 小y的平面

签到题，看看后面的 $(x,y)(x,y)$ 是不是都不小于前面的就行了

B 小y的树

考虑每条边会经过几次
设置 all 为整个树的节点数 $1+k+k^2+\cdots +k^{n-1}=1\frac{1-k^n}{1-k}1+k+k^2+\backslash dots+k^\{n-1\}=1\backslash frac\{1-k^n\}\{1-k\}$
对于第 $ii$ 层的边，有 $k^{i}k^i$ 个同层边
这条边连接的子树有 $1+k+k^2+\cdots +k^{n-i-1}=1\frac{1-k^{n-i}}{1-k}1+k+k^2+\backslash dots+k^\{n-i-1\}=1\backslash frac\{1-k^\{n-i\}\}\{1-k\}$ 个点（设为 son），那么其余就有 $els=all-sonels=all-son$ 个点
子树上每个点与其余点的路径都会经过此边 $son\times allson\backslash times\; all$ 次
所以这一层对答案的贡献即为 $son\times els\times k^{i}son\backslash times\; els\backslash times\; k^i$
遍历 $i:1\to ni:1\backslash to\; n$ 即可得到结果

const int mod = 1e9 + 7;

inline ll ksm ( ll a, ll b ) { ll res = 1; while ( b ) { if ( b & 1 ) res = res * a % mod; a = a * a % mod; b >>= 1; } return res; }
inline ll inv ( ll a ) { return ksm(a, mod - 2); }
inline ll add ( ll a, ll b ) { return (a + b) % mod; }
inline ll sub ( ll a, ll b ) { return ((a - b) % mod + mod) % mod; }

ll n, k;
ll all;

int main () {
        cin >> n >> k;
        all = sub(ksm(k, n), 1) * inv(k - 1) % mod;

        ll num = 1;
        ll res = 0;
        for ( int i = 1; i <= n; i ++ ) {
                ll son = sub(ksm(k, n - i), 1) * inv(k - 1) % mod;
                ll els = sub(all, son);
                num = num * k % mod;
                res += num * els % mod * son % mod;
                res %= mod;
        } 
        cout << res << endl;
}

C 小y的序列

首先要敏感区间 $max\mathrm{\mid }minmax|min$
固定左端点区间 $maxmax$ 递增，$minmin$ 递减，那么 $max-minmax-min$ 递增
单调性有了
（本来因为单调性秒写边界二分 $TT$ 了几发
单调性还有一个应用的地方是双指针
我们遍历 $l:1\to nl:1\backslash to\; n$
途中维护

• $r1r1$ 是满足 $max[l\to r1]-min[l\to r1]=kmax[l\backslash to\; r1]-min[l\backslash to\; r1]=k$ 的左边界
• $r2r2$ 是满足 $max[l\to r1]-min[l\to r1]=kmax[l\backslash to\; r1]-min[l\backslash to\; r1]=k$ 的右边界

如果存在这样的区间，那么就 $res+=r2-r1+1res+=r2-r1+1$ 即可
对于区间查询当然是上线段树啦

const int N = 1e6 + 10;

int n, k;
int a[N];

struct sgtr {
        int mn;
        int mx;
} t[N << 2];
inline void PushUp ( int rt ) {
        t[rt].mx = max(t[rt << 1].mx, t[rt << 1 | 1].mx);
        t[rt].mn = min(t[rt << 1].mn, t[rt << 1 | 1].mn);
}
inline void Build ( int l, int r, int rt ) {
        if ( l == r ) {
                t[rt] = {a[l], a[l]};
                return;
        }
        int mid = (l + r) >> 1;
        Build(l, mid, rt << 1);
        Build(mid + 1, r, rt << 1 | 1);
        PushUp(rt);
}
// second: max   first: min
inline pair<int, int> Query ( int a, int b, int l = 1, int r = n, int rt = 1 ) {
        if ( a <= l && r <= b ) return {t[rt].mn, t[rt].mx};
        if ( r < a || b < l ) return {0x3f3f3f3f, 0};
        int mid = (l + r) >> 1;
        pair<int, int> res;
        pair<int, int> q1 = Query(a, b, l, mid, rt << 1);
        pair<int, int> q2 = Query(a, b, mid + 1, r, rt << 1 | 1);
        res.first = min(q1.first, q2.first);
        res.second = max(q1.second, q2.second);
        return res; 
}

int main () {
        scanf("%d%d", &n, &k);
        for ( int i = 1; i <= n; i ++ ) {
                scanf("%d", &a[i]);
        }
        Build(1, n, 1);
        ll res = 0;
        int l = 1, r1 = 1, r2 = 1;
        for ( ; l <= n; l ++ ) {
                pair<int, int> qry = Query(l, r1);
                while ( r1 <= n && qry.second - qry.first < k ) r1 ++, qry = Query(l, r1);
                qry = Query(l, r2);
                while ( r2 <= n && qry.second - qry.first <= k ) r2 ++, qry = Query(l, r2);
                r2 --;
                if ( r1 <= n ) res += (ll)r2 - (ll)r1 + 1;
                else break;
        }
        printf("%lld\n", res);
}

D 小y的质因数

设 $xx$ 的质因数个数为 $numpnump$
题目要求为

$k\le 10k\backslash le\; 10$ 是一个突破口
由于数越大它的 $loglog$ 也就越大，需要的质因数就会更多才能满足 $lo{g}_{2}x-nump\le 10log\_2x-nump\backslash le10$，所以质因数用的不会太多

想得到最大质因数，让质因数个数尽可能小，那么 $k=10k=10$ ，$10^{12}10^\{12\}$ 下 $549755813888=2^{39}549755813888=2^\{39\}$ 有 $3939$ 个质因数，$k=10k=10$ 时有 $2929$ 个质因数，让 $2828$ 个都是最小的 $22$ ，那么剩下一个我们估算一下范围 $10^{12}\mathrm{/}{2}^{28}=372510^\{12\}/2^\{28\}=3725$ （这还是说大了），那么我们就把质因数上限设到 $4\times 10^{3}4\backslash times\; 10^3$

那么我们从 $11$ 开始向上乘质数地 DFS
如果 $lo{g}_{2}x-nump>10log\_2x-nump>10$ 就可以退出程序
如果质数用完了，就可以将其存入一个 vector[Log2(x)-nump] 中，记录一下 $lo{g}_{2}x-numplog\_2x-nump$ 是出现过 $xx$ 的

统计答案的时候枚举 $i:1\to ki:1\backslash to\; k$ ，在 vector[i] 里面二分出在 $[l,r][l,r]$ 内的左右边界，累加中间的个数即可

const int N = 5e3 + 10;
vector<int> prime; // 质数表
int ntp[N];

inline void Sieve () { // 筛
        ntp[0] = ntp[1] = true;
        for ( int i = 2; i < N; i ++ ) {
                if ( !ntp[i] ) prime.push_back(i);
                for ( int j = 0; j < prime.size() && i * prime[j] < N; j ++ ) {
                        ntp[i * prime[j]] = true;
                        if ( i % prime[j] == 0 ) break;
                }
        }
}


inline int Log2 ( ll x ) {
        double X = x;
        if ( X == 1 ) return 0;
        return ((* (unsigned ll*) &X >> 52) & 1023) + 1 + !(x == (x & (-x)));
}


vector<ll> num[11]; // 存入每个 Log2(x)-nump
inline void DFS ( int idp, ll x, int nump ) { // 第 idp 个质数，当前数为 x，有 nump 个质因数
        if ( Log2(x) - nump > 10 ) return;
        if ( idp == prime.size() ) {
                num[Log2(x) - nump].push_back(x);
                return;
        }
        for ( int i = 0; x <= 1e12; x *= prime[idp], i ++ ) { // i：第idp个质数用的次数
                DFS(idp + 1, x, nump + i);
        }
}       

inline void Solve () {
        ll l, r; int k; cin >> l >> r >> k;
        int res = 0;
        for ( int i = 0; i <= k; i ++ ) {
                res += upper_bound(num[i].begin(), num[i].end(), r) - lower_bound(num[i].begin(), num[i].end(), l);
        }
        cout << res << endl;
}

int main () {
        ios::sync_with_stdio(false); 

        Sieve(); 
        DFS(0, 1, 0);
        for ( int i = 0; i <= 10; i ++ ) sort ( num[i].begin(), num[i].end() );

        int cass; cin >> cass; while ( cass -- ) {
                Solve ();
        }
}

剩下的正在补...