魔のkyo的BLOG

template <class T, class Container = vector<T>, class Compare = less<typename Container::value_type> >
class priority_queue;

#include <queue>
#include <vector>
using namespace std;

struct Student { // 学生
    int id; // 学号
    int height; // 身高
};

int main()
{
    // 定义比较器
    struct Cmp {
        bool operator() (const Node& a, const Node& b) {
            return a.height < b.height;
        }
    };
    // 定义优先队列
    priority_queue<Student, vector<Student>, Cmp> PQ;
}

vector<Student> students = {...};
std::sort(students.begin(), students.end(), [](const Student& a, const Student& b){
	return a.height < b.height;
});

// 等价的
std::sort(students.begin(), students.end(), Cmp());

explicit priority_queue (const Compare& comp = Compare(), Container&& ctnr = Container());

priority_queue<Node> PQ([](const Node& a, const Node& b) {
    return a.height < b.height;
});

// 通过lambda表达式定义序
auto cmp = [](const Node& a, const Node& b) {
    return a.height < b.height;
};
priority_queue<Node, vector<Node>, decltype(cmp)> PQ(cmp);

vector<Student> students = {...};
unordered_map<int, Student> id2stu;
for(auto& stu: students) {
	id2stu[stu.id] = stu;
}

// 我们可以很方便地把id2stu绑定到lambda表达式中用来排序
auto cmp = [&](int a, int b) {
    return id2stu[a].height < id2stu[b].height;
};
priority_queue<int, vector<int>, decltype(cmp)> PQ(cmp);

vector<Student> students = {...};
unordered_map<int, Student> id2stu;
for(auto& stu: students) {
	id2stu[stu.id] = stu;
}

struct Cmp {
    const unordered_map<int, Student>& id2stu;
	Cmp(const unordered_map<int, Student>& id2stu) : id2stu(id2stu) {}
    bool operator() (int a, int b) const {
	    return id2stu[a].height < id2stu[b].height;
    }
};
priority_queue<int, vector<int>, Cmp> PQ;

int find(const string& s, const string& p) {
    for(int i=0;i<=s.size()-p.size();i++) {
        int j=0; // 每次j都从0开始
        for(;j<p.size();j++) {
            if(s[i+j] != p[j]) break;
        }
        if(j == p.size())return i;
        // 如果当前以i开始的字串不匹配，则从i+1继续尝试
    }
    return -1;
}

// 计算next数组，即j不匹配时的回退位置
vector<int> compute_next(const string& p){
    vector<int> next(p.size(), 0);
    for(int i=2; i<p.size(); i++){
        int j = next[i-1];
        while(p[i-1] != p[j] && j>0)
            j = next[j];
        if(p[i-1]==p[j])
            next[i] = j+1;
        else
            next[i] = 0;
    }
    return move(next);
}

//串匹配的KMP算法
//返回s中第一个与p匹配的子串的起始下标，若找不到则返回-1
int find(const string& s, const string& p, const vector<int>* pnext=NULL) {
    vector<int> _next;
    if(pnext == NULL) {
        _next = compute_next(p);
        pnext = &_next;
    }
    const vector<int>& next(*pnext);
    int i = 0, j = 0;
    while(s[i] && p[j]){
        if(s[i] == p[j]){
            ++i;
            ++j;
        }
        else {
            if(j==0) ++i; // 第一个字符就不匹配，直接后移i
            else if(p[j]==0) break; // p[j] 表示找到了匹配，跳出循环
            else j = next[j]; // 这里就是利用预处理好的next来回退j，而i不用变
        }
    }
    if(p[j]==0) return i-j;
    else return -1;
}

template<typename T, int MAX_SIZE>
class CircularArray {
    T data[MAX_SIZE];
public:
    CircularArray(const T& t=T()) {fill(data, data+MAX_SIZE, t);}
    T& operator [] (int i) {
        return data[(i%MAX_SIZE+MAX_SIZE)%MAX_SIZE];
    }
};

template<typename T, int MAX_SIZE>
class Queue {
    CircularArray<T, MAX_SIZE> data;
    int begin = 0;
    int end = 0;
public:
    void push(const T& t) {
        assert(!full());
        data[end++] = t;
    }

    T pop() {
        assert(!empty());
        return data[begin++];
    }

    T& peek() {
        assert(!empty());
        return data[begin];
    }

    const T& peek() const {
        return const_cast<Queue*>(this)->peek();
    }

    bool empty() const {
        return end == begin;
    }

    size_t size() const {
        return end-begin;
    }

    bool full() const {
        return size() == MAX_SIZE;
    }
};

// 得到n二进制最右侧的1表示的数
int lowbit(int n) {
    return n & (-n);
}

// 查询前缀和
int query(int i) {
    int result = 0;
    while(i) {
        result += bitree[i];
        i -= lowbit(i); // 等价的 i &= i-1 
    }
    return result;
}

// 修改元素i的值
void add(int i, int x) {
    ++i;
    while(i<=8) {
        bitree[i] += x;
        i += lowbit(i);
    }
}

add(i, -query(i,i+1)); // 减去旧值
add(i, x); // 加上新值

template <typename T, int N=(1<<17)>
class BITree{
    T C[N+1];
    int lowbit(int i){return i&(-i);}
public:
    BITree(){clear();}

    void clear(){memset(C,0,sizeof(C));}

    // 增量修改元素i的值
    void add(int i, T d){
        for(i++; i<=N; i+=lowbit(i)) C[i]+=d;
    }
    
    // [0, i)元素的和
    T sum(int i){
        T r=0;
        for(; i; i-=lowbit(i)) r+=C[i];
        return r;
    }

    // [b, e)元素的和
    T sum(int b, int e) {
        return sum(e) - sum(b);
    }

    // 修改元素i的值
    void set(int i, T d) {
        add(i, -sum(i, i+1));
        add(i, d);
    }
};

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

namespace detail {

template<typename KT, typename PT>
struct TreeNode {
    KT key;
    PT priority;
    int size;
    TreeNode* left;
    TreeNode* right;

    TreeNode(const KT& key, const PT& priority):key(key),priority(priority),size(1),left(NULL),right(NULL){}
};

template<typename KT, typename PT>
class TreeNodePool {
    int batchsize = 1024;
    vector<char*> memchunks;
    queue<char*> blocks;
public:
    ~TreeNodePool() {
        for(int i=0;i<memchunks.size();i++) {
            free(memchunks[i]);
        }
    }

    TreeNode<KT, PT>* create(const KT& key, const PT& priority) {
        if(blocks.empty()) {
            char* p = (char*)malloc(sizeof(TreeNode<KT, PT>)*batchsize);
            memchunks.emplace_back(p);
            for(int i=0;i<batchsize;i++) {
                blocks.push(p+sizeof(TreeNode<KT, PT>)*i);
            }
            batchsize *= 2;
        }
        char* p = blocks.front(); blocks.pop();
        return new (p)TreeNode<KT, PT>(key, priority);
    }

    void release(TreeNode<KT, PT>* p) {
        blocks.push((char*)p);
    }
};
} // namespace detail

template<typename KT, typename PT, typename CMPF=less<PT> >
class Heap {
public:
    // 插入或更新key对应的priority
    void upsert(const KT& key, const PT& priority) {
        erase(key);
        insert(key, priority);
    }
    // 查看堆顶key
    const KT& peek() const {
        return root->key;
    }
    KT& peek() {
        return root->key;
    }
    // 取出堆顶key
    KT pop() {
        KT result = peek();
        erase(result);
        return result;
    }

    bool empty() const {
        return size() == 0;
    }

    int size() const {
        return _size(root);
    }

private:
    int insert(const KT& key, const PT& priority) {
        return _insert(root, create_tree_node(key, priority));
    }

    void erase(const KT& key) {
        _erase(root, key);
    }

private:
    detail::TreeNode<KT, PT>* create_tree_node(const KT& key, const PT& priority) {
        return pool.create(key, priority);
    }
    
    void release_tree_node(detail::TreeNode<KT,PT>* root) {
        pool.release(root);
    }

    static int _size(detail::TreeNode<KT,PT>* root) {
        return (root != NULL ? root->size : 0);
    }

    // 返回root子树的size减去左右子树的size
    static int _count(detail::TreeNode<KT,PT>* root) {
        if(root == NULL) return 0;
        return _size(root) - _size(root->left) - _size(root->right);
    }

    static void lrotate(detail::TreeNode<KT,PT>* &root) {
        auto right = root->right;
        auto rightleft = right->left;
        root->right = rightleft;
        right->left = root;
        int root_size = root->size;
        root->size += _size(rightleft) - _size(right);
        right->size = root_size;
        root = right;
    }

    static void rrotate(detail::TreeNode<KT,PT>* &root) {
        auto left = root->left;
        auto leftright = left->right;
        root->left = leftright;
        left->right = root;
        int root_size = root->size;
        root->size += _size(leftright) - _size(left);
        left->size = root_size;
        root = left;   
    }

    int _insert(detail::TreeNode<KT,PT>* &root, detail::TreeNode<KT,PT>* p) {
        if(root == NULL) {
            root = p;
            return 1;
        } else {
            if(p->key < root->key) {
                int r = _insert(root->left, p);
                root->size += r;
                if(CMPF()(root->priority, root->left->priority)){
                    rrotate(root);
                }
                return r;
            } else if(root->key < p->key) {
                int r = _insert(root->right, p);
                root->size += r;
                if(CMPF()(root->priority, root->right->priority)){
                    lrotate(root);
                }
                return r;
            } else {
                root->size += 1;
                release_tree_node(p);
                return 1;
            }
        }
    }

    static int _count(detail::TreeNode<KT,PT>* root, const KT& key) {
        if(root == NULL) return 0;
        if(key < root->key) return _count(root->left, key);
        else if(root->key < key) return _count(root->right, key);
        else return _count(root);
    }

    int _erase(detail::TreeNode<KT,PT>* &root, const KT& key) {
        if(root == NULL) return 0;
        if(key == root->key) {
            auto left = root->left;
            auto right = root->right;
            if(left == NULL) {
                int root_count = _count(root);
                release_tree_node(root);
                root = right;
                return root_count;
            } else if(right == NULL) {
                int root_count = _count(root);
                release_tree_node(root);
                root = left;
                return root_count;
            } else {
                int root_count = _count(root);
                int r = 0;
                if(CMPF()(left->priority, right->priority)) {
                    lrotate(root); // 把优先级大的孩子转成根
                    r = _erase(root->left, key);
                } else {
                    rrotate(root);
                    r = _erase(root->right, key);
                }
                root->size -= r;
                return r;
            }
        } else if(key < root->key) {
            int r = _erase(root->left, key);
            root->size -= r;
            return r;
        } else {
            int r = _erase(root->right, key);
            root->size -= r;
            return r;
        }
    }

private:
    detail::TreeNodePool<KT, PT> pool;
    detail::TreeNode<KT, PT>* root = NULL;
};

#include <iostream>
using namespace std;

#define MAXN 8
int bg[MAXN*2]; // 区间左端点，闭
int nd[MAXN*2]; // 区间右端点，开
int sm[MAXN*2]; // 节点值，即区间和

// 递归构建树
void build(int k, int b, int e) {
    bg[k] = b;
    nd[k] = e;
    sm[k] = 0;
    if(e-b>1) {
        int mid = b + (e-b) / 2;
        build(k*2+1, b, mid);
        build(k*2+2, mid, e);
    }
}

// 设置数组下标i的元素值，类似arr[i] = val
void change(int k, int i, int val) {
    if(nd[k]-bg[k]==1) { // 叶子节点
        sm[k] = val; // 直接更新
    } else {
        int mid = bg[k] + (nd[k]-bg[k]) / 2;
        // 递归向下更新
        if(i<mid) change(k*2+1, i, val);
        else change(k*2+2, i, val);
        // 回溯时通过孩子的值更新当前节点值
        sm[k] = sm[k*2+1] + sm[k*2+2];
    }
}

// 查询[b, e)的元素和
int query(int k, int b, int e) {
    if(b<=bg[k] && nd[k]<=e) {
        cout << "DEBUG:[" << bg[k] << "," << nd[k] << ") sm[k]=" << sm[k] << endl;
        return sm[k];
    }
    int mid = bg[k] + (nd[k]-bg[k]) / 2;
    return (b<mid ?query(k*2+1, b, e):0) + (mid<e ? query(k*2+2, b, e):0);
}

// 把n向上对齐到2的幂
int align(int n) {
    if(n & (n-1)) {
        while(n & (n-1)) {
            n &= (n-1);
        }
        n = (n << 1);
    }
    return n;
}

int main()
{
    int arr[] = {3,8,3,3,5,6,8,7};
    build(0, 0, align(8));
    for(int i=0;i<8;i++) {
        change(0, i, arr[i]);
    }
    cout << query(0, 2, 7) << endl;
}

typedef long long ll;

class SegTree {
private:
    enum { INF = ll(4.6e18) };

    struct Node {
        Node* left;
        Node* right;
        ll sum;
        ll min;
        ll max;
        ll lazy;
        bool set_not_add;
        Node():left(0), right(0), sum(0), min(0), max(0), lazy(INF), set_not_add(false) {}
    };

    void update(Node* node, int start, int end, int l, int r, bool set_not_add, ll val) {
        if (l <= start && end <= r) {
            if(set_not_add) {
                node->sum = (end - start + 1) * val;
                node->min = val;
                node->max = val;
                node->lazy = val;
            } else {
                node->sum += (end - start + 1) * val;
                node->min += val;
                node->max += val;
                node->lazy = (node->lazy!=INF?node->lazy:0) + val;
            }
            node->set_not_add = set_not_add;
            return;
        }
        int mid = (start + end) >> 1;
        pushDown(node, mid - start + 1, end - mid);
        if (l <= mid) update(node->left, start, mid, l, r, set_not_add, val);
        if (r > mid) update(node->right, mid + 1, end, l, r, set_not_add, val);
        pushUp(node);
    }

    ll sum(Node* node, int start, int end, int l, int r) {
        if (l <= start && end <= r) return node->sum;
        int mid = (start + end) >> 1;
        ll ans = 0;
        pushDown(node, mid - start + 1, end - mid);
        if (l <= mid) ans += sum(node->left, start, mid, l, r);
        if (r > mid) ans += sum(node->right, mid + 1, end, l, r);
        return ans;
    }

    ll min(Node* node, int start, int end, int l, int r) {
        if (l <= start && end <= r) return node->min;
        int mid = (start + end) >> 1;
        ll ans = INF;
        pushDown(node, mid - start + 1, end - mid);
        if (l <= mid) ans = std::min(ans, min(node->left, start, mid, l, r));
        if (r > mid) ans = std::min(ans, min(node->right, mid + 1, end, l, r));
        return ans;
    }

    ll max(Node* node, int start, int end, int l, int r) {
        if (l <= start && end <= r) return node->max;
        int mid = (start + end) >> 1;
        ll ans = -INF;
        pushDown(node, mid - start + 1, end - mid);
        if (l <= mid) ans = std::max(ans, max(node->left, start, mid, l, r));
        if (r > mid) ans = std::max(ans, max(node->right, mid + 1, end, l, r));
        return ans;
    }

    void pushUp(Node* node) {
        node->sum = node->left->sum + node->right->sum;
        node->min = std::min(node->left->min, node->right->min);
        node->max = std::max(node->left->max, node->right->max);
    }

    void pushDown(Node* node, int leftNum, int rightNum) {
        if (node->left == nullptr) node->left = new Node();
        if (node->right == nullptr) node->right = new Node();
        if (node->lazy == INF) return ;
        if(node->set_not_add) {
            node->left->sum = node->lazy * leftNum;
            node->left->min = node->lazy;
            node->left->max = node->lazy;
            node->left->lazy = node->lazy;
            node->right->sum = node->lazy * rightNum;
            node->right->min = node->lazy;
            node->right->max = node->lazy;
            node->right->lazy = node->lazy;
        } else {
            node->left->sum += node->lazy * leftNum;
            node->left->min += node->lazy;
            node->left->max += node->lazy;
            node->left->lazy += node->lazy;
            node->right->sum += node->lazy * rightNum;
            node->right->min += node->lazy;
            node->right->max += node->lazy;
            node->right->lazy += node->lazy;
        }
        node->left->set_not_add = node->set_not_add;
        node->right->set_not_add = node->set_not_add;
        node->lazy = INF;
    }

    void destory(Node* p) {
        if(p == NULL) return;
        auto left = p->left;
        auto right = p->right;
        delete p;
        destory(left);
        destory(right);
    }

public:
    Node* root = NULL;
    int start;
    int end;
    SegTree(int start=0, int end=1e9) : root(new Node()), start(start), end(end) {}
    ~SegTree() { destory(root); }
private:
    class ItemAccessor {
    public:
        ItemAccessor(SegTree& st, int i): st(st), i(i) {}
        ItemAccessor& operator = (ll x) {st.update(st.root, st.start, st.end, i, i, true, x);return *this;}
        ItemAccessor& operator += (ll x) {st.update(st.root, st.start, st.end, i, i, false, x);return *this;}
        ItemAccessor& operator -= (ll x) {st.update(st.root, st.start, st.end, i, i, false, -x);return *this;}
        operator ll() const {return st.min(st.root, st.start, st.end, i, i);}
    private:
        SegTree& st;
        int i;
    };

    class RangeAccessor {
    public:
        RangeAccessor(SegTree& st, int b, int e):st(st), b(b), e(e) {}
        void operator = (ll x) {st.update(st.root, st.start, st.end, b, e-1, true, x);}
        void operator += (ll x) {st.update(st.root, st.start, st.end, b, e-1, false, x);}
        void operator -= (ll x) {st.update(st.root, st.start, st.end, b, e-1, false, -x);}
    private:
        SegTree& st;
        int b;
        int e;
    };

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

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

    ll sum(int l, int r) { return sum(root, start, end, l, r-1); }
    ll min(int l, int r) { return min(root, start, end, l, r-1); }
    ll max(int l, int r) { return max(root, start, end, l, r-1); }
};

vector<set<int>> a(n);

map<int, set<int>> b;

for(int i=0;i<10;i++) {
    b[i].insert(i);  // 在首次访问b[i]时会自动创建一个空的set<int>，所以可以直接调用insert
}

#include <iostream>
#include <cmath>
#include <cassert>
#include <map>
#include <cstring>
#include <vector>
using namespace std;

typedef long long ll;

template<typename T>
T gcd(T a, T b) { while(b) { T r = a%b; a = b; b = r;} return a;}
template<typename T>
T lcm(T a, T b) { return a/gcd(a,b)*b; }

// 打表大小，[0, UPBOUND)查表，[UPBOUND, UPBOUND*UPBOUND)根据表测试，[UPBOUND*UPBOUND, ll_max)米勒罗宾测试
const ll UPBOUND = 5e6;
class CPrime {
public:
    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;
    }

    bool miller_rabin(ll n,ll b) {
        ll m=n-1;
        int j=0;
        while(!(m&1)){
            m>>=1;
            j++;
        }
        ll v=modExp(b,m,n);
        if(v==1 || v==n-1)return 1;
        for(int i=1;i<j;i++){
            v=modMul(v,v,n);
            if(v==n-1)return 1;
        }
        return 0;
    }

    bool _isprime(ll n)
    {
        const int K=10;//Miller_Rabin的偏真正确率为75%， isprime的正确率为1-(1/4)^K
        if(n<2)return 0;
        if(n==2 || n==3)return 1;
        for(int i=0;i<K;i++){
            if(!miller_rabin(n,rand()%(n-2)+2))return 0;
        }
        return 1;
    }

    //pollard_rho分解，给出N的一个非1因数，返回N时为一次没有找到,C为一个[1,N]的随机数 
    ll pollard_rho(ll C, ll N)
    {
        ll I, X, Y, K, D;
        I = 1;
        X = rand() % N;
        Y = X;
        K = 2;
        do{
            I++;
            D = gcd(N + Y - X, N);
            if (D > 1 && D < N) return D;
            if (I == K) Y = X, K *= 2;
            X = (modMul(X, X, N) + N - C) % N;
        }while (Y != X);
        return N;
    }

    //找出N的最小(质)因数
    ll _min_divisor(ll N)
    {
        if (isprime(N)) return N;
        while(1){
            ll T = pollard_rho(rand() % (N - 1) + 1, N);
            if (T < N){
                  ll A, B;
                  A = _min_divisor(T);
                  B = _min_divisor(N / T);
                  return A < B ? A : B;
            }
        }
    }

    int a[UPBOUND];
    int p[UPBOUND];
    int pn = 0;

    //号称线性的筛素数算法，实际性能确实不错 
    //p[]={2,3,5,7,...},pn为小于UPBOUND的素数个数 
    //若i是合数a[i]为i的最小因子，若i是素数a[i]=0 
    void primefilter(){
        int i, j;
        for(i = 2; i < UPBOUND; ++i){
            if(!(a[i])) p[pn++] = i;
            for(j = 0; (j<pn && i*p[j]<UPBOUND && (p[j]<=a[i]||a[i]==0)); ++j) {
                a[i*p[j]] = p[j];
            }
        }
    }
public:
    CPrime(){
        memset(a, 0, sizeof(a));
        memset(p, 0, sizeof(p));
        primefilter();
    }

    bool isprime(ll n){
        if(n<UPBOUND) return (n>0?!a[n]:0);
        int c = min(3500, pn-1); // 3500个足够支持到1e9
        if(n<p[c]*p[c]) {
            for(int i=0; i<c; i++) {
                if(n%p[i]==0) return false;
            }
            return true;
        } else {
            int c = min(1000, pn);
            for(int i=0; i<c; i++) {
                if(n%p[i]==0) return false;
            }
            return _isprime(n);
        }
    }

    // 返回质数表第n个质数，p[0]=2, ..., p[n]<UPBOUND
    int nth_prime(int n) {
        return n<pn?p[n]:-32768;
    }

    // 返回n的最小因子
    ll min_divisor(ll n) {
        if(n<UPBOUND) return a[n]?a[n]:n;
        int c = min(3500, pn-1); // 3500个足够支持到1e9
        if(n<p[c]*p[c]) {
            for(int i=0; i<c; i++) {
                if(n%p[i]==0) return p[i];
            }
            return n;
        } else {
            // miller_rabin 和 pollard_rho 需要较多的运算
            // 如果有一个小因子不妨先找出来
            int c = min(1000, pn);
            for(int i=0; i<c; i++) {
                if(n%p[i]==0) return p[i];
            }
            return _min_divisor(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;
    }

    // 欧拉函数
    ll phi(ll n) {
        auto factors = factorize(n);
        for(auto [p, c] : factors) {
            n = n / p * (p-1);
        }
        return n;
    }
} Prime;