线段树大根堆模版二合一-白红宇

线段树大根堆模版二合一

阅读量：5875 次

发布时间：2019-06-19

本文共 3438 字，大约阅读时间需要 11 分钟。

#include "stdafx.h"#include 
     
      #include 
      
       #include 
       
        #define N 2000001using namespace std;inline void read_int(int &now_);class T_heap {private:    int heap[N], num;public:    void up(int now)    {        if (now <= 1) return;        if (heap[now] > heap[now >> 1])        {            swap(heap[now], heap[now >> 1]);            up(now >> 1);        }    }    void down(int now)    {        int next = now;        if ((now << 1) <= num)        {            if (heap[now << 1] > heap[next])            {                next = now << 1;            }        }        if ((now << 1 | 1) <= num)        {            if (heap[now << 1 | 1] > heap[next])            {                next = now << 1 | 1;            }        }        if (now != next)        {            swap(heap[next], heap[now]);            down(next);        }    }    void push(int x)    {        heap[++num] = x;        up(num);    }    void pop()    {        heap[1] = heap[num--];        down(1);    }    int top()    {        return heap[1];    }};class T_tree {public:    int l, r, dis, flag, mid;    void mid_()    {        mid = (l + r) >> 1;    }    void dis_()    {        read_int(dis);    }    void flag_()    {        flag = 0;    }};class T_tree tree[N * 4];int n,if_z;char Cget;inline void read_int(int &now_){    now_ = 0,if_z=1, Cget = getchar();    while (Cget<'0' || Cget>'9')    {        if (Cget == '-') if_z = -1;        Cget = getchar();    }    while (Cget >= '0'&&Cget <= '9')    {        now_ = now_ * 10 + Cget - '0';        Cget = getchar();    }    now_ *= if_z;}inline void tree_up(int now){    tree[now].dis = tree[now << 1].dis + tree[now << 1 | 1].dis;}inline void tree_down(int now){    if (tree[now].l == tree[now].r) return;    tree[now << 1].flag += tree[now].flag;    tree[now << 1].dis += tree[now].flag*(tree[now << 1].r - tree[now << 1].l + 1);    tree[now << 1 | 1].flag += tree[now].flag;    tree[now << 1 | 1].dis += tree[now].flag*(tree[now << 1 | 1].r - tree[now << 1 | 1].l + 1);    tree[now].flag_();}void tree_build(int now, int l, int r){    tree[now].l = l, tree[now].r = r;    if (l == r)    {        tree[now].dis_();        return;    }    tree[now].mid_();    tree_build(now << 1, l, tree[now].mid);    tree_build(now << 1 | 1, tree[now].mid + 1, r);    tree_up(now);}void tree_change(int now, int l, int r, int to){    if (tree[now].l == l&&tree[now].r == r)    {        tree[now].dis += (tree[now].r - tree[now].l + 1)*to;        tree[now].flag += to;        return ;    }    if (tree[now].flag) tree_down(now);    if (l > tree[now].mid) tree_change(now << 1 | 1, l, r, to);    else if (r <= tree[now].mid) tree_change(now << 1, l, r, to);    else    {        tree_change(now << 1, l, tree[now].mid, to);        tree_change(now << 1 | 1, tree[now].mid + 1, r, to);    }    tree_up(now);}int tree_query(int now, int l, int r){    if (tree[now].l == l&&tree[now].r == r)    {        return tree[now].dis;    }    if (tree[now].flag) tree_down(now);    int return_=0;    if (l > tree[now].mid) return_ = tree_query(now << 1 | 1, l, r);    else if (r <= tree[now].mid) return_ = tree_query(now << 1, l, r);    else    {        return_ += tree_query(now << 1, l, tree[now].mid);        return_ += tree_query(now << 1 | 1, tree[now].mid + 1, r);    }    tree_up(now);    return return_;}int main(){        return 0;}