魔のkyo的BLOG

typedef long long ll;

template<typename T>
class ChthollyTree {
private:
    struct ChthollyNode {
        ll l, r;
        mutable T w;
        ChthollyNode(ll l, ll r=0, const T& w=T()): l(l),r(r),w(w) {}
        bool operator < (const ChthollyNode& n) const {
            return l < n.l;
        }
    };
    set<ChthollyNode> s;
public:
    ChthollyTree(ll n=1e9+2, const T& v=T()) { s.insert(ChthollyNode(-1, n, v)); }

    auto split(ll pos) {
        auto itr = s.lower_bound(pos);
        if (itr != s.end() && itr->l == pos) return itr;
        --itr;
        auto l = itr->l;
        auto r = itr->r;
        auto w = itr->w;
        s.erase(itr);
        s.insert(ChthollyNode(l, pos, w));
        return s.insert(ChthollyNode(pos, r, w)).first;
    }

    void update(ll l, ll r, function<void(ChthollyNode&)> f) {
        auto right = split(r), left = split(l);
        for(auto itr = left; itr != right; itr++) {
            f(const_cast<ChthollyNode&>(*itr));
        }
    }

    void assign(ll l, ll r, const T& w) {
        auto right = split(r), left = split(l);
        s.erase(left, right);
        s.insert(ChthollyNode(l, r, w));
    }

    void visit(ll l, ll r, function<void(const ChthollyNode&)> f) {
        auto left = s.lower_bound(l);
        if (left == s.end() || left->l != l) --left;
        auto right = s.lower_bound(r);
        for(auto itr = left; itr != right; itr++) {
            f(*itr);
        }
    }

private:
    class ItemAccessor {
    public:
        ItemAccessor(ChthollyTree& ct, ll i): ct(ct), i(i) {}
        ItemAccessor& operator = (const T& x) {ct.assign(i, i+1, x);return *this;}
        ItemAccessor& operator += (const T& x) {ct.update(i, i+1, [x](auto& p){p.w += x;});return *this;}
        ItemAccessor& operator -= (const T& x) {ct.update(i, i+1, [x](auto& p){p.w -= x;});return *this;}
        operator T() const {T r;ct.visit(i, i+1, [&r](auto& p){r = p.w;}); return r;}
    private:
        ChthollyTree& ct;
        ll i;
    };

    class RangeAccessor {
    public:
        RangeAccessor(ChthollyTree& ct, ll b, ll e):ct(ct), b(b), e(e) {}
        void operator = (const T& x) {ct.assign(b, e, x);}
        void operator += (const T& x) {ct.update(b, e, [&x](auto& p){p.w += x;});}
        void operator -= (const T& x) {ct.update(b, e, [&x](auto& p){p.w -= x;});}
    private:
        ChthollyTree& ct;
        ll b;
        ll e;
    };

public:
    // 通过下标访问单点值的语法糖
    ItemAccessor operator [] (ll i) {
        return ItemAccessor(*this, i);
    }

    // 通过下标访问区间值的语法糖
    RangeAccessor operator [] (const tuple<ll, ll>& range) {
        return RangeAccessor(*this, std::get<0>(range), std::get<1>(range));
    }

    T sum(ll l, ll r) {
        T ret = 0;
        visit(l, r, [&](auto& p) {
            ret += p.w * (std::min(p.r, r)-std::max(p.l, l));
        });
        return ret;
    }

    T min(ll l, ll r) {
        bool first = true;
        T ret = 0;
        visit(l, r, [&](auto& p) {
            if(first) {
                first = false;
                ret = p.w;
            } else {
                ret = std::min(ret, p.w);
            }
        });
        return ret;
    }
    
    T max(ll l, ll r) {
        bool first = true;
        T ret = 0;
        visit(l, r, [&](auto& p) {
            if(first) {
                first = false;
                ret = p.w;
            } else {
                ret = std::max(ret, p.w);
            }
        });
        return ret;
    }
};

template<typename T, typename Cmp=less<int>>
class RMQ {
    vector<vector<T>> dp; //dp[i][j]表示从a[i]起连续2^j次方个数的最值

    static int ceil_log2(int n) {
        int r = 0;
        while((1<<r)<n) r++;
        return r;
    }

    static int floor_log2(int n) {
        int r = 0;
        while((1<<r)<=n) r++;
        return r-1;
    }

    int max_or_min(const T& a, const T& b) const {
        return Cmp()(a, b)?a:b;
    }

public:
    RMQ() = default;
    RMQ(const T* a, int n) {init(a, n);}
    RMQ(const vector<T>& a) {init(&a[0], a.size());}

    void init(const T* a, int n) {
        dp.resize(n, vector<T>(ceil_log2(n)+1));
        for(int i=0;i<n;i++){
            dp[i][0] = a[i];
        }
        for(int j=1,s=1;s<n;s=(1<<j++)){
            for(int i=0;i+s<n;i++){
                dp[i][j] = max_or_min(dp[i][j-1], dp[i+s][j-1]);
            }           
        }
    }
    
    //返回[i, j]范围内的最值
    T query(int i, int j) const {
        assert(i<=j);
        int k = floor_log2(j-i+1);
        return max_or_min(dp[i][k], dp[j-(1<<k)+1][k]);
    }
};

template<typename T>
using RMinQ = RMQ<T, less<T>>;
template<typename T>
using RMaxQ = RMQ<T, greater<T>>;

// 二维向量
struct v2d {
    double x;
    double y;
};

// 二维向量拟叉积运算
double pseudoCross(const v2d& v1, const v2d& v2) {
    return v1.x * v2.y - v1.y * v2.x;
}

v2d operator - (const v2d& v1, const v2d& v2) {
    return v2d{v1.x-v2.x, v1.y-v2.y};
}

// 返回一个逆时针围成的凸包（如果要顺时针可以把上下边界换一换，改变while中的比较就可以）
vector<v2d> convexHull(vector<v2d>& pnts) {
    sort(pnts.begin(), pnts.end(), [](const v2d& v1, const v2d& v2) {
        return ((v1.x != v2.x)?(v1.x< v2.x):(v1.y < v2.y));
    });
    int n = pnts.size();
    vector<int> v(n*2); // v 其实是两个单调栈在中间接起来
    int p = n; // 从v中间向后增长的单调栈, p为栈顶的下一个位置（将要被使用的空间）
    int q = n; // 从v中间向前增长的单调栈, q为栈顶的下一个位置（将要被使用的空间）
    for(int i=0; i<n; i++){
        while(p-n>=2 && pseudoCross(pnts[i]-pnts[v[p-1]], pnts[v[p-1]]-pnts[v[p-2]])>=0){
            p--; // 弯曲方向不对，出栈
        }
        while(n-q>=2 && pseudoCross(pnts[i]-pnts[v[q+1]], pnts[v[q+1]]-pnts[v[q+2]])<=0){
            q++; // 弯曲方向不对，出栈
        }
        v[p++] = i;
        v[q--] = i;
    }
    vector<v2d> res;
    for(int i=q+1;i<p-1;i++) {
        res.push_back(pnts[v[i]]);
    }
    return res;
}

ll phi(ll n) {
    auto factors = factorize(n);
    for(auto [p, k] : factors) {
        n = n / p * (p-1);
    }
    return n;
}

vector<pair<ll, int>> factorize(ll n) {
    vector<pair<ll, int>> result;
    while(n!=1) {
        ll p = min_divisor(n);
        int c = 0;
        do {
            n/=p;
            ++c;
        } while(n%p==0);
        result.emplace_back(make_pair(p, c));
    }
    return result;
}

DIR=$(cd $(dirname $0);pwd)

typedef long long ll;

struct Node {
    ll sum;
    int i;
};

// 求非负整数数组nums的第k小子序列和，k=0,1,2,...,2^n-1
// 算法复杂度是O(nlogn)+O(klogk), n=nums.size()
// 所以n和k的规模都是受限的，一般不能超过10^5
ll kMinSumBase(const vector<int>& nums, int k) {
    vector<int> arr = nums;
    sort(arr.begin(), arr.end());
    auto cmp = [&](const Node& a, const Node& b) {
        return a.sum > b.sum;
    };
    priority_queue<Node, vector<Node>, decltype(cmp)> PQ(cmp);
    PQ.push(Node{arr[0], 0});
    PQ.push(Node{0, -1}); // 特殊处理空子段
    ll result = 0;
    for(int i=0;i<k && !PQ.empty();i++) {
        auto node = PQ.top(); PQ.pop();
        if(node.i != -1 && node.i+1 < arr.size()) {
            PQ.push(Node{node.sum+arr[node.i+1], node.i+1});
            PQ.push(Node{node.sum+arr[node.i+1]-arr[node.i], node.i+1});
        }
    }
    assert(!PQ.empty());
    auto node = PQ.top(); PQ.pop();
    return node.sum;
}

// 求数组nums（允许有负数）的第k小子序列和，k=0,1,2,...,2^n-1
// n和k的规模都是受限的，一般不能超过10^5
ll kMinSum(const vector<int>& nums, int k) {
    ll min_sum = 0;
    vector<int> arr(nums.size());
    for(int i=0;i<nums.size();i++) {
        if(nums[i] < 0) {
            min_sum += nums[i];
        }
        arr[i] = abs(nums[i]);
    }
    return min_sum + kMinSumBase(arr, k);
}

// 求数组nums（允许有负数）的第k大子序列和，k=0,1,2,...,2^n-1
// n和k的规模都是受限的，一般不能超过10^5
ll kMaxSum(const vector<int>& nums, int k) {
    ll max_sum = 0;
    vector<int> arr(nums.size());
    for(int i=0;i<nums.size();i++) {
        if(nums[i] > 0) {
            max_sum += nums[i];
        }
        arr[i] = abs(nums[i]);
    }
    return max_sum - kMinSumBase(arr, k);
}

//思想a^13=a^(1+4+8)=a^1*a^4*a^8
int modExp(int a,int b,int m) {
	int t=1,y=a%m;
	while(b){
		if(b&1){
			t=t*y%m;
		}
		y=y*y%m;
		b=(b>>1);
	}
	return t;
}

int r = 0;
for(int i=0;i<a.size();i++) {
	r  = r * 10 + (a[i]-'0');
}

int str2int(const string& a, int m) {
    int r = 0;
    for(int i=0;i<a.size();i++) {
        r  = (r * 10 + (a[i]-'0')) % m;
    }
    return r;
}

int modExp(const string& a, int b, int m) {
    return modExp(str2int(a, m), b, m);
}

int modExp(int a,int b,int m) {
    int t=1,y=a%m;
    while(b){
        if(b&1){
            t=t*y%m;
        }
        y=y*y%m;
        b=(b>>1);
    }
    return t;
}

int str2int(const string& a, int m) {
    int r = 0;
    for(int i=0;i<a.size();i++) {
        r  = (r * 10 + (a[i]-'0')) % m;
    }
    return r;
}

int modExp(const string& a, const string& b, int m) {
    int r = 1;
    int a10k = str2int(a, m);
    for(int i=b.size()-1;i>=0;i--) {
        r = r * modExp(a10k, b[i]-'0', m) % m;
        a10k = modExp(a10k, 10, m);
    }
    return r;
}

ll modMul(ll a,ll b,ll m) {
    ll t=0;
    a=(a%m+m)%m;
    b=(b%m+m)%m;
    while(b){
        if(b&1){
            t=(t+a)%m;
        }
        a=(a+a)%m;
        b>>=1;
    }
    return t;
}

ll modExp(ll a,ll b,ll m) {
    ll t=1,y=a%m;
    while(b){
        if(b&1){
            t=modMul(t,y,m);
        }
        y=modMul(y,y,m);
        b=(b>>1);
    }
    return t;
}

template<typename R, typename T>
R sstream_cast(const T& o) {
    stringstream ss;
    ss << o;
    R result;
    ss >> result;
    return result;
}

// 排列数 n!/(n-k)!
int P(int n,int k)
{
        if(k>n)return 0;
        int res = 1;
        for(int i=n-k+1; i<=n; i++){
            res *= i;
        }
        return res;
}

// 返回小于n的各个数位不同的整数的个数
int countDistinctDigitsNumbers(int n) {
    string s = sstream_cast<string>(n);
    int len = s.size();
    // 分类考虑：
    // 1. 所有位数不足len的数满足条件
    // 2. 首位为 1 ~ s[0]-1 的情况，s[1:len]任意都满足条件
    // 3. 首位为 s[0]，二位为 0 ~ s[1]-1 的情况(但前缀用掉的digit不能再用)，s[2:len]任意都满足条件
    //    ...
    //    前缀为 s[0:i]，第i位为 0 ~ s[i]-1 的情况(但前缀用掉的digit不能再用)，s[i+1:len]任意都满足条件
    //    ...
    //    前缀为 s[0:len-1]，第len-1位为 0 ~s[len-1]-1 的情况(但前缀用掉的digit不能再用)，空后缀

    int result = 0;
    // 第1类：统计任意i位数的个数
    for(int i=1;i<len;i++) {
        result += 9 * P(9, i-1);
    }
    // 第2类
    result += (s[0]-'0'-1) * P(9, len-1);
    // 第3类
    bool used[10] = {0};
    used[s[0]-'0'] = true;
    for(int i=1;i<len;i++) {
        int cnt = 0;
        // 对于cnt的循环计数可以优化，但无必要
        for(int k=0;k<s[i]-'0';k++) {
            if(!used[k]) {
                cnt++;
            }
        }
        result += cnt * P(9-i, len-1-i);

        // 如果s前缀本身用到了重复数字，直接跳出，终止第3类的计算
        if(used[s[i]-'0']) break;
        else used[s[i]-'0'] = true;
    }
    return result;
}