投稿
  1. 高性能架构探索首页
  2. C/C++

区间信息的维护与查询

admin • • C/C++ • 阅读 129

\(BIT\)

大家都会。

//可单点修改区间查询的BIT
//BIT<N> tree; 定义一个大小为 N 的BIT
//modify(x, v) a[x] += v
//query(x) -> sum(1, x)的值
//query(x, y) -> sum(x, y)的值
template<int SIZ>
struct BIT{
    #define inl inline
    #define I int
    I c[SIZ];
    inl I lb(I x){return x & (-x);}
    inl void modify(I x, I v){for(; x < SIZ; x+=lb(x)) c[x] += v;}
    inl I query(I x){int cur = 0; while(x){cur += c[x], x -= lb(x);} return cur;}
    inl I query(I x, I y){return query(y) - query(x-1);}
};

//可区间修改单点查询的BIT
//BIT<N> tree; 定义一个大小为 N 的BIT
//modify(l, r, v) a[l~r] += v
//query(x) -> a[x] 的值
template<int SIZ>
struct BIT{
    #define inl inline
    #define I int
    I c[SIZ];
    inl I lb(I x){return x & (-x);}
    inl void modify(I x, I v){for(; x < SIZ; x+=lb(x)) c[x] += v;}
    inl void modify(I l, I r, I v){modify(l, v), modify(r+1, -v);}
    inl I query(I x){int cur = 0; while(x){cur += c[x], x -= lb(x);} return cur;}
};

线段树

大家都会。

// Author: __ODT__
// web: https://www.luogu.com.cn/problem/SP1716
// SP1716 GSS3 - Can you answer these queries III
// Accepted
/*
题意：
	n 个数，q 次操作
	操作 0 x y 把 a[x] 修改为 y
	操作 1 l r 询问区间 [l,r] 的最大子段和
*/
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <queue>
using namespace std;
const int N = 1e5;
const int inf = 0x3f3f3f3f;
#define I int
struct node{
    I all, maxmid, l, r;
    friend bool operator == (node x, node y){
        return x.all == y.all && x.maxmid == y.maxmid && x.l == y.l && x.r == y.r;
    }
};
node nones = (node){-inf, -inf, -inf, -inf};
void merge(node &mg, node x, node y){
    if(x == nones) mg = y;
    if(y == nones) mg = x;
    if(x == nones || y == nones) return;
    mg.all = x.all + y.all;
    mg.maxmid = max(max(x.maxmid, y.maxmid), x.r+y.l);
    mg.l = max(x.l, x.all+y.l);
    mg.r = max(y.r, y.all+x.r);
}
void init(node &x, int val){x.all = x.maxmid = x.l = x.r = val;}
int n, a[N];
struct segmenttree
{
    node t[N<<2];
    #define lc ((k)<<(1))
    #define rc ((k)<<(1)|(1))
    #define mid ((l)+(r)>>(1))
    void pushup(int k){merge(t[k], t[lc], t[rc]);}
    void build(int k = 1, int l = 1, int r = n){
        if(l == r){init(t[k], a[l]);return;}
        build(lc, l, mid), build(rc, mid+1, r);
        pushup(k);
    }
    void modify(int x, int y, int k = 1, int l = 1, int r = n){
        if(l == r){init(t[k], y); return;}
        if(x <= mid) modify(x, y, lc, l, mid);
        else modify(x, y, rc, mid+1, r);
        pushup(k);
    }
    node query(int x, int y, int k = 1, int l = 1, int r = n){
        if(x > r || y < l) return nones;
        if(l >= x && r <= y) return t[k];
        node cur; merge(cur, query(x, y, lc, l, mid), query(x, y, rc, mid+1, r));
        return cur;
    }
}sgt;
inline I read(){
    static I bo, x; bo = x = 0; static char c; c = getchar();
    while(c < '0' || c > '9'){if(c == '-')bo = 1; c = getchar();}
    while(c >= '0' && c <= '9') {x = (x<<3) + (x<<1) + c - '0'; c = getchar();}
    return bo ? -x : x;
}
inline void out(I x, bool bo = true){
    if(x < 0) putchar('-'), x = -x;
    if(x == 0){if(bo)putchar('0'); return;}
    out(x/10, false), putchar('0' + x%10);
}
int main(){
    n = read();
    for(int i = 1; i <= n; i ++) a[i] = read();
    sgt.build();
    int q = read();
    for(int i = 1; i <= q; i ++){
        int opt = read(), l = read(), r = read();
        if(opt) out((sgt.query(l, r)).maxmid), puts("");
        else sgt.modify(l, r);
    }
    return 0;
}

\(RMQ\)

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
int n,m,a[1111111];
int f[1111111][24];
int lg[1111111];
int main()
{
	memset(f,-1,sizeof(f));
	n=read();
	m=read();
	for(int i=1; i<=n; i++)
	f[i][0]=read();
	for(int j=1; j<=23; j++)
	{
		for(int i=1; i+(1<<j)-1<=n; i++)
		{
			f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);
		}
	}
	for(int i=1; i<=m; i++)
	{
		int l=read(),r=read();
		int c=log2(r-l+1);
		printf("%d\n",max(f[l][c],f[r-(1<<c)+1][c]));
	}
}

习题

P5848 [IOI2005]mou

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <iostream>
using namespace std;
typedef int ll;
struct node{
    ll sum, ls;
    int val, lc, rc;
}t[5500005];
int cnt = 1, n;
void push_up(int k){
    t[k].sum = t[t[k].lc].sum + t[t[k].rc].sum;
    t[k].ls = max(t[t[k].lc].ls, t[t[k].rc].ls + t[t[k].lc].sum);
    return;
}
void Setv(int k, int v, int l, int r){
    assert(l <= r);
    t[k].sum = (ll)(r - l + 1) * (t[k].val = v);
    t[k].ls = max(0, t[k].sum);
    t[k].lc = t[k].rc = 0;
}
void push_down(int k, int l, int r){
    int mid = l + r >> 1;
    t[k].lc = ++cnt;
    t[k].rc = ++cnt;
    Setv(t[k].lc, t[k].val, l, mid);
    Setv(t[k].rc, t[k].val, mid+1, r);
    return;
}
void add(int k, int l, int r, int x, int y, int z){
    int mid = l + r >> 1;
    if(l >= x and r <= y){
        Setv(k, z, l, r);
        return;
    }
    if(t[k].lc == t[k].rc and t[k].lc == 0) push_down(k, l, r);
    if(x <= mid) add(t[k].lc, l, mid, x, y, z);
    if(y > mid) add(t[k].rc, mid+1, r, x, y, z);
    push_up(k);
}
int ask(int k, int l, int r, ll high){
    if(high >= t[k].ls) return r;
    if(t[k].lc == t[k].rc and t[k].lc == 0) return l + (high / t[k].val) - 1;
    int mid = l + r >> 1;
    return high >= t[t[k].lc].ls ? ask(t[k].rc, mid + 1, r, high - t[t[k].lc].sum) : ask(t[k].lc, l, mid, high);
}
int main(){
    cin >> n; char s;
    for(int x, y, z; cin >> s and s != 'E';){
        if(s == 'I'){cin >> x >> y >> z; add(1, 1, n, x, y, z);}
        else {cin >> x;cout << ask(1, 1, n, x) << '\n';}
    }
    return 0;
}

UVA11992 Fast Matrix Operations

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
#define _for(i, a, b) for(int i = (a); i <= (b); i ++)
const int N = 1e6 + 11;
struct node{
    int tag1, tag2, _max, _min;
    int sum;
    void Tag1(int x, int L, int R){
        sum = x * (R - L + 1);
        _max = _min = tag1 = x;
        tag2 = 0;
        return;
    }
    void Tag2(int x, int L, int R){
        sum += x * (R - L + 1);
        _max += x, _min += x;
        tag2 += x;
        return;
    }
};
node merge(node x, node y){
    node k = {0,0, 0,0, 0};
    k.sum = x.sum + y.sum;
    k._max = max(x._max, y._max);
    k._min = min(x._min, y._min);
    return k;
}
struct Segment_Tree{
    node tree[N<<2];
    void build(int k, int l, int r){
        tree[k] = {0,0, 0,0, 0};
        if(l == r){return;}
        int mid = l + r >> 1;
        build(k<<1, l, mid);
        build(k<<1|1, mid+1, r);
    }
    void push_down(int k, int l, int r){
        int mid = l + r >> 1;
        if(tree[k].tag1){
            tree[k<<1].Tag1(tree[k].tag1, l, mid);
            tree[k<<1|1].Tag1(tree[k].tag1, mid+1, r);
            tree[k].tag1 = 0;
        }
        if(tree[k].tag2){
            tree[k<<1].Tag2(tree[k].tag2, l, mid);
            tree[k<<1|1].Tag2(tree[k].tag2, mid+1, r);
            tree[k].tag2 = 0;
        }
        return;
    }
    void add(int k, int l, int r, int x, int y, int v, int opt){
        if(l > y or r < x) return;
        if(l >= x and r <= y){
            if(opt == 1) tree[k].Tag1(v, l, r);
            else tree[k].Tag2(v, l, r);
            return;
        }
        push_down(k, l, r);
        int mid = l + r >> 1;
        if(x <= mid) add(k<<1, l, mid, x, y, v, opt);
        if(y > mid) add(k<<1|1, mid + 1, r, x, y, v, opt);
        tree[k] = merge(tree[k<<1], tree[k<<1|1]);
        return;
    }
    node ask(int k, int l, int r, int x, int y){
        if(l > y or r < x) return (node){0,0, -0x3f3f3f3f,0x3f3f3f3f, 0};
        if(l >= x and r <= y) return tree[k];
        push_down(k, l, r);
        int mid = l + r >> 1;
        return merge(ask(k<<1, l, mid, x, y), ask(k<<1|1, mid+1, r, x, y));
    }
}Segment_tree[21];
int main(){
    int r, c, m;
    while(scanf("%d %d %d", &r, &c, &m) != EOF){
        _for(i, 1, r) Segment_tree[i].build(1, 1, c);
        _for(OPT, 1, m){
            int opt, X1, X2, Y1, Y2, v;
            scanf("%d%d%d%d%d", &opt, &X1, &Y1, &X2, &Y2);
            if(opt == 1){
                scanf("%d", &v);
                _for(i, X1, X2)
                    Segment_tree[i].add(1, 1, c, Y1, Y2, v, 2);
            }
            if(opt == 2){
                scanf("%d", &v);
                _for(i, X1, X2)
                    Segment_tree[i].add(1, 1, c, Y1, Y2, v, 1);
            }
            if(opt == 3){
                node Ans = (node){0,0, -0x3f3f3f3f,0x3f3f3f3f, 0};
                _for(i, X1, X2)
                    Ans = merge(Ans, Segment_tree[i].ask(1, 1, c, Y1, Y2));
                printf("%d %d %d\n", Ans.sum, Ans._min, Ans._max);
            }
        }
    }
    return 0;
}

UVA12419 Heap Manager

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
using namespace std;
const int N = 1e6;
struct node{
    int ch[2], tag, lz, rz, midz;
};
struct Segment_Tree{
    #define lc t[k].ch[0]
    #define rc t[k].ch[1]
    int cnt = 1;
    node t[N<<2];
    inline void push_up(int k, int l, int r){
        int mid = l + r >> 1;
        t[k].lz = (mid - l + 1 == t[lc].lz ? t[lc].lz + t[rc].lz : t[lc].lz);
        t[k].rz = (    r - mid == t[rc].rz ? t[rc].rz + t[lc].rz : t[rc].rz);
        t[k].midz = max(max(t[lc].midz, t[rc].midz), t[lc].rz + t[rc].lz);
    }
    inline void setv(int k, int l, int r, int co){
        t[k].tag = co;
        t[k].lz = t[k].rz = t[k].midz = (co == 1 ? r - l + 1 : 0);
    }
    inline void push_down(int k, int l, int r){
        if(!lc) lc = ++cnt;
        if(!rc) rc = ++cnt;

        if(t[k].tag == 0)return;
        int mid = l + r >> 1;
        setv(lc, l, mid, t[k].tag);
        setv(rc, mid+1, r, t[k].tag);
        t[k].tag = 0;
    }
    inline void add(int k, int l, int r, int x, int y, int co){
        if(r < x or l > y) return;
        if(l >= x and r <= y){
            setv(k, l, r, co);
            return;
        }
        int mid = l + r >> 1;
        push_down(k, l, r);
        if(x <= mid) add(lc, l, mid, x, y, co);
        if(y > mid) add(rc, mid+1, r, x, y, co);
        push_up(k, l, r);
    }
    inline int ask(int k, int l, int r, int length){
        if(t[k].lz >= length) return l;
        push_down(k, l, r);
        int mid = l + r >> 1;
        if(t[lc].midz >= length) return ask(lc, l, mid, length);
        if(t[lc].rz + t[rc].lz >= length) return mid - t[lc].rz + 1;
        return ask(rc, mid+1, r, length);
    }
}Segment_Trees;
struct outevent{
    int t, l, r;
    bool operator < (const outevent &rhs)const{
        return t > rhs.t;
    }
};
priority_queue<outevent> QQ;
struct event{
    int len, t, id;
};
queue<event> q;
int n, b, pcnt, m, p;
void Add(int Tim, const event &x){
    int wh = Segment_Trees.ask(1, 1, n, x.len);
    Segment_Trees.add(1, 1, n, wh, wh + x.len - 1, 2);
    QQ.push(outevent{x.t + Tim, wh, wh + x.len - 1});
    if(b) printf("%d %d %d\n", Tim, x.id, wh - 1);
}
int main(){
    while(cin >> n >> b){
        int t, ans;
        ans = t = 0;
        pcnt = 0;
        Segment_Trees.add(1, 1, n, 1, n, 1);
        for(int i = 1; ; i ++){
            cin >> t >> m >> p;
            if(t == 0 and m == 0 and p == 0) t = 0x3f3f3f3f;
            while(!QQ.empty() and QQ.top().t <= t){
                int T = QQ.top().t;
                while(!QQ.empty() and QQ.top().t == T){
                    const outevent& x = QQ.top();
                    ans = x.t;
                    Segment_Trees.add(1, 1, n, x.l, x.r, 1);
                    QQ.pop();
                }
                while(!q.empty() and q.front().len <= Segment_Trees.t[1].midz){
                    Add(T, q.front());
                    q.pop();
                }
            }
            if(t == 0x3f3f3f3f)break;
            if(m <= Segment_Trees.t[1].midz)Add(t, event{m, p, i});
            else q.push(event{m, p, i}), pcnt++;
        }
        printf("%d\n%d\n\n", ans, pcnt);
    }
    return 0;
}

UVA1232 SKYLINE

#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <queue>
using namespace std;
const int N = 1e5 + 11;
struct node{
    int h1, h2, tag;
};
struct Segment_Tree{
    node t[N<<2];
    void push_up(int x){
        t[x].h1 = min(t[x<<1].h1, t[x<<1|1].h1);
        t[x].h2 = max(t[x<<1].h2, t[x<<1|1].h2);
    }
    void push_down(int k){
        if(t[k].tag == 0) return;
        t[k<<1].h1 = t[k<<1|1].h1 = t[k].tag;
        t[k<<1].h2 = t[k<<1|1].h2 = t[k].tag;
        t[k<<1].tag = t[k<<1|1].tag = t[k].tag;
        t[k].tag = 0;
    }
    int ask(int k, int l, int r, int x, int y, int v){
        if(t[k].h1 > v) return 0;
        if(l >= x and r <= y){
            if(t[k].h2 <= v){
                t[k].h1 = t[k].tag = t[k].h2 = v;
                return r - l + 1;
            }
        }
        push_down(k);
        int mid = l + r >> 1, ans = 0;
        if(x <= mid) ans += ask(k<<1, l, mid, x, y, v);
        if(y > mid) ans += ask(k<<1|1, mid+1, r, x, y, v);
        push_up(k);
        return ans;
    }
}segment_tree;
int main(){
    int T, n;
    cin >> T;
    while(T--){
        memset(segment_tree.t, 0, sizeof segment_tree.t);
        cin >> n;
        int Ans = 0;
        for(int i = 1; i <= n; i ++) {
            static int x, y, v; cin >> x >> y >> v;
            y--;
            Ans += segment_tree.ask(1, 1, N - 11, x, y, v);
        }
        cout << Ans << endl;
    }
    return 0;
}

UVA11525 Permutation

#include <algorithm>
#include <cmath>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5;
int T, n;
struct Segment_Tree{
    int sum[N<<2];
    void push_up(int x) {sum[x] = sum[x<<1] + sum[x<<1|1];}
    int kth(int k, int l, int r, int kths){
        if(l == r) { sum[k] = 0; return l; }
        int mid = l + r >> 1, ans;
        if(sum[k<<1] >= kths) ans = kth(k<<1, l, mid, kths);
        else ans = kth(k<<1|1, mid+1, r, kths - sum[k<<1]);
        push_up(k); return ans;
    }
    void build(int k, int l, int r){
        if(l == r){sum[k] = 1;return;}
        int mid = l + r >> 1;
        build(k<<1, l, mid), build(k<<1|1, mid+1, r);
        push_up(k);
    }
}Segment_Trees;
int main(){
    scanf("%d", &T);
    while(T--){
        scanf("%d", &n);
        Segment_Trees.build(1, 1, n);
        for(int i = 1; i <= n; i ++){
            static int x; scanf("%d", &x);
            printf("%d", Segment_Trees.kth(1, 1, n, x + 1));
            if(i < n) putchar(' ');
        }
        puts("");
    }
}

UVA1455 Kingdom

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <cstdio>
using namespace std;
#define _for(i, a, b) for(int i = (a); i <= (b); i ++)
const int N = 1e6 + 11;
struct node{
    int sum, tag;
};
struct Segment_Tree{
    node t[N<<2];
    #define lc (k<<(1))
    #define rc ((k<<(1))|(1))
    void push_up(int k){t[k].sum = t[lc].sum + t[rc].sum;}
    void push_down(int k, int l, int r){
        if(t[k].tag == 0)return;
        int mid = l + r >> 1;
        t[lc].sum += t[k].tag * (mid - l + 1);
        t[rc].sum += t[k].tag * (r - mid);
        t[lc].tag += t[k].tag;
        t[rc].tag += t[k].tag;
        t[k].tag = 0;
    }
    void modify(int k, int l, int r, int x, int y, int v){
        if(l >= x and r <= y){
            t[k].sum += v * (r - l + 1);
            t[k].tag += v;
            return;
        }
        push_down(k, l, r);
        int mid = l + r >> 1;
        if(x <= mid) modify(lc, l, mid, x, y, v);
        if(y > mid) modify(rc, mid+1, r, x, y, v);
        push_up(k);
    }
    int ask(int k, int l, int r, int x){
        if(l == r){
            return t[k].sum;
        }
        push_down(k, l, r);
        int mid = l + r >> 1;
        if(x <= mid) return ask(lc, l, mid, x);
        if(x > mid) return ask(rc, mid+1, r, x);
    }
    void build(int k, int l, int r){
        t[k] = {0, 0}; if(l == r)return;
        int mid = l + r >> 1;
        build(lc, l, mid), build(rc, mid+1, r);
    }
}Segment_trees[2];
int Y[N], n, T, m;
int maxy(0);
struct Union_Find{
    int fa[N], L[N], R[N], siz[N];
    void init(){
        _for(i, 1, n){
            fa[i] = i;
            siz[i] = 1;
            L[i] = R[i] = Y[i];
        }
    }
    int find(int x){
        return fa[x] == x ? x : fa[x] = find(fa[x]);
    }
    void Union(int x, int y){
        x = find(x), y = find(y);
        if(x == y) return;


        if(L[x] < R[x])
            Segment_trees[0].modify(1, 1, maxy+1, L[x] + 1, R[x], -1),
            Segment_trees[1].modify(1, 1, maxy+1, L[x] + 1, R[x], -siz[x]);
        if(L[y] < R[y])
            Segment_trees[0].modify(1, 1, maxy+1, L[y] + 1, R[y], -1),
            Segment_trees[1].modify(1, 1, maxy+1, L[y] + 1, R[y], -siz[y]);


        L[y] = min(L[y], L[x]);
        R[y] = max(R[y], R[x]);
        siz[y] = siz[x] + siz[y];
        fa[x] = y;


        if(L[y] < R[y])
            Segment_trees[0].modify(1, 1, maxy+1, L[y] + 1, R[y], 1),
            Segment_trees[1].modify(1, 1, maxy+1, L[y] + 1, R[y], siz[y]);
        return;
    }
}Sets;
int main(){
    scanf("%d", &T);
    while(T--){
        scanf("%d", &n);
        maxy = 0;
        _for(i, 1, n){
            static int x;
            scanf("%d %d", &x, &Y[i]);
            maxy = max(maxy, Y[i]);
        }
        Sets.init();
        Segment_trees[0].build(1, 1, maxy+1);
        Segment_trees[1].build(1, 1, maxy+1);
        scanf("%d", &m);
        char opt[11];
        _for(i, 1, m){
            scanf("%s", opt);
            if(opt[0] == 'l'){    
                static int v;
                static double y;
                scanf("%lf", &y);
                v = (int)floor(y + 0.6);
                printf("%d %d\n", Segment_trees[0].ask(1, 1, maxy+1, v), Segment_trees[1].ask(1, 1, maxy+1, v));
            }
            else{
                static int x, y;
                scanf("%d %d", &x, &y);
                x++, y++;
                Sets.Union(x, y);
            }
        }
    }
    return 0;
}

原文链接: https://www.cnblogs.com/dadidididi/p/17067885.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍

    区间信息的维护与查询

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/314226

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

赞 (0)
adminadmin
0 0
上一篇 2023年2月16日 下午1:13
下一篇 2023年2月16日 下午1:13

相关推荐