D. Dark LaTeX vs. Light LaTeX

题意：

给你两个字符串、，分别从 和 中找出一段非零的、连续的子串，将组成 = + ，要求长度为偶数，且前一半与后一半相等。输出满足这样的条件的字符串的数量（可以重复）。

input

abab
ab

output

8

数据范围

，

分析

首先思考：我们应该怎么找，才能不重不漏呢？我们为什么会有这样的问题？因为我们有两个串。

但我们只考虑一个串的时候，会有很多方法能够做到这一点。进一步的，如果，那我们发现短的这个串是被长的这个串给限制住的。但是如果我们只有短的串，长的串会有很多情况。因此我们可以想到我们可以枚举长串，这样的短串是固定的，直接加上短串的数量即可。后面约定 。

好现在我们已经确定好顺序了。既然的前半等于后半，那么可以知道的是，至少存在一个前缀等于后缀。但是这样还是很复杂，我们应该对此进行优化。我们发现长串决定短串，而的全部信息都在中，为什么不枚举的前半部分呢？即枚举的，这样其实就已经确定了。

如果，直接不可能。
如果，有多少情况？我们发现可扩展的长度是和的。比如，我们找到，有这样两个串：，，这两个串都是前缀等于后缀的。也就是和的个。对于这两个串，我们发现我们要找的是：、。此时又可以发现，这两个串都是以为结尾的。原因很显然，无论是多少，是必然要找的，但是前面可以缩短。也就是。

我们貌似还是不好统计。但是“固定”这个性质是非常好的。记 为 中以 结尾、 中以 结尾的最长长度。现在 = 。如果 大于，那么贡献就是。如果小于，贡献就是0。否则就是 。发现我们这一步用到的性质，是中的一个位置（），与 中所有的位置的信息。我们可以对中的每一个位置开一个数组。如果我现在需要找长度为，那么有以下性质：
||贡献|
|---|---|
|||
|||
|||
|||
|||
|||

最后处理一下长度相等的。信息可以在数组中得到。
为方便处理长串和短串，在讨论的时候，对和进行即可。
所以我们只需求出和即可。时间复杂度。

code

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define X first
#define Y second
#define umap unordered_map
using ll = long long;
using ull = unsigned long long;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int maxn = 2e5 + 5, mod = 1e9 + 7, maxp = 31, inf = 1e9;
const ll INF = 1e18;
const double eps = 1e-6;
const int N = 5005;

int lcs[N][N], lcp[N][N];
int f[N][N], g[N][N];

void solve() {
    string ss, tt;
    cin >> ss >> tt;
    const int n = ss.size(), m = tt.size();
    ll ans = 0;

    bool ok = true;

    auto work = [&](string s, string t) {
        const int n = s.size(), m = t.size();
        s = " " + s;
        t = " " + t;
        const int N = max(n, m);

        memset(lcp, 0, sizeof lcp);
        memset(lcs, 0, sizeof lcs);
        memset(f, 0, sizeof f);
        memset(g, 0, sizeof g);

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (s[i] == t[j]) {
                    lcs[i][j] = lcs[i - 1][j - 1] + 1;
                }
                else {
                    lcs[i][j] = 0;
                }
            }
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                int len = lcs[i][j];
                if (len) {
                    f[i][len]++;
                    if (ok) {
                        ans += len;
                    }
                }
            }
        }

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                g[i][j] = j * f[i][j] + g[i][j - 1];
            }
        }

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                f[i][j] += f[i][j - 1];
            }
        }

        for (int i = n; i >= 1; i--) {
            for (int j = i - 1; j >= 1; j--) {
                if (s[i] == s[j]) {
                    lcp[j][i] = lcp[j + 1][i + 1] + 1;
                }
                else {
                    lcp[i][j] = 0;
                }
            }
        }
    
        // 这里枚举的位置是l和r + 1
        for (int p1 = 1; p1 <= n; p1++) {
            for (int p2 = p1 + 2; p2 <= n; p2++) {
                if (p2 == p1 + 1) continue;
                int lo = max(1, p2 - (p1 + lcp[p1][p2] - 1) - 1);
                int hi = p2 - p1 - 1;
                int len = hi - lo + 1;
                ans += g[p2 - 1][hi] - g[p2 - 1][lo - 1] - 1ll * (lo - 1) * (f[p2 - 1][hi] - f[p2 - 1][lo - 1]) + 1ll * (f[p2 - 1][m] - f[p2 - 1][hi]) * len;
            }
        }

        ok = false;
    };

    work(ss, tt);
    reverse(ss.begin(), ss.end());
    reverse(tt.begin(), tt.end());
    work(tt, ss);

    cout << ans << endl;
} 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int tt = 1;
    // cin >> tt;
    while (tt--) solve();
    return 0;
}

I. Three Rectangles

看似过题人数I < B < D，实际I题非常非常水。

题意：

给你一个高为，宽为的长方形，再给你三个小长方形， () 和 ()，不能越界、旋转，但是可以重叠，问有多少方案数，使得这个大长方形能被三个小长方形铺满。答案对取模。

input

10

2 2
1 1
1 1
1 1

2 2
1 1
1 2
1 2

2 2
1 1
1 2
2 1

2 2
1 2
1 2
1 2

2 2
1 2
1 2
2 1

1 3
1 1
1 2
1 3

1 4
1 1
1 2
1 3

1 5
1 1
1 2
1 3

1 6
1 1
1 2
1 3

1000000000 1000000000
1 1
1 1
1000000000 1000000000

output

0
8
4
6
4
6
12
14
6
2401

数据范围

有样例数，；
。

分析

切入点是四个角。这四个角上是肯定要放的。所以想枚举四个角放谁。
但是这样是有问题的。如果一个长方形占了两个角甚至四个角呢？想到这个点之后就有新的思路了。如果有一个长方形占了大于一个角，那么肯定有。有了这个新想法，我们就可以从这个想法入手了。分以下几种情况。

下面记为的个数。同理，swap即可。
1. 存在 and 。此时随便放即可。

if (h[i] == H && w[i] == W) {
    ll ans = 1;
    for (int j = 0; j < 3; j++) {
        ans = ans * (H - h[j] + 1) % mod * (W - w[j] + 1) % mod;
    }
    cout << ans << endl;
    return;
}

2. 。这是最复杂的一种情况了，但也不难。此时长方形退化成了一条线段。因为要做到不重不漏，我们可以枚举谁靠着最左端（下称），谁靠着最右端（下称）。因为有可能有重叠的部分会重复计算（重叠是指有两个放在最左端，两个放在最右端），因此我们分离开来。

• 先讨论不重叠的情况。如果，那么除了最左最右端是随便放的。否则，能放的最大位置就是贴着，能放的最小位置就是贴着。
• 那么重叠的部分呢？显然不可能三个都贴着一端。此时枚举谁单独在一端就行了，剩下两个重叠。由于左右端可以互换，因此一旦满足就需要。

if (cnt == 3) {
    ll s = 0;
    for (int i = 0; i < 3; i++) {
        s += w[i];
    }
    if (s < W) {
        cout << 0 << endl;
        return;
    }

    vector<int> p(3);// p与上文意义相同
    iota(p.begin(), p.end(), 0);
    ll ans = 0;
    do {
        if (w[p[0]] + w[p[2]] < W) {
            ll mn = max(1ll, W - w[p[2]] - w[p[1]]);
            ll mx = min(W - w[p[1]] - 1, w[p[0]]);
            ans += mx - mn + 1;
            ans %= mod;
        }
        else {
            ans += max(0ll, W - w[p[1]] - 1);
            ans %= mod;
        }
    } while (next_permutation(p.begin(), p.end()));

    for (int i = 0; i < 3; i++) {
        for (int j = i + 1; j < 3; j++) {//i和j是两个重叠的
            int k = 3 - i - j;
            if (max(w[i], w[j]) + w[k] >= W) {
                ans += 2;
            }
        }
    }
    cout << ans % mod << endl;
    return;
}

3. 。这就非常好判断了。你会发现如果满足的这两个中间留了一条缝，那么答案肯定是。否则，这两个已经把所有空间占满了。剩下的那个随便放即可。

if (cnt == 2) {
    int p1 = -1, p2 = -1;
    for (int i = 0; i < 3; i++) {
        if (h[i] == H) {
            if (p1 == -1) {
                p1 = i;
            }
            else {
                p2 = i;
            }
        }
    }

    int p3 = 3 - p1 - p2;
    if (w[p1] + w[p2] >= W) {
        cout << 2 * (W - w[p3] + 1) * (H - h[p3] + 1) % mod << endl;
    }
    else {
        cout << 0 << endl;
    }
    return;
}

4. 。剩下两个不满足的如果不能把填满，答案是0；或者不能把填满的，答案为0。否则上下互换，左右互换，。

for (int i = 0; i < 3; i++) {
    if (h[i] == H) {
        ll mn = inf, s = 0;
        for (int j = 0; j < 3; j++) {
            if (j == i) continue;
            s += h[j];
            mn = min(mn, w[j]);
        }

        if (s >= H && mn + w[i] >= W) {
            cout << 4 << endl;
            return;
        }
    }
}

5. 。只能占三个角。答案是0。
   时间复杂度。（带点常数，问题不大
   最后贴个总代码

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define X first
#define Y second
#define umap unordered_map
using ll = long long;
using ull = unsigned long long;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int maxn = 2e5 + 5, mod = 1e9 + 7, maxp = 31, inf = 1e9;
const ll INF = 1e18;
const double eps = 1e-6;

void solve() {
    ll H, W;
    cin >> H >> W;
    vector<ll> w(3), h(3);
    for (int i = 0; i < 3; i++) {
        cin >> h[i] >> w[i];
    }

    for (int i = 0; i < 3; i++) {
        if (h[i] == H && w[i] == W) {
            ll ans = 1;
            for (int j = 0; j < 3; j++) {
                ans = ans * (H - h[j] + 1) % mod * (W - w[j] + 1) % mod;
            }
            cout << ans << endl;
            return;
        }
    }

    int cnt = 0;
    for (int i = 0; i < 3; i++) {
        if (h[i] == H) {
            cnt++;
        }
    }


    if (cnt == 3) {
        ll s = 0;
        for (int i = 0; i < 3; i++) {
            s += w[i];
        }
        if (s < W) {
            cout << 0 << endl;
            return;
        }

        vector<int> p(3);
        iota(p.begin(), p.end(), 0);
        ll ans = 0;
        do {
            if (w[p[0]] + w[p[2]] < W) {
                ll mn = max(1ll, W - w[p[2]] - w[p[1]]);
                ll mx = min(W - w[p[1]] - 1, w[p[0]]);
                ans += mx - mn + 1;
                ans %= mod;
            }
            else {
                ans += max(0ll, W - w[p[1]] - 1);
                ans %= mod;
            }
        } while (next_permutation(p.begin(), p.end()));

        for (int i = 0; i < 3; i++) {
            for (int j = i + 1; j < 3; j++) {
                int k = 3 - i - j;
                if (max(w[i], w[j]) + w[k] >= W) {
                    ans += 2;
                }
            }
        }
        cout << ans % mod << endl;
        return;
    }

    if (cnt == 2) {
        int p1 = -1, p2 = -1;
        for (int i = 0; i < 3; i++) {
            if (h[i] == H) {
                if (p1 == -1) {
                    p1 = i;
                }
                else {
                    p2 = i;
                }
            }
        }

        int p3 = 3 - p1 - p2;
        if (w[p1] + w[p2] >= W) {
            cout << 2 * (W - w[p3] + 1) * (H - h[p3] + 1) % mod << endl;
        }
        else {
            cout << 0 << endl;
        }
        return;
    }

    swap(H, W);
    swap(h, w);

    cnt = 0;
    for (int i = 0; i < 3; i++) {
        if (h[i] == H) {
            cnt++;
        }
    }

    cnt = 0;
    for (int i = 0; i < 3; i++) {
        if (h[i] == H) {
            cnt++;
        }
    }


    if (cnt == 3) {
        ll s = 0;
        for (int i = 0; i < 3; i++) {
            s += w[i];
        }
        if (s < W) {
            cout << 0 << endl;
            return;
        }

        vector<int> p(3);
        iota(p.begin(), p.end(), 0);
        ll ans = 0;
        do {
            if (w[p[0]] + w[p[2]] < W) {
                ll mn = max(1ll, W - w[p[2]] - w[p[1]]);
                ll mx = min(W - w[p[1]] - 1, w[p[0]]);
                ans += mx - mn + 1;
                ans %= mod;
            }
            else {
                ans += max(0ll, W - w[p[1]] - 1);
                ans %= mod;
            }
        } while (next_permutation(p.begin(), p.end()));

        for (int i = 0; i < 3; i++) {
            for (int j = i + 1; j < 3; j++) {
                int k = 3 - i - j;
                if (max(w[i], w[j]) + w[k] >= W) {
                    ans += 2;
                }
            }
        }
        cout << ans % mod << endl;
        return;
    }

    if (cnt == 2) {
        int p1 = -1, p2 = -1;
        for (int i = 0; i < 3; i++) {
            if (h[i] == H) {
                if (p1 == -1) {
                    p1 = i;
                }
                else {
                    p2 = i;
                }
            }
        }

        int p3 = 3 - p1 - p2;
        if (w[p1] + w[p2] >= W) {
            cout << 2 * (W - w[p3] + 1) * (H - h[p3] + 1) % mod << endl;
        }
        else {
            cout << 0 << endl;
        }
        return;
    }

    swap(H, W);
    swap(h, w);

    for (int i = 0; i < 3; i++) {
        if (h[i] == H) {
            ll mn = inf, s = 0;
            for (int j = 0; j < 3; j++) {
                if (j == i) continue;
                s += h[j];
                mn = min(mn, w[j]);
            }

            if (s >= H && mn + w[i] >= W) {
                cout << 4 << endl;
                return;
            }
        }
    }

    swap(H, W);
    swap(h, w);

    for (int i = 0; i < 3; i++) {
        if (h[i] == H) {
            ll mn = inf, s = 0;
            for (int j = 0; j < 3; j++) {
                if (j == i) continue;
                s += h[j];
                mn = min(mn, w[j]);
            }

            if (s >= H && mn + w[i] >= W) {
                cout << 4 << endl;
                return;
            }
        }
    }

    cout << 0 << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int tt = 1;
    cin >> tt;
    while (tt--) solve();
    return 0;
}

B. Turning Permutation

题意：

令为出现的位置。定义转折序列是指一个排列，对于每个 都有 给你 和 ，求长度为的第大的排列。如果不存在则输出。
### input

3 2

output

2 1 3

数据范围

分析

我们发现转折序列和第 大这两个点是对不上的。转折序列是对于而言的，而 是对原排序而言的。我们应该把这两点并到一起。
在做这些之前，我们分析一下题目本身的性质。
- 给你一个长度为 的排列，能组合出多少种情况？我们考虑递推。表示第一、二个为增大的个数，则是递减。怎么递推？我们考虑放在哪个位置。既然放完了，剩下的数字都是比大的。因此递增递减的顺序就确定了。直接递推即可。结束后发现开始位置递增递减两种的排列个数是相同的。因此直接将定义为长度为 的转折序列的个数。

dp[0] = dp[1] = 2;
for (int i = 2; i <= 23; i++) {
    ll x = 0;
    for (int p = 1; p <= i; p++) {
        int l = p - 1, r = i - p;
        x += C(i - 1, l) * dp[l] / 2 * dp[r] / 2;
    }
    dp[i] = x;
}

发现已经是 的极限了。因此如果，可以直接判断是否有解；否则肯定有解。

接下来把 “转折序列” 和 “第大” 的性质结合。
我们考虑把第 大放到 上去，因为主要的性质在转折序列上。原数组的大小，在 上是怎么体现的？在原数组上，大小是由第一个放谁决定的。转到数组上，那就是 放在哪里决定的。显然，在原数组中，越靠后的位置贡献越小。因此在 数组中， 越大的数字贡献越少。

这下思路就清晰了。我们从小到大枚举每个数放在哪个位置。注意除了 以外，放其他数是有不合法的位置的。比如，我们知道奇数位置上比下一个数小，偶数位置上比下一个数大。一旦 放在第 个，因为后面放的数一定比 大，因此是不满足的。所以这么分析， 和 就一定放在奇数位置上了吗？下面看，就是合法的。因此应当进一步细化。

接下来，如果我们已经确定的一些位置，那么会产生多少种情况呢？我们对于每个区间考虑。找到两个相邻

G. Function Query

题意

给你一个数组 和 次询问(, )，每次询问给你两个数和，定义，找出下标 满足，不存在则输出。

input

5 6
3 5 1 2 4
0 2
1 1
2 3
3 2
4 2
5 8

output

2
3
2
1
4
-1

我们发现对于给定的 和 ， 只有大于0、小于0和等于0三种情况。而一旦 ，就只要选择 即可。因此下面讨论另外两种情况。

我们发现如果不存在 满足$ f(x) < 0x$都满足 ，显然答案是。 同理。反之，若两者都存在，那么我们肯定能找到一个分界点（因为只有 只有两种情况），使得 。现在的问题转换成我们怎么找到这个下标。

下标肯定不是盲目去找的，要想到找到某些具有特殊性质的下标。由于异或并不满足单调性，那么我们的特殊性质就很少了。我们应该想到需要找下标最小的点（最大也可以，下面以最小为例子），这样如果找到了满足 最小下标 ，肯定有 。但是又有新问题出现了：如果该怎么处理呢？因为只有大于或者小于两种情况，因此我们既找满足 的最小下标，也找 的最小下标，若答案存在， 和 之间必定有一个是，一个非。我们取大的那个输出即可。

那么我们怎么去找呢？看到二进制，我们可以想到逐位比较。用字典树记录 ，并且每个位置都记录最小的那个下标（即如果 与 具有部分相同的二进制前缀，那么该他们在字典树上有重合的位置。这些重合的位置上我只记录小的那个下标）。给定了 和 ，我们怎么找 呢？我们以找 为例，从高到低找到了第 位。我们要知道如果比到了第 位，那么前面的每个位置肯定都满足。 如果 这一位是，那么 这一位不得不是 。反之如果 的这一位是，那么如果存在 使得 这一位是 ，我们就取，然后让的这一位与 的这一位相同，继续往后找。

code

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define X first
#define Y second
#define umap unordered_map
using ll = long long;
using ull = unsigned long long;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int maxn = 2e5 + 5, mod = 1e9 + 7, maxp = 31, inf = 1e9;
const ll INF = 1e18;
const double eps = 1e-6;

struct Trie {
    vector<vector<int>> ch;
    vector<int> z;

    Trie(int n) {
        ch.resize((n + 1) << 4);
        z.resize((n + 1) << 4);
        for (int i = 0; i < ((n + 1) << 4); i++) {
            ch[i].resize(2);
        }
    }

    int idx = 0;

    void insert(int x, int id) {
        int p = 0;
        for (int j = 31; j >= 0; j--) {
            int k = x >> j & 1;
            if (!ch[p][k]) {
                ch[p][k] = ++idx;
                z[idx] = id;
            }
            p = ch[p][k];
        }
    }

    int querym(int a, int b) {
        int ans = -1;
        int p = 0;
        for (int j = 31; j >= 0; j--) {
            bool f = false, g = false;
            if (a >> j & 1) {
                f = true;
            }
            if (b >> j & 1) {
                g = true;
            }

            if (f && g) {
                if (ch[p][1]) {
                    int res = z[ch[p][1]];
                    if (ans == -1) {
                        ans = res;
                    }
                    else {
                        ans = min(ans, res);
                    }
                }
                if (!ch[p][0]) {
                    return ans;
                }
                p = ch[p][0];
            }

            if (f && !g) {
                if (!ch[p][1]) {
                    return ans;
                }
                p = ch[p][1];
            }

            if (!f && g) {
                if (ch[p][0]) {
                    int res = z[ch[p][0]];
                    if (ans == -1) {
                        ans = res;
                    }
                    else {
                        ans = min(ans, res);
                    }
                }
                if (!ch[p][1]) {
                    return ans;
                }
                p = ch[p][1];
            }

            if (!f && !g) {
                if (!ch[p][0]) {
                    return ans;
                }
                p = ch[p][0];
            }
        }

        return ans;
    }

    int queryb(int a, int b) {
        int ans = -1;
        int p = 0;
        for (int j = 31; j >= 0; j--) {
            bool f = false, g = false;
            if (a >> j & 1) {
                f = true;
            }
            if (b >> j & 1) {
                g = true;
            }

            if (f && g) {
                if (!ch[p][0]) {
                    return ans;
                }
                p = ch[p][0];
            }

            if (f && !g) {
                if (ch[p][0]) {
                    int res = z[ch[p][0]];
                    if (ans == -1) {
                        ans = res;
                    }
                    else {
                        ans = min(ans, res);
                    }
                }
                if (!ch[p][1]) {
                    return ans;
                }
                p = ch[p][1];
            }

            if (!f && g) {
                if (!ch[p][1]) {
                    return ans;
                }
                p = ch[p][1];
            }

            if (!f && !g) {
                if (ch[p][1]) {
                    int res = z[ch[p][1]];
                    if (ans == -1) {
                        ans = res;
                    }
                    else {
                        ans = min(ans, res);
                    }
                }
                if (!ch[p][0]) {
                    return ans;
                }
                p = ch[p][0];
            }

        }

        return ans;
    }
};

void solve() {
    int n, q;
    cin >> n >> q;

    Trie tree(n + 1);
    map<int, int> mp;

    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        tree.insert(x, i);
        mp[x] = min(i, n - 1);
    }


    while (q--) {
        int a, b;
        cin >> a >> b;
        if (mp.contains(a ^ b)) {
            cout << mp[a ^ b] << endl;
            continue;
        }
        int ans = max(tree.queryb(a, b), tree.querym(a, b));
        if (ans <= 1) {
            ans = -1;
        }
        else {
            ans--;
        }

        cout << ans << endl;
    }

}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int tt = 1;
    // cin >> tt;
    while (tt--) solve();
    return 0;
}

A. Reverse Pairs Coloring

题意

给你一个长度为 () 的排列，以及一个的方格，对于所有满足 以及 的下标，给方格第 行第 列的方格染色， 求染色的联通块的个数。

input

9
5 9 1 8 2 6 4 7 3

output

5

可以对小数据画图分析。 比如题目所给样例，最后的方格是这样的：

xxxx.....
xxxx.xxx.
.........
.xxx.xx..
.........
..xx.....
..x......
..x......
.........

我们发现以下性质：
1. 对于第 行，染色个数不超过。因为需要找逆序对，而对于所有逆序对，都有。
2. 对于每个，它肯定不会作用到满足的下标 。因为逆序对是对于 的下标 ，而对于列的染色是 列。既然 在前面出现过了，就不会在后面形成逆序对。

于是我们可以模拟以下过程：
1. 对于每一个 ，先对这一行的前 个格子染色。
2. 对于每一个 ，将满足 的下标 中的第 列中染色的方块划去。

这样我们就模拟完了这个过程。但是目前还有一点问题，那就是怎么去记录每一行的染色情况呢？我们可以转换一下过程：只有一行。首先所有方格都染色。遍历到第 行时，对第 个删除。然后取前 个，就是目前的状态。
所以现在我们只需要维护一个数组了。由于是取前 个，我们可以考虑保存中数组连续位置左端点的位置。删除了第 个，如果是左端点，就将其删去；如果 被染色，那么第 个将成为新的左端点。注意到当 时是不会产生新的联通块的，因为此时 是 的前缀。当 ，只需要查找区间 的左端点个数就是新的联通块的个数。可以用树状数组保存左端点。时间复杂度。

code

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define X first
#define Y second
#define umap unordered_map
using ll = long long;
using ull = unsigned long long;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int maxn = 2e5 + 5, mod = 1e9 + 7, maxp = 31, inf = 1e9;
const ll INF = 1e18;
const double eps = 1e-6;

template<class T>
struct BIT {
    vector<T> c;
    int ub;
    BIT() {}
    BIT(int ub_) {
        ub = ub_;
        init();
    }

    void init() {
        c.resize(ub + 1);
        c.assign(ub + 1, 0);
    }

    int lowbit(int x) {
        return x & -x;
    }

    void add(int pos, T val) {
        if (pos <= 0) return;
        while (pos <= ub) {
            c[pos] += val;
            pos += lowbit(pos);
        }
    }

    T query(int pos) {
        if (pos <= 0) return 0;
        T res = 0;
        while (pos) {
            res += c[pos];
            pos -= lowbit(pos);
        }
        return res;
    }

    T query(int l, int r) {
        return query(r) - query(l - 1); 
    }
};

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    vector<bool> vis(n + 2, true);
    vis[0] = vis[n + 1] = false;

    BIT<int> c(n);

    c.add(1, 1);

    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        int x = a[i];
        vis[x] = false;
        if (c.query(x, x)) {
            c.add(x, -1);
        }
        if (vis[x + 1]) {
            c.add(x + 1, 1);
        }
        if (a[i] < a[i - 1]) continue;
        ans += c.query(a[i - 1], a[i]);
    }


    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int tt = 1;
    // cin >> tt;
    while (tt--) solve();
    return 0;
}

矩阵快速幂-HDU-07-1008 循环图

题意

坎格鲁斯普雷被困在了一张循环图里，这张循环图有无数个节点，初始时坎格鲁斯普雷在 号节点。

循环图是边存在着一定循环关系的图，循环图里面的边可以用循环周期 和 对三元组 表示。每对三元组 表示，对于循环图内所有的满足 的点对 ，都存在有 ​ 条从点 通往点 的边。

现在，坎格鲁斯普雷知道了这张循环图的第 个节点到第 个节点各存在着一个出口，坎格鲁斯普雷需要到达这些节点中的任意一个才能逃出循环图（到达有出口存在的节点后不一定要立刻逃出）。坎格鲁斯普雷想请你帮他算算，他有多少种逃出这张循环图的方式。由于答案可能很大，你需要输出答案对 取模后的结果。

朴素思路

首先可以想到朴素 ，表示从走到有种方案，转移可以 = 。但是这样显然会超时。

矩阵快速幂思路

由于、很大，很小，而又存在非常显然的递推关系，即，十分符合矩阵的乘法，可以想到矩阵快速幂。
现在就是要考虑矩阵需要记录什么。由于需要求区间，可以转化成前缀和的差，所以矩阵需要记录前缀。而前面提到的递推关系也很自然的想到用矩阵表示从走到的方案数。

然后就是怎么递推了。我们发现 ，的范围很好，但是会到的范围，我们不妨先用矩阵记录的方案数，再用矩阵记录从 一步走到的方案数，这样利用矩阵乘法就可以算出从 走到的总方案数（总方案数意思是可以有中转，比如1->2->10）。
再考虑前缀和。这肯定是要再开一维的。考虑到要利用到矩阵快速幂，我们发现两个极好的性质：
1. 由题意，这样的点对之间有边，所以既可以表示以为起点，走到的方案数，又可以表示从开始，走到的方案数。你会发现就是从开始，走到的方案数！
2. 由于前缀和要和方案数存在同一个矩阵里面，那么如果前缀和与方案数在同一个维度（意思是说，矩阵表示从走到，前缀和也表示走到的方案数，这两个都是(k + 1)维度的），那么递推肯定是不好推的，因为我现在还没有求得下一维度的方案数，我根本就没法得到下一个维度的前缀和。说到这里就很有感触了，那就是把前缀和降一个维度！这样一个矩阵里面存的是这个维度的方案数和上一个维度的前缀和，而上一维度的前缀和+这一维度的方案是就是这一维度的前缀和，也就是下一矩阵中的前缀和！

注意矩阵的初始化就AC了（

code

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;
const int mod = 1e9 + 7;

struct matrix {
    vector<vector<ll>> t;
    int n, m;

    matrix(int _n, int _m) {
        n = _n, m = _m;
        t.resize(n + 1);
        for (int i = 1; i <= n; i++) {
            t[i].resize(m + 1);
        }
    }

    matrix operator *(const matrix &a) const {
        matrix res(n, a.m);
        for (int i = 1; i <= res.n; i++) {
            for (int j = 1; j <= res.m; j++) {
                for (int k = 1; k <= m; k++) {
                    res.t[i][j] += t[i][k] * a.t[k][j];
                    res.t[i][j] %= mod;
                }
            }
        }
        return res;
    }

    matrix m_qpow(ll k) {
        matrix res(n, n);
        auto A = *this;
        for (int i = 1; i <= n; i++) {
            res.t[i][i] = 1;
        }
        while (k) {
            if (k & 1) {
                res = res * A;
            }
            A = A * A;
            k >>= 1;
        }
        return res;
    }
};

void solve() {
    int n, m;
    ll L, R;
    cin >> n >> m >> L >> R;
    vector<vector<ll>> ed(n + 1, vector<ll>(n + 1)), W(n + 1, vector<ll>(n + 1)), dp(n + 1, vector<ll>(n + 1));
    vector<bool> vis(n + 1);
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        if (v <= n) {
            ed[u][v] = w;
        }
        else {
            W[u][v - n] = w;
        }
        // 分别记录，这样好处理出D和Q矩阵
    }

    auto dfs = [&](auto self, int u) -> void {
        if (vis[u]) return;
        vis[u] = true;
        dp[u][u] = 1;
        for (int v = u + 1; v <= n; v++) {
            for (int k = u + 1; k <= v; k++) {
                self(self, k);
                dp[u][v] = (dp[u][v] + 1ll * ed[u][k] * dp[k][v] % mod) % mod;
            } 
        }
    };

    for (int i = 1; i <= n; i++) {
        dfs(dfs, i);
        // 预处理D矩阵
    }

    auto get = [&](ll x) -> ll {
        ll k = x / n;
        // 这里要注意因为矩阵是n个一推的，所以要留下x % n个直接加
        matrix D(n + 1, n + 1);
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                D.t[i][j] = dp[i][j];
            }
        }

        D.t[n + 1][n + 1] = 1;

        matrix Q(n + 1, n + 1);
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                Q.t[i][j] = W[i][j];
            }
        }
        for (int i = 1; i <= n + 1; i++) {
            Q.t[i][n + 1] = 1;
            // 给第n + 1维赋值，好直接处理出A的前缀和列（第n + 1列）
        }

        auto A = D * Q;
        auto res = A.m_qpow(k);
        ll ans = res.t[1][n + 1];
        res = res * D;
        // *A实际上是*D*Q，即先自己内部计算然后再递推到下一个，这里算剩下的不需要递推到下一个，所以只要*D即可
        for (int i = 1; i <= x % n; i++) {
            ans = (ans + res.t[1][i]) % mod;
        }
        return ans;
    };

    ll ans = get(R) - get(L - 1);
    // 前缀和相减得到区间和
    ans = (ans + mod) % mod;
    cout << ans << endl;
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int tt = 1;
    cin >> tt;
    while (tt--) solve();
    return 0;
}

DSU on tree（树上启发式合并）

适用范围/算法特点

• 树上启发式合并是一种处理树上不带修改的离线子树问题的算法
• 时间复杂度为

前置知识

• 无

问题引入

先来看cf上的一道不算模版的题：1709-E XOR Tree - Codeforces
给定有 () 个节点的树，每个节点有一个数字 () 。一条简单路径的权重定义为路径上所有点的异或值。如果没有简单路径的权重为，则这棵树称为好的。
你可以进行任意次操作，每次操作修改一个节点的值为任意值。求为了使这棵树变成“好的”，最少需要的操作次数。
输入
第一行一个数，表示节点个数
第二行n个整数, , ..., ()---节点的数字。
接下来行，每行两个数、，表示一条连接点、的边。

input
6
3 2 1 3 2 1
4 5
3 4
1 4
2 1
6 1
output
2

Solution

• 对于路径权值的问题，让我们取1为根节点。首先可以求出从到的路径权重。假设一条路径上的两个端点为和，而他们的最近公共祖先为，那么这条路径的权值等于就等价于 ^ ^ == 。整理得 ^ == 。从而处理成子树的问题。
• 对于修改操作，我们可以将这个节点的值改为一个很大的值，从而使这个数的某一位二进制只有它为1（因为修改的值没有上限），这样经过这个点的路径权值都不为了。

我们发现如果一棵树去暴力处理它的所有子树，时间复杂度为。DSU on tree优秀的地方就在于此。我们每个节点开一个set，将一个节点的所有信息都insert到这个节点。我们发现这个时候交换两个节点的set是不会影响的，因此我们可以让该节点的set成为较大的那个set。可以证明，这样的时间复杂度为。而对于一旦发现需要修改，直接clear即可。

Code

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;

void solve() {
    int n;
    cin >> n;
    vector<int> c(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> c[i];
    }
    vector<vector<int>> E(n + 1, vector<int>());
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        E[u].push_back(v);
        E[v].push_back(u);
    }
    vector<int> d(n + 1);
    
    // dfs0处理出d[u]
    function<void(int u, int fa)> dfs0 = [&](int u, int fa) {
        d[u] = d[fa] ^ c[u];
        for (auto v : E[u]) {
            if (v == fa) continue;
            dfs0(v, u);
        }
    };
    
    set<int> s[n + 1];
    int ans = 0;
    
    // 这里u是正在遍历的节点, v是其子节点, fa是其父节点
    function<void(int, int)> dfs = [&](int u, int fa) {
        s[u].insert(d[u]);
        bool f = 0; // f打标记, 若需要清空就置1
        for (auto v : E[u]) {
            if (v == fa) continue;
            dfs(v, u);

            // 最关键的一步, 可以发现后面的两次都是遍历s[v]的, 因此我们把小的set给v
            if (s[u].size() < s[v].size()) {
                swap(s[u], s[v]);
            }

            for (auto x : s[v]) {
                if (s[u].count(x ^ c[u])) f = 1;
            }
            for (auto x : s[v]) {
                s[u].insert(x);
            }
        }
        
        // 注意细节, 这里是全部遍历再清空set
        if (f) {
            s[u].clear();
            ans++;
        }
    };
    dfs0(1, 0);
    dfs(1, -1);
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int tt = 1;
    // cin >> tt;
    while (tt--) solve();
    return 0;
}

ok成功AC

正式介绍

其实上面的例子不算是DSU on tree算法的例子，但它却处处存在着该算法的影子。可以发现，这是一种“优美的暴力”。我们暴力处理每个节点的子节点，但是时间复杂度却来到了。这是由于我们都只处理了size较小的set。相对于上题的代码，DSU on tree给出了三点扩展:
1. 我们不必给每一个节点开一个状态（即set）；（1）
2. 每个点的暴搜过程可以直接用dfs遍历一遍；（2）
3. 交换set大小的操作改为先遍历重儿子，再遍历轻儿子。（3）
（重儿子是指该节点size最大的儿子，其他都为轻儿子）

下面先给出一道真正的模板题，以上的特点会一一解释。

600-E Lomsat gelral - Codeforces
给定有 () 个节点的有根树，根节点为。每个节点有一个颜色。对于每个节点，求出他的子树中数量最多的颜色。如果有多种数量最多的颜色，求出他们的总和。
输入
第一行一个数，表示节点个数
第二行n个整数, , ..., ()---节点的数字。
接下来行，每行两个数、，表示一条连接点、的边。
输出
个数，第个数表示以为根的子树中数量最多的颜色的总和。

input
4
1 2 3 4
1 2
2 3
2 4
output
10 9 3 4

下面的思路参考了【AgOHの算法胡扯】树上启发式合并（dsu on tree）_哔哩哔哩_bilibili

算法流程
对于节点：
* 处理好所有轻儿子及其子树的贡献，算出来后删除轻儿子的贡献也就是说先遍历轻儿子；
* 处理好重儿子及其子树的贡献，算完后不删除贡献对应；
* 暴力统计所有轻儿子及其子树的贡献，就是此时节点的答案对应。

对于，我们可以开一个总的数组，这样在遍历完节点的时候这个数组就是它的答案。这就是为什么我们在遍历完轻儿子的时候要删除掉它的贡献，因为它的贡献会影响到其他子树。
对于，重儿子是后遍历的，因此它可以保存下来。而它的size又是最大的，这样时间复杂度最优。
其实思路和上题XOR Tree非常相似。

具体细节可以看code

Code

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;

void solve() {
    int n;
    cin >> n;
    vector<int> col(n + 1);
    vector<ll> ans(n + 1);
    vector<vector<int>> E(n + 1, vector<int>());
    for (int i = 1; i <= n; i++) {
        cin >> col[i];
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        E[u].push_back(v);
        E[v].push_back(u);
    }

    vector<int> sz(n + 1), son(n + 1);

    // dfs0处理出所有重儿子和轻儿子
    function<void(int, int)> dfs0 = [&](int u, int fa) {
        sz[u] = 1;
        for (auto v : E[u]) {
            if (v == fa) continue;
            dfs0(v, u);
            sz[u] += sz[v];
            if (sz[v] > sz[son[u]]) {
                son[u] = v;
            }
        }
    };

    // 这里cnt记录了每个颜色的个数, 将数组开在外面
    vector<int> cnt(n + 1);
    ll sum = 0, maxc = 0;
    // flag的作用后面会提到
    int flag = 0;

    // 下面的update函数是暴搜的过程, val分别取1和-1, 代表加贡献/删贡献
    function<void(int, int, int)> update = [&](int u, int fa, int val) {
        // 以下八行计算贡献, 不同的题目需求不同
        cnt[col[u]] += val;
        if (cnt[col[u]] > maxc) {
            maxc = cnt[col[u]];
            sum = col[u];
        }
        else if (cnt[col[u]] == maxc) {
            sum += col[u];
        }

        // 这里为什么不写v == son[u]呢？因为只有一个重儿子son[u]不需要遍历, 那就是最开始那个u
        // 所以开一个flag, flag就是最开始的flag, 不理解的可以看下面函数的调用时机
        for (auto v : E[u]) {
            if (v == fa || v == flag) continue;
            update(v, u, val);
        }
    };

    // 第三个参数keep表示是否需要清空
    function<void(int, int, bool)> dfs = [&](int u, int fa, bool keep) {
        for (auto v : E[u]) {
            if (v == fa || v == son[u]) continue;
            // 轻儿子需要清空, keep为false
            dfs(v, u, false);
        }
        if (son[u]) {
            // 重儿子不需要清空, keep为true
            dfs(son[u], u, true);
            flag = son[u];
        }

        // 可以看到在这里只需要统计轻儿子就可以, 只有当前u的重儿子不需要遍历, 而轻儿子可能有与他自己的重儿子, 还是需要遍历的, 因此需要开一个flag
        update(u, fa, 1);
        flag = 0;

        // 此时所有儿子都已经遍历完一遍, 当前的cnt数组就是该节点的子树的所有状态
        ans[u] = sum;
        if (!keep) {
            update(u, fa, -1);
            maxc = sum = 0;
        }
    };
    dfs0(1, -1);
    dfs(1, -1, 0);
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << " ";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int tt = 1;
    // cin >> tt;
    while (tt--) solve();
    return 0;
}

DSU on tree题单：洛谷 | DSU on tree