06-数据结构.md

数据结构

树状数组

struct BIT {
    ll c[maxn];
    int n;

    void init(int _n) {
        n = _n;
        for (int i = 1; i <= n; i++) {
            c[i] = 0;
        }
    }
    int lowbit(int x) {
        return x & (-x);
    }
    void update(int i, int v) {
        while (i <= n) {
            c[i] += v;
            i += lowbit(i);
        }
    }
    ll getsum(int i) {
        ll ans = 0;
        while (i) {
            ans += c[i];
            i -= lowbit(i);
        }
        return ans;
    }
};

线段树

/*
区间乘、区间加，维护区间和

线段树题 考虑3个点
- mergeInfo info合并，pushup和query时使用
- Tag.mergeTag tag向下合并，pushdown时使用
- Info.applyTag tag更新info，pushdown时使用
3个点解决则题目解决
*/
const int maxn = 100005;
const int mod = 1e9 + 7;

int a[maxn];

struct Tag {
    ll mul, add;
    void clear() {
        mul = 1;
        add = 0;
    }
    void mergeTag(Tag k) {
        mul = mul * k.mul % mod;
        add = (add * k.mul % mod + k.add) % mod;
    }
};

struct Info {
    ll sum;
    int l, r;
    void applyTag(Tag k) {
        sum = sum * k.mul % mod;
        sum += k.add * (r - l + 1) % mod;
        sum %= mod;
    }
};

struct SegTree {
    Info info[maxn << 2];
    Tag tag[maxn << 2];
    Info mergeInfo(Info x, Info y) {
        if (x.l == 0) return y;
        if (y.l == 0) return x;
        return Info{(x.sum + y.sum) % mod, x.l, y.r};
    }

    void applyTag(int x, Tag k) {
        tag[x].mergeTag(k);
        info[x].applyTag(k);
    }

    void pushup(int x) {
        info[x] = mergeInfo(info[x * 2], info[x * 2 + 1]);
    }

    void pushdown(int x) {
        applyTag(x * 2, tag[x]);
        applyTag(x * 2 + 1, tag[x]);
        tag[x].clear();
    }

    void build(int x, int l, int r) {
        tag[x].clear();
        if (l == r) {
            info[x].sum = a[l];
            info[x].l = info[x].r = l;
        } else {
            int mid = l + r >> 1;
            build(x * 2, l, mid);
            build(x * 2 + 1, mid + 1, r);
            pushup(x);
        }
    }

    void update(int x, int l, int r, int ql, int qr, Tag k) {
        if (ql > r || qr < l) return;
        if (ql <= l && r <= qr) {
            applyTag(x, k);
            return;
        }
        pushdown(x);
        int mid = l + r >> 1;
        update(x * 2, l, mid, ql, qr, k);
        update(x * 2 + 1, mid + 1, r, ql, qr, k);
        pushup(x);
    }

    Info query(int x, int l, int r, int ql, int qr) {
        if (ql > r || qr < l) return Info{0, 0, 0};
        if (ql <= l && r <= qr) {
            return info[x];
        }
        pushdown(x);
        int mid = l + r >> 1;
        return mergeInfo(query(x * 2, l, mid, ql, qr), query(x * 2 + 1, mid + 1, r, ql, qr));
    }
}

主席树

//主席树求静态区间第k小
struct PersistentSegTreeNode {
    int w;
    int ls, rs;
};

struct PersistentSegTree {
    PersistentSegTreeNode info[maxn * 25];
    int tot;

    void init() {
        tot = 0;
    }

    void pushup(int x) {
        int ls = info[x].ls;
        int rs = info[x].rs;
        info[x].w = info[ls].w + info[rs].w;
    }

    int build(int l, int r) {
        int x = ++tot;
        if (l == r) {
            info[x].w = 0;
        } else {
            int mid = l + r >> 1;
            info[x].ls = build(l, mid);
            info[x].rs = build(mid + 1, r);
            pushup(x);
        }
        return x;
    }

    int newNode(int x) {
        ++tot;
        info[tot] = info[x];
        return tot;
    }

    int update(int x, int l, int r, int id, int w) {
        x = newNode(x);
        if (l == r) {
            info[x].w += w;
        } else {
            int mid = l + r >> 1;
            if (id <= mid) {
                info[x].ls = update(info[x].ls, l, mid, id, w);
            } else {
                info[x].rs = update(info[x].rs, mid + 1, r, id, w);
            }
            pushup(x);
        }
        return x;
    }

    int kth(int x, int y, int l, int r, int k) {
        if (l == r) return l;
        int mid = l + r >> 1;
        int lx = info[x].ls, rx = info[x].rs;
        int ly = info[y].ls, ry = info[y].rs;
        int ls = info[ly].w - info[lx].w;
        if (k <= ls) {
            return kth(lx, ly, l, mid, k);
        } else {
            return kth(rx, ry, mid + 1, r, k - ls);
        }
    }
};

SegmentTreeBeats

#include<bits/stdc++.h>
using namespace std;

#define pr pair<int,int>
#define mk(a,b) make_pair(a,b)
#define LL long long
namespace SegmentTreeBeats{
    typedef LL T;
    #define lson l,mid,rt<<1
    #define rson mid+1,r,rt<<1|1

    const T inf=1e9+7;
    const int maxn=5e5+5;
    T sum[maxn<<2],col[maxn<<2],v[maxn<<2];

    template<class cmp,T Inf>
    struct INFO{
        T mv,smv;
        int cnt;
        const static T INF=Inf;
        INFO operator + (const INFO& p)const{
            INFO ans;
            if(cmp()(mv,p.mv)){
                ans.mv=p.mv;
                ans.cnt=p.cnt;
                ans.smv=cmp()(mv,p.smv)?p.smv:mv;
            }else if(cmp()(p.mv,mv)){
                ans.mv=mv;
                ans.cnt=cnt;
                ans.smv=cmp()(smv,p.mv)?p.mv:smv;
            }else{
                ans.mv=mv;
                ans.cnt=cnt+p.cnt;
                ans.smv=cmp()(smv,p.smv)?p.smv:smv;
            }
            return ans;
        }
    };
    INFO<less<T>,-inf>Mx[maxn<<2];
    INFO<greater<T>,inf>Mn[maxn<<2];
    void updata(int rt){
        sum[rt]=sum[rt<<1]+sum[rt<<1|1];
        Mx[rt]=Mx[rt<<1]+Mx[rt<<1|1];
        Mn[rt]=Mn[rt<<1]+Mn[rt<<1|1];
    }
    void build(int l,int r,int rt){
        col[rt]=0;
        if(l==r){
            Mx[rt].mv=Mn[rt].mv=sum[rt]=v[l];
            Mx[rt].cnt=Mn[rt].cnt=1;
            Mx[rt].smv=Mx[rt].INF;
            Mn[rt].smv=Mn[rt].INF;
            return;
        }
        int mid=(l+r)>>1;
        build(lson);
        build(rson);
        updata(rt);
    }
    inline void color(int l,int r,int rt,T val){
        sum[rt]+=val*(r-l+1);
        col[rt]+=val;
        if(Mx[rt].smv!=-inf)Mx[rt].smv+=val;
        if(Mn[rt].smv!=inf)Mn[rt].smv+=val;
        Mx[rt].mv+=val,Mn[rt].mv+=val;
    }
    inline void colorToLess(int rt,T val){
        if(Mx[rt].mv<=val)return;
        sum[rt]+=(val-Mx[rt].mv)*Mx[rt].cnt;
        if(Mn[rt].smv==Mx[rt].mv)Mn[rt].smv=val;
        if(Mn[rt].mv==Mx[rt].mv)Mn[rt].mv=val;
        Mx[rt].mv=val;
    }
    inline void colorToMore(int rt,T val){
        if(Mn[rt].mv>=val)return;
        sum[rt]+=(val-Mn[rt].mv)*Mn[rt].cnt;
        if(Mx[rt].smv==Mn[rt].mv)Mx[rt].smv=val;
        if(Mx[rt].mv==Mn[rt].mv)Mx[rt].mv=val;
        Mn[rt].mv=val;
    }
    inline void pushcol(int l,int r,int rt){
        if(col[rt]){
            int mid=(l+r)>>1;
            color(lson,col[rt]);
            color(rson,col[rt]);
            col[rt]=0;
        }
        colorToLess(rt<<1,Mx[rt].mv);
        colorToLess(rt<<1|1,Mx[rt].mv);
        colorToMore(rt<<1,Mn[rt].mv);
        colorToMore(rt<<1|1,Mn[rt].mv);
    }
    void toLess(int l,int r,int rt,int nl,int nr,T val){
        if(Mx[rt].mv<=val)return;
        if(nl<=l&&nr>=r&&Mx[rt].smv<val){
            colorToLess(rt,val);
            return;
        }
        pushcol(l,r,rt);
        int mid=(l+r)>>1;
        if(nl<=mid)toLess(lson,nl,nr,val);
        if(nr>mid)toLess(rson,nl,nr,val);
        updata(rt);
    }

    void toMore(int l,int r,int rt,int nl,int nr,T val){
        if(Mn[rt].mv>=val)return;
        if(nl<=l&&nr>=r&&Mn[rt].smv>val){
            colorToMore(rt,val);
            return;
        }
        pushcol(l,r,rt);
        int mid=(l+r)>>1;
        if(nl<=mid)toMore(lson,nl,nr,val);
        if(nr>mid)toMore(rson,nl,nr,val);
        updata(rt);
    }
    void modify(int l,int r,int rt,int nl,int nr,T val){
        if(nl<=l&&nr>=r){
            color(l,r,rt,val);
            return ;
        }
        pushcol(l,r,rt);
        int mid=(l+r)>>1;
        if(nl<=mid)modify(lson,nl,nr,val);
        if(nr>mid)modify(rson,nl,nr,val);
        updata(rt);
    }

    T querySum(int l,int r,int rt,int nl,int nr){
        if(nl<=l&&nr>=r)return sum[rt];
        pushcol(l,r,rt);
        int mid=(l+r)>>1;
        T ans=0;
        if(nl<=mid)ans+=querySum(lson,nl,nr);
        if(nr>mid)ans+=querySum(rson,nl,nr);
        return ans;
    }
    T queryMx(int l,int r,int rt,int nl,int nr){
        if(nl<=l&&nr>=r)return Mx[rt].mv;
        pushcol(l,r,rt);
        int mid=(l+r)>>1;
        T ans=Mx->INF;
        if(nl<=mid)ans=max(ans,queryMx(lson,nl,nr));
        if(nr>mid)ans=max(ans,queryMx(rson,nl,nr));
        return ans;
    }
    T queryMn(int l,int r,int rt,int nl,int nr){
        if(nl<=l&&nr>=r)return Mn[rt].mv;
        pushcol(l,r,rt);
        int mid=(l+r)>>1;
        T ans=Mn->INF;
        if(nl<=mid)ans=min(ans,queryMn(lson,nl,nr));
        if(nr>mid)ans=min(ans,queryMn(rson,nl,nr));
        return ans;
    }

    #undef lson
    #undef rson
}
using namespace SegmentTreeBeats;

int main(){
  //  freopen("4695.in","r",stdin);
 //   freopen("4695.out","w",stdout);
    int n,m;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&v[i]);
    build(1,n,1);
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        int ck,l,r,val;
        scanf("%d%d%d",&ck,&l,&r);
        if(ck<=3)scanf("%d",&val);
        if(ck==1)modify(1,n,1,l,r,val);	//区间加
        else if(ck==2)toMore(1,n,1,l,r,val);	//区间取max
        else if(ck==3)toLess(1,n,1,l,r,val);	//区间取min
        else if(ck==4)printf("%lld\n",querySum(1,n,1,l,r));	//查询区间和
        else if(ck==5)printf("%lld\n",queryMx(1,n,1,l,r));	//查询区间max
        else printf("%lld\n",queryMn(1,n,1,l,r));	//查询区间min
    }
}

fhq_Treap

洛谷P3369/P6136 普通平衡树

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 100005;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;

struct TreapNode {
    int ls, rs;
    int w, sz, rnd;
} tr[maxn];
int tot;

int newNode(int w) {
    int p = ++tot;
    tr[p].ls = tr[p].rs = 0;
    tr[p].w = w;
    tr[p].sz = 1;
    tr[p].rnd = rand();
    return p;
}

void pushup(int p) {
    int ls = tr[p].ls, rs = tr[p].rs;
    tr[p].sz = tr[ls].sz + tr[rs].sz + 1;
}

void split(int p, int w, int &x, int &y) {
    if (!p) {
        x = y = 0;
        return;
    }
    if (tr[p].w <= w) {
        x = p;
        split(tr[p].rs, w, tr[p].rs, y);
    } else {
        y = p;
        split(tr[p].ls, w, x, tr[p].ls);
    }
    pushup(p);
}

int merge(int x, int y) {
    if (!x || !y) return x + y;
    int ans = 0;
    if (tr[x].rnd > tr[y].rnd) {
        tr[x].rs = merge(tr[x].rs, y);
        ans = x;
    } else {
        tr[y].ls = merge(x, tr[y].ls);
        ans = y;
    }
    pushup(ans);
    return ans;
}

int kth(int p, int k) {
    int ls = tr[p].ls, rs = tr[p].rs;
    if (tr[ls].sz + 1 == k) return tr[p].w;
    else if (tr[ls].sz + 1 < k) return kth(tr[p].rs, k - tr[ls].sz - 1);
    else return kth(tr[p].ls, k);
}

int main() {
    srand(time(0));
    int q;
    scanf("%d", &q);
    int rt = 0;
    int x, y, z;
    while (q--) {
        int op, w;
        scanf("%d%d", &op, &w);
        if (op == 1) {
            split(rt, w, x, y);
            rt = merge(merge(x, newNode(w)), y);
        } else if (op == 2) {
            split(rt, w, x, y);
            split(x, w - 1, x, z);
            z = merge(tr[z].ls, tr[z].rs);
            rt = merge(merge(x, z), y);
        } else if (op == 3) {
            split(rt, w - 1, x, y);
            printf("%d\n", tr[x].sz + 1);
            rt = merge(x, y);
        } else if (op == 4) {
            printf("%d\n", kth(rt, w));
        } else if (op == 5) {
            split(rt, w - 1, x, y);
            printf("%d\n", kth(x, tr[x].sz));
            rt = merge(x, y);
        } else if (op == 6) {
            split(rt, w, x, y);
            printf("%d\n", kth(y, 1));
            rt = merge(x, y);
        }
    }

    return 0;
}

/*
若多组数据 初始化时 tot=0; rt=0;
6种操作:
1 插入w
2 删除w 若重复则只删除1个
3 查询w的排名（比w小的数的个数+1）
4 查询排名为w的数
5 求w的前驱（比w小的最大数）
6 求w的后继（比w大的最小数）
*/

洛谷P2042 维护数列

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 500005;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;

struct TreapNode {
    int ls, rs;
    int w, sum, sz, rnd;
    int pre, suf, seq;
    int rev, cov;
} tr[maxn];
int rt;
queue<int> q;

int a[maxn];

void rev(int p) {
    tr[p].rev ^= 1;
    swap(tr[p].ls, tr[p].rs);
    swap(tr[p].pre, tr[p].suf);
}

void cov(int p, int c) {
    tr[p].cov = c;
    tr[p].w = c;
    tr[p].sum = c * tr[p].sz;
    tr[p].pre = tr[p].suf = max(0, tr[p].sum);
    tr[p].seq = max(c, tr[p].sum);
}

void del(int p) {
    if (!p) return;
    q.push(p);
    del(tr[p].ls);
    del(tr[p].rs);
}

void pushdown(int p) {
    int ls = tr[p].ls, rs = tr[p].rs;
    if (tr[p].rev) {
        if (ls) rev(ls);
        if (rs) rev(rs);
        tr[p].rev = 0;
    }
    if (tr[p].cov != inf) {
        if (ls) cov(ls, tr[p].cov);
        if (rs) cov(rs, tr[p].cov);
        tr[p].cov = inf;
    }
}

void pushup(int p) {
    int ls = tr[p].ls, rs = tr[p].rs;
    tr[p].sz = tr[ls].sz + tr[rs].sz + 1;
    tr[p].sum = tr[ls].sum + tr[rs].sum + tr[p].w;

    tr[p].pre = max(tr[ls].pre, tr[ls].sum + tr[p].w + tr[rs].pre);
    tr[p].suf = max(tr[rs].suf, tr[rs].sum + tr[p].w + tr[ls].suf);
    tr[p].seq = tr[ls].suf + tr[p].w + tr[rs].pre;
    if (ls) tr[p].seq = max(tr[p].seq, tr[ls].seq);
    if (rs) tr[p].seq = max(tr[p].seq, tr[rs].seq);
}

int newNode(int w) {
    int p = q.front();
    q.pop();
    tr[p].ls = tr[p].rs = 0;
    tr[p].w = tr[p].sum = w;
    tr[p].sz = 1;
    tr[p].rnd = rand();
    tr[p].pre = tr[p].suf = max(0, w); tr[p].seq = w;
    tr[p].rev = 0; tr[p].cov = inf;
    return p;
}

int build(int l, int r) {
    int mid = (l + r) >> 1;
    int p = newNode(a[mid]);
    if (l <= mid - 1) tr[p].ls = build(l, mid - 1);
    if (mid + 1 <= r) tr[p].rs = build(mid + 1, r);
    pushup(p);
    return p;
}

void split(int p, int sz, int &x, int &y) {
    if (!p) {
        x = y = 0;
        return;
    }
    pushdown(p);
    int ls = tr[p].ls, rs = tr[p].rs;
    if (tr[ls].sz >= sz) {
        y = p;
        split(ls, sz, x, tr[p].ls);
    } else {
        x = p;
        split(rs, sz - 1 - tr[ls].sz, tr[p].rs, y);
    }
    pushup(p);
}

int merge(int x, int y) {
    if (!x || !y) return x + y;
    if (tr[x].rnd > tr[y].rnd) {
        pushdown(x);
        tr[x].rs = merge(tr[x].rs, y);
        pushup(x);
        return x;
    } else {
        pushdown(y);
        tr[y].ls = merge(x, tr[y].ls);
        pushup(y);
        return y;
    }
}

void INSERT() {
    int pos, tot;
    scanf("%d%d", &pos, &tot);
    if (tot == 0) return;
    for (int i = 1; i <= tot; i++) {
        scanf("%d", a + i);
    }
    int y = build(1, tot);
    int x, z;
    split(rt, pos, x, z);
    rt = merge(merge(x, y), z);
}

void DELETE() {
    int pos, tot;
    scanf("%d%d", &pos, &tot);
    if (tot == 0) return;
    int x, y, z;
    split(rt, pos - 1, x, y);
    split(y, tot, y, z);
    del(y);
    rt = merge(x, z);
}

void COVER() {
    int pos, tot, c;
    scanf("%d%d%d", &pos, &tot, &c);
    if (tot == 0) return;
    int x, y, z;
    split(rt, pos - 1, x, y);
    split(y, tot, y, z);
    cov(y, c);
    rt = merge(merge(x, y), z);
}

void REVERSE() {
    int pos, tot;
    scanf("%d%d", &pos, &tot);
    if (tot == 0) return;
    int x, y, z;
    split(rt, pos - 1, x, y);
    split(y, tot, y, z);
    rev(y);
    rt = merge(merge(x, y), z);
}

void GETSUM() {
    int pos, tot;
    scanf("%d%d", &pos, &tot);
    if (tot == 0) {
        printf("0\n");
        return;
    }
    int x, y, z;
    split(rt, pos - 1, x, y);
    split(y, tot, y, z);
    printf("%d\n", tr[y].sum);
    rt = merge(merge(x, y), z);
}

void MAXSUM() {
    printf("%d\n", tr[rt].seq);
}

int main() {
    srand(time(0));
    for (int i = 1; i < maxn; i++) {
        q.push(i);
    }

    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", a + i);
    }
    rt = build(1, n);

    while (m--) {
        char op[20];
        scanf("%s", op);
        if (op[0] == 'I') {
            INSERT();
        } else if (op[0] == 'D') {
            DELETE();
        } else if (op[0] == 'M' && op[2] == 'K') {
            COVER();
        } else if (op[0] == 'R') {
            REVERSE();
        } else if (op[0] == 'G') {
            GETSUM();
        } else if (op[0] == 'M' && op[2] == 'X') {
            MAXSUM();
        }
    }

    return 0;
}

/*
INSERT(); 往第pos个数后插入tot个数
DELETE(); 从pos起删除tot个数（含pos）
COVER(); 从pos起tot个数均修改为c（含pos）
REVERSE(); 从pos起tot个数翻转（含pos）
GETSUM(); 从pos起tot个数求和（含pos）
MAXSUM(); 求整个数列的最大连续子段和（不可取空段）
*/