XCPC Notes

Appearance

发布时间：2024-08-27

第一场 ​

A ​

题意：
求有多少长为 n 的元素是 [0,2m)[0,2^m) 的整数序列

满足存在一个非空子序列的 AND 和是1

思路：

  • 二进制下第一位为1的所有数的AND一定为1
  • 枚举这样的数k，则对于二进制下第一位为0的数，其他位可以任选，有 2m−12^{m-1} 种方案，有 n−kn-k 个数，因此方案为 2(m−1)(n−k)2^{(m-1)(n-k)}
  • 对于二进制下第一位为1的数，考虑剩余的m-1位，每一位AND为0，有 2k−12^k-1 种选法，一共 (2k−1)m−1(2^k-1)^{m-1} 种
  • 总方案为 Cnk2(m−1)(n−k)(2k−1)m−1C_n^k2^{(m-1)(n-k)}(2^k-1)^{m-1} 种
cpp
int C[N][N];
int n,m,q;
int qpow(int a,int b){
    int ans=1;
    for(;b;b>>=1){
        if(b&1)ans=ans*a%q;
        a=a*a%q;
    }
    return ans;
}
void solve(){
    cin>>n>>m>>q;
    C[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)C[i][j]=(C[i-1][j]+C[i-1][j-1])%q;
        C[i][0]=1;
    }
    int ans=0;
    for(int k=1;k<=n;k++){
        ans+=C[n][k]%q*qpow(2,(m-1)*(n-k))%q*qpow((qpow(2,k)-1)%q,m-1)%q;
        ans%=q;
    }
    cout<<ans<<"\n";
}

B ​

题意：

A的基础上，询问存在至少两个这样的子序列的方案数

思路：

  • A的答案-只有一个子序列的方案
  • 考虑只有一个子序列的情况，对于当前子序列，去除任意一个数，都会影响结果
  • 对于每一位来讲，总有一个数，这个数的当前位为0，其他数的当前位为1，这些位称为特殊位
  • dpi,jdp_{i,j} 表示考虑了 ii 个数，有 jj 个特殊位的情况
  • 对于当前提供的特殊位，去掉该特殊位，可能仍然包含i行，也可能变成i-1行
  • 特殊位一共有i个位置可选，dpi,j=i⋅(dpi,j−1+dpi−1,j−1)dp_{i,j}=i \cdot (dp_{i,j-1}+dp_{i-1,j-1})
  • 仍然枚举二进制第一位为1的个数 kk ，枚举特殊位 tt ，k≤t≤m−1k \leq t \leq m-1，从 m−1m-1 位选 tt 位，方案为 Cm−1tdpk,tC_{m-1}^tdp_{k,t}，剩余 m−t−1m-t-1 位，每一位的选法为 2k−k−12^k-k-1(总方案-存在特殊位的方案(只有一个0其余为1)-全1)
  • 总方案：Cnk⋅2(n−k)(m−1)⋅Cm−1t⋅dpk,t⋅(2k−k−1)m−t−1C_n^k \cdot 2^{(n-k)(m-1)} \cdot C_{m-1}^t \cdot dp_{k,t} \cdot (2^k-k-1)^{m-t-1}
cpp
#include<bits/stdc++.h>
namespace atcoder {

namespace internal {

// @param m `1 <= m`
// @return x mod m
constexpr long long safe_mod(long long x, long long m) {
    x %= m;
    if (x < 0) x += m;
    return x;
}

// Fast modular multiplication by barrett reduction
// Reference: https://en.wikipedia.org/wiki/Barrett_reduction
// NOTE: reconsider after Ice Lake
struct barrett {
    unsigned int _m;
    unsigned long long im;

    // @param m `1 <= m < 2^31`
    barrett(unsigned int m) : _m(m), im((unsigned long long)(-1) / m + 1) {}

    // @return m
    unsigned int umod() const { return _m; }

    // @param a `0 <= a < m`
    // @param b `0 <= b < m`
    // @return `a * b % m`
    unsigned int mul(unsigned int a, unsigned int b) const {
        // [1] m = 1
        // a = b = im = 0, so okay

        // [2] m >= 2
        // im = ceil(2^64 / m)
        // -> im * m = 2^64 + r (0 <= r < m)
        // let z = a*b = c*m + d (0 <= c, d < m)
        // a*b * im = (c*m + d) * im = c*(im*m) + d*im = c*2^64 + c*r + d*im
        // c*r + d*im < m * m + m * im < m * m + 2^64 + m <= 2^64 + m * (m + 1) < 2^64 * 2
        // ((ab * im) >> 64) == c or c + 1
        unsigned long long z = a;
        z *= b;
#ifdef _MSC_VER
        unsigned long long x;
        _umul128(z, im, &x);
#else
        unsigned long long x =
            (unsigned long long)(((unsigned __int128)(z)*im) >> 64);
#endif
        unsigned int v = (unsigned int)(z - x * _m);
        if (_m <= v) v += _m;
        return v;
    }
};

// @param n `0 <= n`
// @param m `1 <= m`
// @return `(x ** n) % m`
constexpr long long pow_mod_constexpr(long long x, long long n, int m) {
    if (m == 1) return 0;
    unsigned int _m = (unsigned int)(m);
    unsigned long long r = 1;
    unsigned long long y = safe_mod(x, m);
    while (n) {
        if (n & 1) r = (r * y) % _m;
        y = (y * y) % _m;
        n >>= 1;
    }
    return r;
}

// Reference:
// M. Forisek and J. Jancina,
// Fast Primality Testing for Integers That Fit into a Machine Word
// @param n `0 <= n`
constexpr bool is_prime_constexpr(int n) {
    if (n <= 1) return false;
    if (n == 2 || n == 7 || n == 61) return true;
    if (n % 2 == 0) return false;
    long long d = n - 1;
    while (d % 2 == 0) d /= 2;
    constexpr long long bases[3] = {2, 7, 61};
    for (long long a : bases) {
        long long t = d;
        long long y = pow_mod_constexpr(a, t, n);
        while (t != n - 1 && y != 1 && y != n - 1) {
            y = y * y % n;
            t <<= 1;
        }
        if (y != n - 1 && t % 2 == 0) {
            return false;
        }
    }
    return true;
}
template <int n> constexpr bool is_prime = is_prime_constexpr(n);

// @param b `1 <= b`
// @return pair(g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/g
constexpr std::pair<long long, long long> inv_gcd(long long a, long long b) {
    a = safe_mod(a, b);
    if (a == 0) return {b, 0};

    // Contracts:
    // [1] s - m0 * a = 0 (mod b)
    // [2] t - m1 * a = 0 (mod b)
    // [3] s * |m1| + t * |m0| <= b
    long long s = b, t = a;
    long long m0 = 0, m1 = 1;

    while (t) {
        long long u = s / t;
        s -= t * u;
        m0 -= m1 * u;  // |m1 * u| <= |m1| * s <= b

        // [3]:
        // (s - t * u) * |m1| + t * |m0 - m1 * u|
        // <= s * |m1| - t * u * |m1| + t * (|m0| + |m1| * u)
        // = s * |m1| + t * |m0| <= b

        auto tmp = s;
        s = t;
        t = tmp;
        tmp = m0;
        m0 = m1;
        m1 = tmp;
    }
    // by [3]: |m0| <= b/g
    // by g != b: |m0| < b/g
    if (m0 < 0) m0 += b / s;
    return {s, m0};
}

// Compile time primitive root
// @param m must be prime
// @return primitive root (and minimum in now)
constexpr int primitive_root_constexpr(int m) {
    if (m == 2) return 1;
    if (m == 167772161) return 3;
    if (m == 469762049) return 3;
    if (m == 754974721) return 11;
    if (m == 998244353) return 3;
    int divs[20] = {};
    divs[0] = 2;
    int cnt = 1;
    int x = (m - 1) / 2;
    while (x % 2 == 0) x /= 2;
    for (int i = 3; (long long)(i)*i <= x; i += 2) {
        if (x % i == 0) {
            divs[cnt++] = i;
            while (x % i == 0) {
                x /= i;
            }
        }
    }
    if (x > 1) {
        divs[cnt++] = x;
    }
    for (int g = 2;; g++) {
        bool ok = true;
        for (int i = 0; i < cnt; i++) {
            if (pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1) {
                ok = false;
                break;
            }
        }
        if (ok) return g;
    }
}
template <int m> constexpr int primitive_root = primitive_root_constexpr(m);

}  // namespace internal

}  // namespace atcoder


#include <cassert>
#include <numeric>
#include <type_traits>

namespace atcoder {

namespace internal {

#ifndef _MSC_VER
template <class T>
using is_signed_int128 =
    typename std::conditional<std::is_same<T, __int128_t>::value ||
                                  std::is_same<T, __int128>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using is_unsigned_int128 =
    typename std::conditional<std::is_same<T, __uint128_t>::value ||
                                  std::is_same<T, unsigned __int128>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using make_unsigned_int128 =
    typename std::conditional<std::is_same<T, __int128_t>::value,
                              __uint128_t,
                              unsigned __int128>;

template <class T>
using is_integral = typename std::conditional<std::is_integral<T>::value ||
                                                  is_signed_int128<T>::value ||
                                                  is_unsigned_int128<T>::value,
                                              std::true_type,
                                              std::false_type>::type;

template <class T>
using is_signed_int = typename std::conditional<(is_integral<T>::value &&
                                                 std::is_signed<T>::value) ||
                                                    is_signed_int128<T>::value,
                                                std::true_type,
                                                std::false_type>::type;

template <class T>
using is_unsigned_int =
    typename std::conditional<(is_integral<T>::value &&
                               std::is_unsigned<T>::value) ||
                                  is_unsigned_int128<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using to_unsigned = typename std::conditional<
    is_signed_int128<T>::value,
    make_unsigned_int128<T>,
    typename std::conditional<std::is_signed<T>::value,
                              std::make_unsigned<T>,
                              std::common_type<T>>::type>::type;

#else

template <class T> using is_integral = typename std::is_integral<T>;

template <class T>
using is_signed_int =
    typename std::conditional<is_integral<T>::value && std::is_signed<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using is_unsigned_int =
    typename std::conditional<is_integral<T>::value &&
                                  std::is_unsigned<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using to_unsigned = typename std::conditional<is_signed_int<T>::value,
                                              std::make_unsigned<T>,
                                              std::common_type<T>>::type;

#endif

template <class T>
using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;

template <class T>
using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;

template <class T> using to_unsigned_t = typename to_unsigned<T>::type;

}  // namespace internal

}  // namespace atcoder

#include <cassert>
#include <numeric>
#include <type_traits>

#ifdef _MSC_VER
#include <intrin.h>
#endif

namespace atcoder {

namespace internal {

struct modint_base {};
struct static_modint_base : modint_base {};

template <class T> using is_modint = std::is_base_of<modint_base, T>;
template <class T> using is_modint_t = std::enable_if_t<is_modint<T>::value>;

}  // namespace internal

template <int m, std::enable_if_t<(1 <= m)>* = nullptr>
struct static_modint : internal::static_modint_base {
    using mint = static_modint;

  public:
    static constexpr int mod() { return m; }
    static mint raw(int v) {
        mint x;
        x._v = v;
        return x;
    }

    static_modint() : _v(0) {}
    template <class T, internal::is_signed_int_t<T>* = nullptr>
    static_modint(T v) {
        long long x = (long long)(v % (long long)(umod()));
        if (x < 0) x += umod();
        _v = (unsigned int)(x);
    }
    template <class T, internal::is_unsigned_int_t<T>* = nullptr>
    static_modint(T v) {
        _v = (unsigned int)(v % umod());
    }
    static_modint(bool v) { _v = ((unsigned int)(v) % umod()); }

    unsigned int val() const { return _v; }

    mint& operator++() {
        _v++;
        if (_v == umod()) _v = 0;
        return *this;
    }
    mint& operator--() {
        if (_v == 0) _v = umod();
        _v--;
        return *this;
    }
    mint operator++(int) {
        mint result = *this;
        ++*this;
        return result;
    }
    mint operator--(int) {
        mint result = *this;
        --*this;
        return result;
    }

    mint& operator+=(const mint& rhs) {
        _v += rhs._v;
        if (_v >= umod()) _v -= umod();
        return *this;
    }
    mint& operator-=(const mint& rhs) {
        _v -= rhs._v;
        if (_v >= umod()) _v += umod();
        return *this;
    }
    mint& operator*=(const mint& rhs) {
        unsigned long long z = _v;
        z *= rhs._v;
        _v = (unsigned int)(z % umod());
        return *this;
    }
    mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }

    mint operator+() const { return *this; }
    mint operator-() const { return mint() - *this; }

    mint pow(long long n) const {
        assert(0 <= n);
        mint x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    mint inv() const {
        if (prime) {
            assert(_v);
            return pow(umod() - 2);
        } else {
            auto eg = internal::inv_gcd(_v, m);
            assert(eg.first == 1);
            return eg.second;
        }
    }

    friend mint operator+(const mint& lhs, const mint& rhs) {
        return mint(lhs) += rhs;
    }
    friend mint operator-(const mint& lhs, const mint& rhs) {
        return mint(lhs) -= rhs;
    }
    friend mint operator*(const mint& lhs, const mint& rhs) {
        return mint(lhs) *= rhs;
    }
    friend mint operator/(const mint& lhs, const mint& rhs) {
        return mint(lhs) /= rhs;
    }
    friend bool operator==(const mint& lhs, const mint& rhs) {
        return lhs._v == rhs._v;
    }
    friend bool operator!=(const mint& lhs, const mint& rhs) {
        return lhs._v != rhs._v;
    }

  private:
    unsigned int _v;
    static constexpr unsigned int umod() { return m; }
    static constexpr bool prime = internal::is_prime<m>;
};

template <int id> struct dynamic_modint : internal::modint_base {
    using mint = dynamic_modint;

  public:
    static int mod() { return (int)(bt.umod()); }
    static void set_mod(int m) {
        assert(1 <= m);
        bt = internal::barrett(m);
    }
    static mint raw(int v) {
        mint x;
        x._v = v;
        return x;
    }

    dynamic_modint() : _v(0) {}
    template <class T, internal::is_signed_int_t<T>* = nullptr>
    dynamic_modint(T v) {
        long long x = (long long)(v % (long long)(mod()));
        if (x < 0) x += mod();
        _v = (unsigned int)(x);
    }
    template <class T, internal::is_unsigned_int_t<T>* = nullptr>
    dynamic_modint(T v) {
        _v = (unsigned int)(v % mod());
    }
    dynamic_modint(bool v) { _v = ((unsigned int)(v) % mod()); }

    unsigned int val() const { return _v; }

    mint& operator++() {
        _v++;
        if (_v == umod()) _v = 0;
        return *this;
    }
    mint& operator--() {
        if (_v == 0) _v = umod();
        _v--;
        return *this;
    }
    mint operator++(int) {
        mint result = *this;
        ++*this;
        return result;
    }
    mint operator--(int) {
        mint result = *this;
        --*this;
        return result;
    }

    mint& operator+=(const mint& rhs) {
        _v += rhs._v;
        if (_v >= umod()) _v -= umod();
        return *this;
    }
    mint& operator-=(const mint& rhs) {
        _v += mod() - rhs._v;
        if (_v >= umod()) _v -= umod();
        return *this;
    }
    mint& operator*=(const mint& rhs) {
        _v = bt.mul(_v, rhs._v);
        return *this;
    }
    mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }

    mint operator+() const { return *this; }
    mint operator-() const { return mint() - *this; }

    mint pow(long long n) const {
        assert(0 <= n);
        mint x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    mint inv() const {
        auto eg = internal::inv_gcd(_v, mod());
        assert(eg.first == 1);
        return eg.second;
    }

    friend mint operator+(const mint& lhs, const mint& rhs) {
        return mint(lhs) += rhs;
    }
    friend mint operator-(const mint& lhs, const mint& rhs) {
        return mint(lhs) -= rhs;
    }
    friend mint operator*(const mint& lhs, const mint& rhs) {
        return mint(lhs) *= rhs;
    }
    friend mint operator/(const mint& lhs, const mint& rhs) {
        return mint(lhs) /= rhs;
    }
    friend bool operator==(const mint& lhs, const mint& rhs) {
        return lhs._v == rhs._v;
    }
    friend bool operator!=(const mint& lhs, const mint& rhs) {
        return lhs._v != rhs._v;
    }

  private:
    unsigned int _v;
    static internal::barrett bt;
    static unsigned int umod() { return bt.umod(); }
};
template <int id> internal::barrett dynamic_modint<id>::bt = 998244353;

using modint998244353 = static_modint<998244353>;
using modint1000000007 = static_modint<1000000007>;
using modint = dynamic_modint<-1>;

namespace internal {

template <class T>
using is_static_modint = std::is_base_of<internal::static_modint_base, T>;

template <class T>
using is_static_modint_t = std::enable_if_t<is_static_modint<T>::value>;

template <class> struct is_dynamic_modint : public std::false_type {};
template <int id>
struct is_dynamic_modint<dynamic_modint<id>> : public std::true_type {};

template <class T>
using is_dynamic_modint_t = std::enable_if_t<is_dynamic_modint<T>::value>;

}  // namespace internal

}  // namespace atcoder
typedef atcoder::modint MINT;
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N=5010,M=N*2;
const int mod=1e9+7;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
MINT C[N][N],dp[N][N],pw[N*N],ans;
void solve(){
    int n,m,q;
    cin>>n>>m>>q;
    MINT::set_mod(q);
    C[0][0]=pw[0]=dp[0][0]=1;
    for(int i=1;i<=max(n,m);i++){
        for(int j=1;j<=max(n,m);j++)C[i][j]=C[i-1][j]+C[i-1][j-1];
        C[i][0]=1;
        for(int j=1;j<=m;j++)dp[i][j]=i*(dp[i][j-1]+dp[i-1][j-1]);
    }
    for(int i=1;i<=n*m;i++)pw[i]=pw[i-1]*2;
    for(int k=2;k<=n;k++){
        MINT tmp=1;
        for(int j=1;j<=m-1;j++)tmp*=pw[k]-1;
        ans+=C[n][k]*pw[(m-1)*(n-k)]*tmp;
    }
    for(int k=2;k<=n;k++){
        MINT tmp=C[n][k]*pw[(m-1)*(n-k)],cur=1;
        for(int t=m-1;t>=k;t--){
            ans-=tmp*C[m-1][t]*dp[k][t]*cur;
            cur*=pw[k]-k-1;
        }
    }
    cout<<ans.val()<<"\n";
}

D ​

题意：

  • q次操作，每次操作t v，表示将数组末端弹出t个元素，加入元素v
  • 操作完后计算，s1⊕s2⊕s3...⊕sns_1 \oplus s_2 \oplus s_3...\oplus s_n ,sis_i 为后缀和
  • 答案对 2097152即2212097152即2^{21} 取模

思路：

  • 即求 ∑i=1n(sn−si−1)mod221\sum_{i=1}^n (s_n-s_{i-1}) mod 2^{21}
  • 按位计算，只需要考虑21位
  • 后缀和转前缀和
  • 第 dd 位有贡献，(sn−si−1)mod2d+1>=2d(s_n-s_{i-1})mod 2^{d+1}>= 2^d
  • 令 x=(−si−1)mod2d+1x=(-s_{i-1})mod 2^{d+1}，查询有多少个 xx 满足 (sn+x)mod2d+1>=2d(s_n+x) mod 2^{d+1}>=2^d 即可，可以用树状数组查
  • l=2d,r=2d+1−1,l≤(sn+x)≤r,l−sn≤x≤r−snl=2^d,r=2^{d+1}-1,l \leq (s_n+x) \leq r,l-s_n \leq x \leq r-s_n
  • 值域范围会被分成一段或两段区间
  • 注意最后一个元素不用加进树状数组
cpp
struct BIT{
    vector<int> c;
    int n;
    BIT(){}
    BIT(int n):n(n){
        c=vector<int> (n+10);
    }
    void add(int x,int y){
        x++;
        for(int i=x;i<=n;i+=i&-i)c[i]+=y;
    }
    int query(int x){
        x++;
        int ans=0;
        for(int i=x;i;i&=i-1)ans+=c[i];
        return ans;
    }
    int query(int l,int r){
        if(l>r)return 0;
        return query(r)-query(l-1);
    }
} t[21];
int sum[N],st[N],top;
void pop(int x){
    for(int i=0;i<21;i++){
        int p=1<<i+1;
        int val=(-x%p+p)%p;
        t[i].add(val,-1);
    }
}
void push(int x){
    for(int i=0;i<21;i++){
        int p=1<<i+1;
        int val=(-x%p+p)%p;
        t[i].add(val,1);
    }
}
int cal(){
    int x=sum[top];
    int ans=0;
    for(int i=0;i<21;i++){
        int l=1<<i,p=1<<i+1,r=p-1;
        l=(l-x%p+p)%p,r=(r-x%p+p)%p;
        int cnt=0;
        if(l<=r)cnt+=t[i].query(l,r);
        else cnt+=t[i].query(0,r)+t[i].query(l,p-1);
        if(cnt&1)ans+=1<<i;
    }
    return ans;
}
void solve(){
    int q;
    cin>>q;
    for(int i=0;i<21;i++)t[i]=BIT(1<<i+1);
    while(q--){
        int t,v;
        cin>>t>>v;
        while(t--){
            int x=sum[--top];
            pop(x);
        }
        push(sum[top]);
        st[++top]=v;
        sum[top]=sum[top-1]+v;
        cout<<cal()<<"\n";
    }
}

第二场 ​

B ​

题意：

  • 给定n个点的简单带权无向图G
  • 每次询问一个点集S，求S关于G导出子图的最小生成树
  • 没有输出-1
  • 2≤n≤105,1≤m,q≤105∑ki≤1052 \leq n \leq 10^5,1 \leq m,q \leq 10^5 \sum k_i \leq 10^5

思路：

解法一：

对于每次询问，枚举 n2n^2 的所有点，跑kruscal，时间复杂度 O(n2logn)O(n^2logn)

如果是枚举相关边，则为 O(mlogn)O(mlogn)

考虑根号分治，B=nB=\sqrt n

  • 对于 ≤B\leq B 的询问，使用方法一，时间复杂度为 O(nBlogn)O(nB logn)，可以看作每个点都要乘一个B
  • 否则，使用方法二，时间复杂度为 O(nBmlogn)O(\frac{n}{B}mlogn),大于B的询问不会超过 nB\frac{n}{B} 次
cpp
struct Edge{
    int u,v,w;
    bool operator<(const Edge&tmp)const{
        return w>tmp.w;
    }
};
struct DSU{
    vector<int> par;
    void init(int n){
        par.resize(n);
        iota(par.begin(),par.end(),0);
    }
    int find(int x){
        return par[x]==x?x:par[x]=find(par[x]);
    }
    bool merge(int x,int y){
        x=find(x),y=find(y);
        if(x==y)return false;
        par[y]=x;
        return true;
    }
} dsu;
int kruscal(priority_queue<Edge> &q,vector<int> &a){
    for(auto &x:a)dsu.par[x]=x;
    int ans=0,cnt=0;
    while(!q.empty()){
        auto [u,v,w]=q.top();
        q.pop();
        if(!dsu.merge(u,v))continue;
        ans+=w;
        if(++cnt==a.size()-1)break;
    }
    return (cnt==a.size()-1?ans:-1);
}
void solve(){
    int n,m,q;
    cin>>n>>m>>q;
    vector<Edge> e;
    map<PII,int> adj;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        if(u>v)swap(u,v);
        e.push_back({u,v,w});
        if(adj.count({u,v}))adj[{u,v}]=min(adj[{u,v}],w);
        else adj[{u,v}]=w;
    }
    int block=sqrt(n);
    vector<bool> vis(n+1);
    dsu.init(n+1);
    while(q--){
        int k;
        cin>>k;
        vector<int> a(k);
        for(int i=0;i<k;i++)cin>>a[i],vis[a[i]]=1;
        priority_queue<Edge> q;
        if(k<=block){
            for(int i=0;i<k;i++){
                for(int j=0;j<i;j++){
                    int x=a[i],y=a[j];
                    if(x>y)swap(x,y);
                    if(adj.count({x,y}))q.push({x,y,adj[{x,y}]});
                }
            }
        }
        else{
            for(auto &[u,v,w]:e){
                if(vis[u]&&vis[v])q.push({u,v,w});
            }
        }
        for(int i=0;i<k;i++)vis[a[i]]=0;
        cout<<kruscal(q,a)<<"\n";
    }
}

解法二：

  • 考虑平衡每个点的度数，只设置单向边，让度数小的连向度数大的
  • 那么每个点的平均边数会变成 O(m)O(\sqrt m)
  • 时间复杂度： O(∣S∣mlog(∣S∣log(n)))O(|S|\sqrt m log(|S|log(n)))
cpp
struct Edge{
    int u,v,w;
    bool operator<(const Edge&tmp)const{
        return w>tmp.w;
    }
};
struct DSU{
    vector<int> par;
    void init(int n){
        par.resize(n);
        iota(par.begin(),par.end(),0);
    }
    int find(int x){
        return par[x]==x?x:par[x]=find(par[x]);
    }
    bool merge(int x,int y){
        x=find(x),y=find(y);
        if(x==y)return false;
        par[y]=x;
        return true;
    }
} dsu;
int kruscal(priority_queue<Edge> &q,vector<int> &a){
    for(auto &x:a)dsu.par[x]=x;
    int ans=0,cnt=0;
    while(!q.empty()){
        auto [u,v,w]=q.top();
        q.pop();
        if(!dsu.merge(u,v))continue;
        ans+=w;
        if(++cnt==a.size()-1)break;
    }
    return (cnt==a.size()-1?ans:-1);
}
void solve(){
    int n,m,q;
    cin>>n>>m>>q;
    vector<array<int,2>> node[n+1];
    vector<Edge> e;
    vector<int> len(n+1);
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        len[u]++,len[v]++;
        e.push_back({u,v,w});
    }
    for(auto [u,v,w]:e){
        if(len[u]>len[v])swap(u,v);
        node[u].push_back({v,w});
    }
    vector<bool> vis(n+1);
    dsu.init(n+1);
    while(q--){
        int k;
        cin>>k;
        vector<int> a(k);
        priority_queue<Edge> q;
        for(auto &x:a)cin>>x,vis[x]=1;
        for(auto &x:a){
            for(auto &[y,w]:node[x]){
                if(vis[y])q.push({x,y,w});
            }
        }
        for(auto &x:a)vis[x]=0;
        cout<<kruscal(q,a)<<"\n";
    }
}

解法三：

  • 如果查询 ∣S∣≤105|S| \leq 10^5,直接prim
  • 否则直接遍历所有边kruscal，这样的询问最多不超过 n\sqrt n 次

G ​

题意：

定义一个多重数集合是好的，但且仅当集合中元素乘积是一个正整数的 平方，集合的权值为这个正整数的值。

求大小为N的多重数集的所有子集中所有好集的权值和

1≤N≤1000,1≤Si≤10001 \leq N \leq 1000,1 \leq S_i \leq 1000

思路：

  • 对于每个数Si，大于等于32的质数最多有一个，32*32=1024>1000
  • 对于小质数状压，大质数分组背包即可
  • 注意：空集合的值为1，最后答案需要减去
cpp
int prime[11]={2,3,5,7,11,13,17,19,23,29,31};
int f[2][N][2];//f[i][j][k]表示枚举到第i个数，当前状态为j，当前大质数指数是奇数(1)还是偶数(0)
void solve(){
    int n;
    cin>>n;
    vector<int> a(n+1);
    vector<PII> nums[1010];
    f[0][0][0]=1;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        int mask=0,val=1;
        for(int j=0;j<11;j++){
            while(a[i]%prime[j]==0){
                if(mask>>j&1)(val*=prime[j])%=mod;
                mask^=1<<j;
                a[i]/=prime[j];
            }
        }
        nums[a[i]].push_back({mask,val});
    }
    int cur=0;
    auto cal=[&](int x,int y){
        int ans=1;
        for(int i=0;i<11;i++){
            if((x&y)>>i&1)(ans*=prime[i])%=mod;
        }
        return ans;
    };
    for(auto [mask,val]:nums[1]){
        for(int i=0;i<N;i++)f[cur^1][i][0]=f[cur][i][0];
        for(int i=0;i<N;i++)(f[cur^1][mask^i][0]+=f[cur][i][0]*val%mod*cal(mask,i)%mod)%=mod;
        cur^=1;
    }
    for(int j=32;j<=1000;j++){
        if(nums[j].size()==0)continue;
        for(int i=0;i<N;i++)f[cur][i][1]=0;//清空上一个数的1，因为不能构成平方数
        for(auto [mask,val]:nums[j]){
            for(int i=0;i<N;i++)f[cur^1][i][0]=f[cur][i][0],f[cur^1][i][1]=f[cur][i][1];
            for(int i=0;i<N;i++){
                (f[cur^1][mask^i][0]+=f[cur][i][1]*val%mod*cal(mask,i)%mod*j%mod)%=mod;
                (f[cur^1][mask^i][1]+=f[cur][i][0]*val%mod*cal(mask,i)%mod)%=mod;
            }
            cur^=1;
        }
    }
    cout<<(f[cur][0][0]-1+mod)%mod;
}

H ​

题意：

给定一个长度为 2 × n 的数组，1 到 n 每个元素恰好出现两次

每次操作可以删除一个长度不小于 2 的连续子数组，需要满足该子数组 首尾相同，获得该连续子数组“首尾元素值”乘以“元素数量”的分数

问最终可以得到的最大分数

1≤n,ai≤30001 \leq n,a_i \leq 3000

思路：

  • 考虑区间从小到达进行dp
  • 用小区间来更新大区间
cpp
int n,a[N];
struct Node{
    int l,r,val;
} tmp[N];
int dp[N];
int cal(int l,int r,int x){
    for(int i=l-1;i<=r;i++)dp[i]=0;
    for(int i=l;i<=r;i++){
        dp[i]=max(dp[i],dp[i-1]+x);
        if(tmp[a[i]].val){
            auto [L,R,val]=tmp[a[i]];
            if(L==i&&R<=r)dp[R]=max(dp[R],dp[i-1]+val);
        }
    }
    return dp[r];
}   
void solve(){
    cin>>n;
    map<int,int> mp;
    for(int i=1;i<=2*n;i++){
        cin>>a[i];
        if(mp.count(a[i]))tmp[a[i]]={mp[a[i]],i,0};
        else mp[a[i]]=i;
    }
    for(int i=n;i>=1;i--){
        auto &[x,y,z]=tmp[i];
        z=cal(x,y,i);
    }
    for(int i=0;i<=2*n;i++)dp[i]=0;
    for(int i=1;i<=2*n;i++){
        dp[i]=max(dp[i],dp[i-1]);
        auto [L,R,val]=tmp[a[i]];
        if(L==i)dp[R]=max(dp[R],dp[i-1]+val);
    }
    cout<<dp[2*n]<<"\n";
}

第三场 ​

A ​

题意：

nn 个人在河的一侧，第 ii 个人有体力值 hih_i

有且仅有一艘能容纳 L到RL到 R 个人的船

问是否能将所有人从河的左侧运送到右侧

思路：

  • 不包含最后一次运走的R个人，来回趟数为 ⌈n−RR−L⌉\lceil \frac{n-R}{R-L} \rceil
  • 对于每个人，能多来回的次数为 ⌊hi−12⌋\lfloor \frac{h_i-1}{2} \rfloor
  • 判断是否 SL≤sumSL \leq sum 即可
cpp
void solve(){
    int n,L,R;
    cin>>n>>L>>R;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    int k=(n-R+R-L-1)/(R-L);
    int sum=0;
    for(int i=1;i<=n;i++)sum+=min(k,(a[i]-1)/2);
    if(sum>=k*L)cout<<"YES\n";
    else cout<<"NO\n";
}

D ​

题意：

  • 一张牌有两个数，在左和右
  • 考虑将这些牌横置成一排，属于不同牌的相邻数必须不同
  • 可以直接贪心，优先放数多的
cpp
void solve(){
    int n;
    cin>>n;
    vector<int> nums;
    vector<PII> a(n);
    for(auto &[x,y]:a)cin>>x>>y;
    map<int,multiset<int>> mp;
    set<PII> s;
    for(int i=0;i<n;i++){
        auto &[x,y]=a[i];
        mp[x].insert(i);
        mp[y].insert(i);
    }
    for(auto &[x,y]:mp){
        s.insert({y.size(),x});
    }
    if(s.rbegin()->first>n+1){
        cout<<"No\n";
        return;
    }
    int lst=-1;
    cout<<"Yes\n";
    while(!s.empty()){
        auto it=s.end();
        it--;
        if(lst==it->second)it--;
        auto &[z,x]=*it;
        int id=*mp[x].rbegin();
        if(a[id].first==x)cout<<a[id].first<<" "<<a[id].second<<"\n",lst=a[id].second;
        else cout<<a[id].second<<" "<<a[id].first<<"\n",lst=a[id].first;
        s.erase({z,x});
        s.erase({mp[lst].size(),lst});
        mp[x].erase(id);
        mp[lst].erase(id);
        if(mp[x].size())s.insert({mp[x].size(),x});
        if(mp[lst].size())s.insert({mp[lst].size(),lst});
    }
}

第四场 ​

A ​

题意：

给定一颗有根树，每次询问前i条边组成的森林中，已第c_i个点为根的树的深度。

思路：

  1. 带权并查集维护每个点到当前根节点的距离 deepudeep_u

  2. 每个根节点维护一个当前深度 fuf_u

  3. 当连接u,v，其中u为父亲时，设root_u为此时u节点的根，那么可以更新此时的 frootu=max(frootu,deepu+fv+1)f_{root_u}=max(f_{root_u},deep_u+f_v+1)

cpp
struct DSU{
    vector<int> par,dis,mxdis;
    DSU(int n){
        par.resize(n);
        dis.resize(n);
        mxdis.resize(n);
        iota(par.begin(),par.end(),0);
    }
    int find(int x){
        if(par[x]==x)return x;
        int t=par[x];
        // mxdis[t]=max(mxdis[t],mxdis[])
        par[x]=find(par[x]);
        dis[x]+=dis[t];
        return par[x];
    }
    bool merge(int x,int y){
		int px = find(x);
		int py = find(y);
		if (px != py)
		{
			par[px] = py;
			dis[px] = -dis[x] + dis[y] + 1;
            mxdis[py]=max(mxdis[px]+dis[y]+1,mxdis[py]);
		}
        // mxdis[find(x)]=max(mxdis[find(x)],dis[x]);
        // mxdis[find(y)]=max(mxdis[find(y)],dis[y]);
        find(x);
        return true;
    }
    int get(int x){
        return mxdis[find(x)];
    }
};
void solve(){
    int n;
    cin>>n;
    DSU dsu(n+1);
    for(int i=1;i<n;i++){
        int a,b,c;
        cin>>a>>b>>c;
        dsu.merge(b,a);
        // for(int j=1;j<=n;j++)cout<<dsu.mxdis[j]<<" \n"[j==n];
        cout<<dsu.get(c)<<" ";
    }
    cout<<"\n";
}

C ​

题意：

给定一个排列，每次选择四个位置任意交换其中的元素，求排序的最小次数。

思路：

  • i→aii \rightarrow a_i 连环
  • len=3,4的可以一次性排好
  • 两个len=2可以一次排好
  • len>4,每次可以让len-3
  • len=2的环最后两两合并处理即可
cpp
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+1);
    vector<int> b(5);
    int ans=0;
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            int x=i;
            int cnt=0;
            while(!vis[x]){
                vis[x]=1;
                x=a[x];
                cnt++;
            }
            ans+=(cnt-1)/3;
            b[(cnt-1)%3+1]++;
        }
    }
    ans+=b[3]+(b[2]+1)/2;
    cout<<ans<<"\n";
}

H ​

题意：

给两种操作：排序数组后在值域上翻折一个前缀或翻折一个后缀，问任意次操作能做到的最小极差

思路：

答案为当前gcd

cpp
void solve(){
    int n;
    cin>>n;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a.begin()+1,a.end());
    bool g=0;
    for(int i=2;i<=n;i++)g|=(a[i]!=a[i-1]);
    if(!g){
        cout<<"0\n";
        return;
    }
    int gcd=0;
    for(int i=2;i<=n;i++){
        gcd=__gcd(gcd,a[i]-a[i-1]);
    }
    cout<<gcd<<"\n";
}

I ​

题意：

cpp
void solve(){
    int n,m;
    cin>>n>>m;
    map<int,bool> vis[n+1];
    vector<int> mex(n+10);
    iota(mex.begin(),mex.end(),1);
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        if(u>v)swap(u,v);
        vis[u][v]=1;
        while(vis[u].count(mex[u]))mex[u]++;
    }
    int ans=0;
    for(int i=n;i>=1;i--){
        mex[i]--;
        mex[i]=min(mex[i],mex[i+1]);
        ans+=mex[i]-i+1;
    }
    cout<<ans<<'\n';
}

第五场 ​

B ​

分类讨论

J ​

dp

K ​

dp

第六场 ​

A ​

dp

D ​

tarjan

F ​

待补

I ​

dp

J ​

分类讨论

第七场 ​

C ​

Sorting network,双调排序,待补

G ​

网络流，狼抓兔子，待补

H ​

大模拟，待补

D ​

题意：

询问区间内所有数均出现k次的区间数量

思路1(异或哈希)：

cpp
mt19937_64 rng(time(0));
void solve(){
    int n,k;
    cin>>n>>k;
    vector<int> a(n+1),nums,freq(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        nums.push_back(a[i]);
    }
    sort(nums.begin(),nums.end());
    nums.erase(unique(nums.begin(),nums.end()),nums.end());
    for(int i=1;i<=n;i++)a[i]=lower_bound(nums.begin(),nums.end(),a[i])-nums.begin()+1;
    vector<ULL> h(n+1),rdm(n+1);
    for(int i=0;i<=n;i++)rdm[i]=rng();
    vector<int> fre(n+1);
    for(int i=1;i<=n;i++){
        h[i]=h[i-1];
        h[i]-=fre[a[i]]*rdm[a[i]];
        (fre[a[i]]+=1)%=k;
        h[i]+=fre[a[i]]*rdm[a[i]];
    }
    fre.assign(n+1,0);
    unordered_map<ULL,int> cnt;
    cnt[0]=1;
    int ans=0;
    for(int i=1,j=0;i<=n;i++){
        fre[a[i]]++;
        while(fre[a[i]]>k){
            fre[a[j]]--;
            cnt[h[j-1]]--;
            j++;
        }
        ans+=cnt[h[i]]++;
    }
    cout<<ans<<"\n";
}

思路2(扫描线)：

cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
int n,m;
struct Node{
    int l,r,len,tag;
};
struct SegmentTree{
    vector<Node> t;
    SegmentTree(int n){
        t=vector<Node>(n<<2);
    }
    void pushup(int p){ 
        if(t[p].tag)t[p].len=t[p].r-t[p].l+1;
        else if(t[p].l!=t[p].r)t[p].len=t[p<<1].len+t[p<<1|1].len;
        else t[p].len=0;
    }
    void build(int p,int l,int r){
        t[p]={l,r,0,0};
        if(l==r)return;
        int mid=l+r>>1;
        build(p<<1,l,mid);
        build(p<<1|1,mid+1,r);
        pushup(p);
    }
    void modify(int p,int l,int r,int x){
        if(l<=t[p].l&&r>=t[p].r){
            t[p].tag+=x;
            pushup(p);
            return;
        }
        int mid=t[p].l+t[p].r>>1;
        if(l<=mid)modify(p<<1,l,r,x);
        if(r>mid)modify(p<<1|1,l,r,x);
        pushup(p);
    }
    int query(int p,int l,int r){
        if(l<=t[p].l&&r>=t[p].r)return t[p].len;
        int mid=t[p].l+t[p].r>>1;
        int ans=0;
        if(l<=mid)ans+=query(p<<1,l,r);
        if(r>mid)ans+=query(p<<1|1,l,r);
        return ans;
    }
};
void solve(){
    int n,k;
    cin>>n>>k;
    vector<int> a(n+1);
    vector<array<int,2>> e[n+1];
    map<int,vector<int>> pos;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        pos[a[i]].push_back(i);
    }
    for(int i=1;i<=n;i++){
        auto &p=pos[a[i]];
        int t=lower_bound(p.begin(),p.end(),i)-p.begin();
        if(t+k-1<p.size()){
            if(k!=1)e[i].push_back({i,p[t+k-1]-1});
        }
        else e[i].push_back({i,n});
        if(t+k<p.size())e[i].push_back({p[t+k],n});
    }
    SegmentTree seg(n+1);
    seg.build(1,1,n);
    int ans=0;
    map<int,int> lst;
    for(int i=n;i>=1;i--){
        if(lst.count(a[i])){
            for(auto [l,r]:e[lst[a[i]]])seg.modify(1,l,r,-1);
        }
        for(auto [l,r]:e[i])seg.modify(1,l,r,1);
        ans+=n-i+1-seg.query(1,i,n);
        lst[a[i]]=i;
    }
    cout<<ans<<"\n";
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int T=1;
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    cin>>T;
    while(T--)solve();
    return 0;
}

K ​

题意：

给定两个字符串 S,T，求 S中有多少本质不同的子序列，包含前缀 T并

且要求该子序列的反串也同时包含前缀 T

思路：

  • 首先先贪心，从 S的前缀中取一个子序列 T，找到能够包含该子序列且 最短的前缀位置，然后反过来从后往前找能包含该子序列且最短的后缀 位置。
  • 如果这两个位置没有交叉，首先答案至少是从这两个位置切开，剩余部 分本质不同的子序列数目，这是一个经典字符串 dp，你可以直接搜索 “动态规划：本质不同子序列数”。
  • 例如 S = ”abegfhbca”, T = ”ab”，此时贪心取到的最短前缀为 ab，最短 后缀为 bca。把这两部分去掉，相当于求中间部分 ”egfh”的子序列数目。
  • 当然，如果只算不交叉部分，会发现答案漏了一些。正好丢掉了 T在所 选子序列中交叉的情况，同时注意到 T一旦在正反串中交叉，就会使得 该字符串变为回文串。
  • 而 T又是该回文串的一个前缀，所以对 T的后缀跑一个马拉车/哈希求 回文中心，对于每一个回文中心，看对称过去之后的部分，能否在 S中 取到，这里只需要考虑每个回文中心能构成最长的回文即可（因为回文 中心相同时，实际上最后构成的子序列本质相同）。检查每一个后缀回 文中心能否取到对应的子序列，加上其贡献即可。
cpp
int p[N*2],l[N],r[N],dp[N];
char ma[N*2];
void manacher(string tmp){
    string s="";
    s+="$#";
    for(auto c:tmp)s+=c,s+="#";
    s+="^";
    int n=s.size();
    int mr=0,mid;
    for(int i=0;i<n;i++){
        if(i<mr)p[i]=min(p[2*mid-i],mr-i);
        else p[i]=1;
        while(s[i-p[i]]==s[i+p[i]])p[i]++;
        if(i+p[i]>mr){
            mr=i+p[i];
            mid=i;
        }
    }
}
string s,t;
int n,m;
void init(){
    for(int i=1;i<=m;i++)l[i]=r[i]=-1;
    for(int i=1,j=1;i<=n;i++){
        if(j<=m&&s[i]==t[j]){
            l[j]=i;
            j++;
        }
    }
    r[0]=n+1;
    for(int i=n,j=1;i>=1;i--){
        if(j<=m&&s[i]==t[j]){
            r[j]=i;
            j++;
        }
    }
}
void solve(){
    cin>>n>>m>>s>>t;
    manacher(t);
    s=" "+s;
    t=" "+t;
    init();
    int ans=0;
    if(l[m]==-1||r[m]==-1){
        cout<<"0\n";
        return;
    }
    for(int i=0;i<2*m+2;i++){
        if(i+p[i]==2*m+2&&p[i]-1)ans+=(l[m]<r[m-p[i]+1]);
    }
    if(l[m]<r[m]){
        vector<int> lst(26);
        dp[l[m]]=1;
        for(int i=l[m]+1;i<r[m];i++){
            if(lst[s[i]-'a'])dp[i]=((dp[i-1]*2-dp[lst[s[i]-'a']-1])%mod+mod)%mod;
            else dp[i]=dp[i-1]*2%mod;
            lst[s[i]-'a']=i;
        }
        (ans+=dp[r[m]-1])%=mod;
    }
    cout<<ans<<"\n";
}

第八场 ​

A ​

题意：

有一个集合，两个人玩游戏。

每次一个人选择两个数，满足它们的 gcd 不在集合里。

然后插入 gcd 的值。

无法行动的人输，问赢家。

思路：

对于 d 枚举所有 d 的倍数并求它们的 gcd，最后检查 gcd 是否等于 d。

D ​

大模拟

E ​

Pollard_Rho，区间筛

G ​

dp

J ​

构造题

第九场 ​

B ​

题意：

思路：

cpp
struct Node{
    int l,r,sum,tag,val,add;
};
struct SegmentTree{
    vector<Node> t;
    SegmentTree(int n){
        t=vector<Node> (n<<2);
    }
    void build(int p,int l,int r){
        t[p]={l,r,0,0,0};
        if(l==r)return;
        int mid=l+r>>1;
        build(p<<1,l,mid);
        build(p<<1|1,mid+1,r);
    }
    void pushup(int p){
        t[p].sum=(t[p<<1].sum+t[p<<1|1].sum)%mod;
        t[p].val=(t[p<<1].val+t[p<<1|1].val)%mod;
    }
    void pushdown(int p){
        if(t[p].add){
            t[p<<1].tag+=t[p].add;
            t[p<<1|1].tag+=t[p].add;
            t[p<<1].add+=t[p].add;
            t[p<<1|1].add+=t[p].add;
            if(!t[p<<1].tag)t[p<<1].sum=t[p<<1].val;
            else t[p<<1].sum=0;
            if(!t[p<<1|1].tag)t[p<<1|1].sum=t[p<<1|1].val;
            else t[p<<1|1].sum=0;
            t[p].add=0;
        }
    }
    void modify(int p,int x,int y){
        if(t[p].l==t[p].r){
            t[p].val=y;
            if(!t[p].tag)t[p].sum=t[p].val;
            else t[p].sum=0;
            return;
        }
        pushdown(p);
        int mid=t[p].l+t[p].r>>1;
        if(x<=mid)modify(p<<1,x,y);
        else modify(p<<1|1,x,y);
        pushup(p);
    }
    void modify_tag(int p,int l,int r,int x){
        if(l<=t[p].l&&r>=t[p].r){
            t[p].tag+=x;
            t[p].add+=x;
            if(!t[p].tag)t[p].sum=t[p].val;
            else t[p].sum=0;
            return;
        }
        pushdown(p);
        int mid=t[p].l+t[p].r>>1;
        if(l<=mid)modify_tag(p<<1,l,r,x);
        if(r>mid)modify_tag(p<<1|1,l,r,x);
        pushup(p);
    }
    int query(int p,int l,int r){
        if(l<=t[p].l&&r>=t[p].r)return t[p].sum;
        pushdown(p);
        int mid=t[p].l+t[p].r>>1;
        int res=0;
        if(l<=mid)res+=query(p<<1,l,r);
        res%=mod;
        if(r>mid)res+=query(p<<1|1,l,r);
        res%=mod;
        return res;
    }
};
void solve(){
    int n,m;
    cin>>n>>m;
    vector<int> a(n+1),pos[n+1],dp(n+1),s;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        pos[i].push_back(0);
    }
    for(int i=1;i<=m;i++){
        int x;
        cin>>x;
        s.push_back(x);
    }
    sort(s.begin(),s.end());
    dp[0]=1;
    SegmentTree seg(n+1);
    seg.build(1,0,n);
    seg.modify(1,0,1);
    for(int i=1;i<=n;i++){
        for(int j=0;j<s.size();j++){
            if(pos[a[i]].size()>=s[j]+1){
                int tmp=pos[a[i]].size()-1-s[j];
                int l=pos[a[i]][tmp],r=pos[a[i]][tmp+1]-1;
                seg.modify_tag(1,l,r,-1);
            }
        }
        pos[a[i]].push_back(i);
        for(int j=0;j<s.size();j++){
            if(pos[a[i]].size()>=s[j]+1){
                int tmp=pos[a[i]].size()-1-s[j];
                int l=pos[a[i]][tmp],r=pos[a[i]][tmp+1]-1;
                seg.modify_tag(1,l,r,1);
            }
        }
        dp[i]=seg.query(1,0,i-1);
        // cout<<mn<<" "<<s<<"\n";
        seg.modify(1,i,dp[i]);
    }
    cout<<dp[n]%mod<<"\n";
}

C ​

欧拉函数，待补

G ​

待补

H ​

旋转卡壳

第十场 ​

D ​

dp思维

J ​

待补

K ​

二分，待补

L ​

暴力，待补

Wenwei Lin · 2022 — 2025