Skip to content

Latest commit

 

History

History
595 lines (528 loc) · 11.5 KB

2-数据结构.md

File metadata and controls

595 lines (528 loc) · 11.5 KB
Raw

2-数据结构

树状数组

class BIT
{
    int n = 2e6;
    long long *a;

  public:
    BIT(int size) : n(size)
    {
        a = new long long[size + 10];
    }
    void update(int p, long long x)
    {
        while (p <= n)
            a[p] += x, p += (p & (-p));
    }

    long long query(int l, int r)
    {
        long long ret = 0;
        l--;
        while (r > 0)
            ret += a[r], r -= (r & (-r));
        while (l > 0)
            ret -= a[l], l -= (l & (-l));
        return ret;
    }
};

template<typename T>
struct Fenwick{
    int n;
    vector<T> tr;
 
    Fenwick(int n) : n(n), tr(n + 1, 0){}
 
    int lowbit(int x){
        return x & -x;
    }
 
    void modify(int x, T c){//单点添加
        for(int i = x; i <= n; i += lowbit(i)) tr[i] += c;
    }
 
    void modify(int l, int r, T c){//区间添加
        modify(l, c);
        if (r + 1 <= n) modify(r + 1, -c);
    }
 
    T query(int x){
        T res = T();
        for(int i = x; i; i -= lowbit(i)) res += tr[i];
        return res;
    }
 
    T query(int l, int r){
        return query(r) - query(l - 1);
    }
 
    int find_first(T sum){//和出现的第一位置
        int ans = 0; T val = 0;
        for(int i = __lg(n); i >= 0; i--){
            if ((ans | (1 << i)) <= n && val + tr[ans | (1 << i)] < sum){
                ans |= 1 << i;
                val += tr[ans];
            }
        }
        return ans + 1;
    }
 
    int find_last(T sum){
        int ans = 0; T val = 0;
        for(int i = __lg(n); i >= 0; i--){
            if ((ans | (1 << i)) <= n && val + tr[ans | (1 << i)] <= sum){
                ans |= 1 << i;
                val += tr[ans];
            }
        }
        return ans;
    }
 
};
using BIT = Fenwick<int>;

并查集

带有路径压缩的并查集

struct DSU
{
    vector<int> f;

    DSU() {}
    DSU(int n)
    {
        clear(n);
    }

    // 多测时只构造一次 清空T次
    void clear(int n)
    {
        f.resize(n);
        iota(f.begin(), f.end(), 0);
    }

    int find(int x)
    {
        return f[x] == x ? x : (f[x] = find(f[x]));
    }

    bool same(int x, int y)
    {
        return find(x) == find(y);
    }

    bool merge(int x, int y)
    {
        x = find(x);
        y = find(y);
        return (x == y) ? false : f[y] = x;
    }
};

带权并查集

struct DSU
{
    vector<int> f, siz;

    DSU() {}
    DSU(int n)
    {
        clear(n);
    }

    void clear(int n)
    {
        f.resize(n);
        iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
    }

    int find(int x)
    {
        return f[x] == x ? x : (f[x] = find(f[x]));
    }

    bool same(int x, int y)
    {
        return find(x) == find(y);
    }

    bool merge(int x, int y)
    {
        x = find(x);
        y = find(y);
        if (x == y)
            return false;
        // if (siz[x] < siz[y])
        //     swap(x, y);
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }

    int size(int x)
    {
        return siz[find(x)];
    }
};

ST表

// log2(x) 的预处理
// 1. 递推
lg[2] = 1;
for (int i = 3; i < N; i++)
    lg[i] = lg[i / 2] + 1;
// 2. 基于编译期计算
using std::array;
// WARNING: LOG_SIZE may cause CE if too big.
const int LOG_SIZE = 1e5 + 10;
constexpr array<int, LOG_SIZE> LOG = []() {
    array<int, LOG_SIZE> l{0, 0, 1};
    for (int i = 3; i < LOG_SIZE; i++)
        l[i] = l[i / 2] + 1;
    return l;
}();
// 3. 直接计算
int lg(int x)
{
    return 31 - __builtin_clz(x);
}
// STL 提供了 std::lg(), 底数是e.
class SparseTable
{
  private:
    // SIZE depends on range of f[i][0].
    // 22 is suitable for 1e5.
    static const int SIZE = 22;
    // f[i][j] maintains the result from i to i + 2 ^ j - 1;
    int (*f)[SIZE];
    using func = std::function<int(int, int)>;
    func op;
    // length of f from 1 to l;
    int l;

  public:
    SparseTable(int a[][SIZE], func foo, int len) : f(a), op(foo), l(len)
    {
        for (int j = 1; j < SIZE; j++)
            for (int i = 1; i + (1 << j) - 1 <= len; i++)
                // f[i][j] comes from f[i][j - 1].
                // f[i][j - 1], f[i + 2^(j - 1)] cover the range of f[i][j].
                f[i][j] = foo(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
    };
    int query(int x, int y)
    {
        int s = LOG[y - x + 1];
        return op(f[x][s], f[y - (1 << s) + 1][s]);
    }
};

带懒标记线段树

const int N = 1e6;
int a[N];
int tag[4 * N];
int tree[4 * N];
int n;
void push_up(int p)
{
    tree[p] = tree[ls(p)] + tree[rs(p)];
}
void build(int p, int l, int r)
{
    if (l == r)
    {
        tree[p] = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(ls(p), l, mid);
    build(rs(p), mid + 1, r);
    push_up(p);
}
void push_down(int p, int l, int r)
{
    int mid = (l + r) >> 1;
    tag[ls(p)] += tag[p];
    tag[rs(p)] += tag[p];
    tree[ls(p)] += tag[p] * (mid - l + 1);
    tree[rs(p)] += tag[p] * (r - mid);
    tag[p] = 0;
}
void update(int nl, int nr, int k, int p = 1, int l = 1, int r = n)
{
    if (nl <= l && r <= nr)
    {
        tag[p] += k;
        tree[p] += k * (r - l + 1);
        return;
    }
    push_down(p, l, r);
    int mid = (l + r) >> 1;
    if (nl <= mid)
        update(nl, nr, k, ls(p), l, mid);
    if (nr > mid)
        update(nl, nr, k, rs(p), mid + 1, r);
    push_up(p);
}
int query(int x, int y, int l = 1, int r = n, int p = 1)
{
    int res = 0;
    if (x <= l && y >= r)
        return tree[p];
    int mid = (l + r) >> 1;
    push_down(p, l, r);
    if (x <= mid)
        res += query(x, y, l, mid, ls(p));
    if (y > mid)
        res += query(x, y, mid + 1, r, rs(p));
    return res;
}
int main()
{
    int q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    build(1, 1, n);
    while (q--)
    {
        int op, x, y, k;
        cin >> op;
        if (op == 1)
        {
            cin >> x >> y >> k;
            update(x, y, k);
        }
        else
        {
            cin >> x >> y;
            cout << query(x, y) << endl;
        }
    }
    return 0;
}

线段树上二分

eg. 两种操作，1. 修改ai为d 2. 查询l,r中第一次出现大于等于d位置，否则返回-1

维护区间最大值，

对一个区间判断最大值是否大于等于d

存在则先找左区间，再找右区间

区间最值线段树

struct node
{
    int maxn;
} tree[800005];
int n;
int tag[800005];
void push_down(int p, int l, int r)
{ // 标记下压
    int mid = (r + l) / 2;
    tree[2 * p].maxn += tag[p];
    tree[2 * p + 1].maxn += tag[p];
    tag[2 * p] += tag[p];
    tag[2 * p + 1] += tag[p];
    tag[p] = 0;
}
void update(int l, int r, int k, int cl = 1, int cr = n, int p = 1)
{ // 更新
    if (cl > r || cr < l)
    {
        return;
    }
    if (cl >= l && cr <= r)
    {
        tree[p].maxn += k;
        if (cl < cr)
        {
            tag[p] += k;
        }
    }
    else
    {
        int mid = (cl + cr) >> 1;
        push_down(p, cl, cr);
        if (l <= mid)
            update(l, r, k, cl, mid, 2 * p);
        if (r > mid)
            update(l, r, k, mid + 1, cr, 2 * p + 1);
        tree[p].maxn = max(tree[p << 1].maxn, tree[p * 2 + 1].maxn);
    }
}
int query(int l, int r, int cl = 1, int cr = n, int p = 1)
{ // 查询
    if (cl >= l && cr <= r)
    {
        return tree[p].maxn;
    }
    else
    {
        int mid = (cl + cr) >> 1;
        push_down(p, cl, cr);
        int tmp = 0;
        if (l <= mid)
            tmp = max(tmp, query(l, r, cl, mid, 2 * p));
        if (r > mid)
            tmp = max(tmp, query(l, r, mid + 1, cr, 2 * p + 1));
        return tmp;
    }
}

单调栈

满足栈中元素单调递增或递减的栈

可用于o(n)寻找每个数之后第一个大于他的数的位置（用单调递减栈）

可解决求 $max_{1\leq l\leq n,l\leq r \leq n}((r-l+1)*min_{l\leq i \leq r}a[i])$

即区间长度乘区间最值结果的最值

int n,m;//洛谷P5788
stack<int>st;
int a[3000005],ans[3000005];
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++){
        while(st.size()&&a[i]>a[st.top()]){//维护递减栈
            ans[st.top()] = i;//更新答案
            st.pop();
        }
        st.push(i);
    }
    for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
    cout<<endl;
}

单调队列

p[head]表示序号 p[head]!=head

int p[N];
int head=1,tail=0;
for(int i=1;i<=n;i++){
	if(head<=tail&&p[head]==i-k){//当前0			区间长度大于k时扔掉头部
		head++;
	}
	while(head<=tail&&a[p[tail]]<=a[i]) tail--;//此时求最大值
	p[++tail]=i;
	//则head记录区间内最值
}

可持久化线段树

struct node
{
    int l, r;
    ll v;
} tr[N];
ll a[N];
int tot;

int clone(int x)
{
    tr[++tot] = tr[x];
    return tot;
}

int push_up(int p)
{
    tr[p].v = tr[tr[p].l].v + tr[tr[p].r].v;
    return p;
}

int build(int l, int r)
{
    int x = ++tot;
    if (l == r)
    {
        tr[x].v = a[l];
        return x;
    }
    int mid = (l + r) / 2;
    tr[x].l = build(l, mid);
    tr[x].r = build(mid + 1, r);

    return push_up(x);
}

int update(int pos, int l, int r, int x, int p)
{
    int np = clone(p);
    if (l == r)
    {
        tr[np].v = x;
        return np;
    }
    int mid = (l + r) / 2;
    if (pos <= mid)
        tr[np].l = update(pos, l, mid, x, tr[np].l);
    else
        tr[np].r = update(pos, mid + 1, r, x, tr[np].r);
    return push_up(np);
}

ll query(int l, int r, int x, int y, int p)
{
    if (l >= x && r <= y)
        return tr[p].v;
    int mid = (l + r) / 2;
    if (y <= mid)
        return query(l, mid, x, y, tr[p].l);
    else if (x > mid)
        return query(mid + 1, r, x, y, tr[p].r);
    return query(l, mid, x, mid, tr[p].l) + query(mid + 1, r, mid + 1, y, tr[p].r);
}

可持久化线段树-区间第k大

struct pree_kth
{
    int tot = 0;
    int size;
    vector<node> tr;
    vector<int> his;
    map<int, int> to, back;
    int clone(int x)
    {
        tr[++tot] = tr[x];
        return tot;
    }

    int push_up(int p)
    {
        tr[p].v = tr[tr[p].l].v + tr[tr[p].r].v;
        return p;
    }

    pree_kth(vector<int> &a, int n) : his(n + 1), tr(n << 5), size(n)
    {
        map<int, int> mp;
        int cnt = 0;
        for (int i = 1; i <= n; i++)
            mp[a[i]]++;
        for (auto [k, v] : mp)
            to[k] = ++cnt, back[cnt] = k;
        his[0] = build(1, n);
        for (int i = 1; i <= n; i++)
            his[i] = update(to[a[i]], 1, n, his[i - 1]);
    }

    int build(int l, int r)
    {
        int x = ++tot;
        if (l == r)
        {
            tr[x].v = 0;
            return x;
        }
        int mid = (l + r) / 2;
        tr[x].l = build(l, mid);
        tr[x].r = build(mid + 1, r);

        return push_up(x);
    }

    int update(int pos, int l, int r, int p)
    {
        int np = clone(p);
        if (l == r)
        {
            tr[np].v++;
            return np;
        }
        int mid = (l + r) / 2;
        if (pos <= mid)
            tr[np].l = update(pos, l, mid, tr[np].l);
        else
            tr[np].r = update(pos, mid + 1, r, tr[np].r);
        return push_up(np);
    }

    int _get(int u, int v, int l, int r, int k)
    {
        if (l == r)
            return l;
        int x = tr[tr[v].l].v - tr[tr[u].l].v;
        int mid = (l + r) / 2;
        if (x >= k)
            return _get(tr[u].l, tr[v].l, l, mid, k);
        else
            return _get(tr[u].r, tr[v].r, mid + 1, r, k - x);
    }

    int kth(int l, int r, int k)
    {
        return back[_get(his[l - 1], his[r], 1, size, k)];
    }
};