Htto的小站
0%

数据结构

发表于 更新于 分类于 ，

[TOC]

线段树模版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
#define int long long
namespace SegTree{
    const int maxn=1e6+5;
    int dat[maxn],tree[maxn*4],tag[maxn*4];
    int n;
    int lson(int p){return 2*p;}
    int rson(int p){return 2*p+1;}
    void push_up(int p){
        tree[p]=tree[lson(p)]+tree[rson(p)];
    }
    void f(int p,int l,int r,int v)
    {
        tag[p]+=v;
        tree[p]+=(r-l+1)*v;
    }
    void push_down(int p,int l,int r)
    {
        int m=(l+r)/2;
        f(lson(p),l,m,tag[p]);
        f(rson(p),m+1,r,tag[p]);
        tag[p]=0;
    }

    void build(int l=1,int r=n,int p=1){
        if(l==r)
            tree[p]=dat[l];
        else{
            int m=(l+r)/2;
            build(l,m,lson(p));
            build(m+1,r,rson(p));
            tree[p]=tree[lson(p)]+tree[rson(p)];
        }
    }
    void update(int p,int l,int r,int L,int R,int v)
    {
        if(l > R || r < L) return;
        if(l<=L && r>=R)
        {
            f(p,L,R,v);
            return;
        }
        push_down(p,L,R);
        int m=(L+R)/2;
        if(l <= m) update(lson(p),l,r,L,m,v);
        if(r > m) update(rson(p),l,r,m+1,R,v);
        push_up(p);
    }
    void update(int l,int r,int v)
    {
        update(1,l,r,1,n,v);
    }
    int query(int p,int l,int r,int L,int R)
    {
        if(l>R || r<L) return 0;
        if(l<=L && r>=R) return tree[p];
        push_down(p,L,R);
        int m=(L+R)/2;
        int res=0;
        if(l<=m) res+=query(lson(p),l,r,L,m);
        if(r>m) res+=query(rson(p),l,r,m+1,R);
        return res;
    }
    int query(int l,int r)
    {
        return query(1,l,r,1,n);
    }
}
signed main(){
    int n,m;
    cin>>n>>m;
    SegTree::n=n;
    for(int i=1;i<=n;i++)
        cin>>SegTree::dat[i];
    SegTree::build();

    for(int i=1;i<=m;i++)
    {
        int a;
        cin>>a;
        if(a==1)
        {
            int x,y,k;
            cin>>x>>y>>k;
            SegTree::update(x,y,k);
        }
        else{
            int x,y;
            cin>>x>>y;
            cout<<SegTree::query(x,y)<<endl;
        }
    }
    return 0;
}

模版版模版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

template <typename T, typename Operator>
class SegTree {
public:
    SegTree(T *begin, T *end, T _z = T()) : A(begin), one(_z) {
        n = end - begin;
        tree = new T[4 * n];
        build(1, 1, n);
    }
    void update(int i, T value) { update(i, value, 1, 1, n); }
    T query(int l, int r) { return query(l, r, 1, 1, n); }
    ~SegTree() { delete[] tree; }

private:
    void merge(int p) { tree[p] = _oper(tree[_ls(p)], tree[_rs(p)]); }

    void build(int p, int L, int R) {
        if (L == R)
            tree[p] = A[L];
        else {
            int m = (L + R) / 2;
            build(_ls(p), L, m);
            build(_rs(p), m + 1, R);
            merge(p);
        }
    }

    T query(int l, int r, int p, int L, int R) {
        if (l > R || r < L)
            return one;
        if (l <= L && r >= R) {
            return tree[p];
        }
        int m = (L + R) / 2;
        T ret = one;
        if (l <= m)
            ret = _oper(ret, query(l, r, _ls(p), L, m));
        if (r > m)
            ret = _oper(ret, query(l, r, _rs(p), m + 1, R));
        return ret;
    }

    void update(int i, T value, int p, int L, int R) {
        if (i < L || i > R)
            return;
        if (L == R) {
            tree[p] = value;
            return;
        }
        int m = (L + R) / 2;
        if (i <= m)
            update(i, value, _ls(p), L, m);
        else
            update(i, value, _rs(p), m + 1, R);
        merge(p);
    }

    inline int _ls(int p) { return 2 * p; }

    inline int _rs(int p) { return 2 * p + 1; }

    int n;

    T *tree;

    T *A;

    Operator _oper;

    T one;
};

01-字典树

模版

Xor Sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
namespace Trie01
{
    int trie[33 * maxn][2];
    int num[33 * maxn], cnt = 1;
    void init()
    {
        memset(trie, 0, sizeof(trie));
        memset(num, 0, sizeof(num));
        cnt = 1;
    }

    void insert(int x)
    {
        int cur = 1;
        for (int i = max_bit; i >= 0; i--)
        {
            int bit = x >> i & 1;
            if (!trie[cur][bit])
                trie[cur][bit] = ++cnt;
            cur = trie[cur][bit];
        }
        num[cur] = x;
    }

    int find_xor_max(int x)
    {
        int cur = 1;
        for (int i = max_bit; i >= 0; i--)
        {
            int bit = x >> i & 1;
            if (trie[cur][bit ^ 1])
                cur = trie[cur][bit ^ 1];
            else
                cur = trie[cur][bit];
        }
        return num[cur];
    }
}

CF1446 Xor Tree

给定你一个序列aa，对于每个\(i\)，它会向序列中的满足\(a_i \oplus a_j\)最小的\(j\)连双向边，并且如果\(j\)也向\(i\)连了边，只算一条边。现在要让你删去序列中的一些数，使得最后形成的图是一颗树，输出最少需要删除几个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 3e5 + 5;
const int max_bit = 32;
#define int long long

int n;
int A[maxn];
namespace Trie01
{
    int trie[32 * maxn][2];
    int num[32 * maxn], cnt = 1;
    void init()
    {
        memset(trie, 0, sizeof(trie));
        memset(num, 0, sizeof(num));
        cnt = 1;
    }

    void insert(int x)
    {
        int cur = 1;
        for (int i = max_bit; i >= 0; i--)
        {
            int bit = x >> i & 1;
            if (!trie[cur][bit])
                trie[cur][bit] = ++cnt;
            cur = trie[cur][bit];
        }
        num[cur] = x;
    }

    int find_xor_max(int x)
    {
        int cur = 1;
        for (int i = max_bit; i >= 0; i--)
        {
            int bit = x >> i & 1;
            if (trie[cur][bit ^ 1])
                cur = trie[cur][bit ^ 1];
            else
                cur = trie[cur][bit];
        }
        return num[cur];
    }
}

int dfs(int p = 1)
{
    int l = Trie01::trie[p][0], r = Trie01::trie[p][1];
    if (!l && !r)
        return 1;
    if (!l)
        return dfs(r);
    if (!r)
        return dfs(l);
    return max(dfs(l), dfs(r)) + 1;
}
signed main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> A[i];
        Trie01::insert(A[i]);
    }
    cout << n - dfs(1) << endl;
    return 0;
}

388535

This is the easy version of the problem. The difference in the constraints between both versions is colored below in red. You can make hacks only if all versions of the problem are solved.

Marin and Gojou are playing hide-and-seek with an array.

Gojou initially performs the following steps:

  • First, Gojou chooses \(2\) integers \(l\) and \(r\) such that \(l \leq r\).
  • Then, Gojou makes an array \(a\) of length \(r-l+1\) which is a permutation of the array \([l,l+1,\ldots,r]\).
  • Finally, Gojou chooses a secret integer \(x\) and sets \(a_i\) to \(a_i \oplus x\) for all \(i\) (where \(\oplus\) denotes the bitwise XOR operation).

Marin is then given the values of \(l,r\) and the final array \(a\). She needs to find the secret integer \(x\) to win. Can you help her?

Note that there may be multiple possible \(x\) that Gojou could have chosen. Marin can find any possible \(x\) that could have resulted in the final value of \(a\).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int maxn = (1 << 17) + 5;

namespace DS
{
    int nxt[maxn * 18][2];
    int num[maxn * 18];
    int cnt = 1;
    void init()
    {
        nxt[0][1] = nxt[0][0] = 0;
        cnt = 1;
    }

    void insert(int x)
    {
        int cur = 0;
        for (int i = 20; i >= 0; i--)
        {
            int bit = x >> i & 1;
            if (!nxt[cur][bit])
            {
                nxt[cnt][0] = nxt[cnt][1] = 0;
                nxt[cur][bit] = cnt++;
            }
            cur = nxt[cur][bit];
        }
        num[cur] = x;
    }
    int find_max(int x)
    {
        int cur = 0;
        for (int i = 20; i >= 0; i--)
        {
            int bit = x >> i & 1;
            if (nxt[cur][bit ^ 1])
                cur = nxt[cur][bit ^ 1];
            else
                cur = nxt[cur][bit];
        }
        return num[cur] ^ x;
    }
    int find_min(int x)
    {
        int cur = 0;
        for (int i = 20; i >= 0; i--)
        {
            int bit = x >> i & 1;
            if (nxt[cur][bit])
                cur = nxt[cur][bit];
            else
                cur = nxt[cur][bit ^ 1];
        }
        return num[cur] ^ x;
    }
}
int A[maxn];
void solve()
{
    DS::init();
    int l, r;
    cin >> l >> r;
    for (int i = 1; i <= r - l + 1; i++)
    {
        cin >> A[i];
        DS::insert(A[i]);
    }
    for (int i = 1; i <= r - l + 1; i++)
    {
        int cur = l ^ A[i];
        // printf("%d->%d,%d\n", i, DS::find_min(cur), DS::find_max(cur));
        if (DS::find_min(cur) == l && DS::find_max(cur) == r)
        {
            cout << cur << "\n";
            return;
        }
    }
    cout << -1 << "\n";
}
int main()
{
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

^ 参考 Pecco