前缀和和差分

https://ac.nowcoder.com/acm/contest/19483

普通前缀和

前缀和数组

对于数组 \(A\) 的前缀和数组 \(s\) 是 \[ s[x]=\sum_{i=0}^{x}A[i] \] 递推公式 \[ s[x]=s[x-1]+A[x] \\ s[0]=0 \]

广义前缀和

把求和看成某种操作的累加。

维护dp矩阵

DP转移用矩阵表示，然后可以用前缀和维护

求 \[ dp(l,r) = dp(1,r)-dp(1,l) \] 设初始列向量为 \(\textbf{v}\), 转移矩阵为 \(mat[i]\)

然后 \[ dp(l,r) = mat[r] \cdot mat[r-1] \cdot mat[r-2]...mat[l+1] \cdot \textbf{v} \] 所以我们维护一个左乘矩阵前缀和 \[ sum[i] = mat[i] \cdot mat[i-1] ... mat[2] \cdot mat[1]\\ sum[i]=mat[i] \cdot sum[i-1] \] 维护好之后计算的时候： \[ dp(l,r) = sum[r] \cdot (sum[l])^{-1} \cdot \textbf{v} \]

差分

高维前缀和

线段树

https://ac.nowcoder.com/acm/contest/19684

势能线段树

https://ac.nowcoder.com/acm/contest/19917

平衡树

https://ac.nowcoder.com/acm/contest/20160

莫队

https://ac.nowcoder.com/acm/contest/20376

可持久化

https://ac.nowcoder.com/acm/contest/20647

CDQ分治

https://ac.nowcoder.com/acm/contest/20888

变量

用变量来个维护一个性质

维护数组的最大值

平衡树

set和multiset

是一颗支持插入删除的平衡树

定义与操作

自小到大的

1
set<int> s;

自大到小

1
set<int, greater<int>> s;

头元素

1
*s.begin()

尾元素

1
*s.rbegin() | *(--s.end())

大于或等于自己的元素

1
*lower_bound(v)

后继

1
*upper_bound(v)

前驱

1
2
3
if (v != s.begin()) {
    return *(--lower_bound(v));
}

寻找元素

返回一个元素的迭代器，若不存在则返回 s.end()

1
s.find(v)

计算元素个数

1
s.count(v)

中序遍历

1
2
3
4
5
set<int> s;
s.insert(4); s.insert(9); s.insert(1); s.insert(7); s.insert(5);

for (auto x : s) cout << x<< " ";
cout << endl;

不要用auto循环变处理边删除

1
2
3
4
5
6
7
for (auto t : s) { // 改用 while
    i++;
    b.push_back(t.second);
    cnt[t.second]++;
    if (t.first == cnt[t.second]) s.erase(t); // 别这样
    if (i == x) break;
}

好题

pbds

添加头文件

1
2
#include <bits/extc++.h>
using namespace __gnu_pbds;

红黑树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
tree<pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update> tr;
pii //存储的类型
null_type //无映射(低版本g++为null_mapped_type)
less<pii> //从小到大排序
rb_tree_tag //红黑树
tree_order_statistics_node_update //更新方式 
tr.insert(mp(x,y)); //插入;
tr.erase(mp(x,y)); //删除;
tr.order_of_key(pii(x,y)); //求排名 
tr.find_by_order(x); //找k小值，返回迭代器 
tr.join(b); //将b并入tr，前提是两棵树类型一样且没有重复元素 
tr.split(v,b); //分裂，key小于等于v的元素属于tr，其余的属于b
tr.lower_bound(x); //返回第一个大于等于x的元素的迭代器
tr.upper_bound(x); //返回第一个大于x的元素的迭代器
//以上所有操作的时间复杂度均为O(logn)

可重复红黑树

1
2
3
4
5
6
7
8
tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> bbt;
int sz;
#define ins(k) (bbt.insert((k<<20)+(++sz)))
#define del(k) (bbt.erase(bbt.lower_bound(k<<20)))
#define rk(k) (bbt.order_of_key(k<<20)+1)
#define kth(k) ((*bbt.find_by_order(k-1))>>20)
#define lower(k) ((*--bbt.lower_bound(k<<20))>>20)
#define upper(k) ((*bbt.upper_bound((k<<20)+n))>>20)

Splay

博客：

这个教程

标准splay模板

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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
/** splay tree
 * Author: Fyind
 * 
 */
#include <bits/stdc++.h>
using namespace std;
#define oo (1e9+1)
typedef long long ll;
const int maxn = 1e5 + 1;

int n, m;
typedef int typec;


int root, tot;
template<typename T>
struct Node {
    /** Node: Splay树节点
     * v: 节点的值
     * fa: 父亲节点
     * ch[0]: 左子节点
     * ch[1]: 右子节点
     * rep: 重复值的个数
     * sz: 子树元素个数(包含重复节点)
     */
    int fa, ch[2], rep, sz;
    T v;
};

#define child spl[x].ch[nxt]
#define fa(x) spl[x].fa
#define ls(x) spl[x].ch[0]
#define rs(x) spl[x].ch[1]
#define root spl[0].ch[1]

Node<int> spl[maxn];

template<typename T>
int newnode(T v, int fa) {
    /** 新建一个节点, 返回节点编号
     * v: 新建节点的值
     * fa: 谁是它的父亲
     */
    spl[++tot].v = v; 
    spl[tot].fa = fa; 
    spl[tot].rep = spl[tot].sz = 1;
    return tot;
}

bool ident(int x) {
    /** 判断左儿子右儿子
     *  右儿子返回1 左儿子返回0
     */
    return x == rs(fa(x));
}

void connect(int x, int f, int k) {
    /** 建立父子关系
     * x 认 f 为父亲， x 是 f 的 k 儿子
     */
    spl[f].ch[k] = x;
    fa(x) = f;
}

void update(int x) {
    /** 重新计算 sz */
    spl[x].sz = spl[ls(x)].sz + spl[rs(x)].sz + spl[x].rep;
}

void rotate(int x) {
    /** 旋转 x 节点：
     *      如果 x 是左儿子就右旋，如果x是右儿子就左旋
     */
    int f = fa(x), ff = fa(f), k = ident(x);
    connect(spl[x].ch[k^1], f, k); // 1
    connect(x, ff, ident(f));  // 2   (2,3)顺序不能反,因为2要用到 ident(f) 不能先把f 更新了
    connect(f, x, k^1);         // 3
    update(f); update(x);
}

void splay(int x, int top) {
    /** 旋转x到to位置 */
    int to = fa(top); // 找到那个位置的爸爸
    while (fa(x) != to) { // 只要我的爸爸不是 to的爸爸，就要一直转
        if (fa(fa(x)) == to) rotate(x); // 只差一步就到了
        else if (ident(x) == ident(fa(x))) { rotate(fa(x)); rotate(x); } // 链情况
        else rotate(x), rotate(x);
    }
}

void ins(int v) {
    /** 插入一个结点，值为 v */
    int x = root;
    if (!x) { root = newnode(v, 0); return; }
    while (true) {
        if (spl[x].v == v) { spl[x].rep++; splay(x, root); return; } // 值重复情况
        int nxt = v < spl[x].v ? 0 : 1; // 去左子树还是右子树
        if (!child) {  child = newnode(v, x); splay(child, root); return; } // 跟新根
        x = child;
    }
}

int find(int v) {
    /** 查找值 v 是否存在，存在返回结点编号 */
    int x = root;
    while (true) {
        if (!x) return 0; // 找不到的情况
        if (spl[x].v == v) { splay(x, root); return x; }
        int nxt = v < spl[x].v ? 0 : 1;
        x = child;
    }
}

void del(int v) {
    /** 删除一个结点 */
    int x = find(v);
    if (!x) return; // 删除结点不存在
    if (spl[x].rep > 1) { spl[x].rep--; spl[x].sz--; return; } // 删除重复数据
    else if (!ls(x) && !rs(x)) { root = 0; return; } // 只剩一个点
    else if (!ls(x)) { root = rs(x); fa(rs(x)) = 0; return; } // 没有前驱
    else {  // 有前驱
        int u = ls(x);   
        while (rs(u)) u = rs(u); // 找到前驱
        splay(u, ls(x)); // 转到x的左儿子
        connect(rs(x), u, 1);
        connect(u, 0, 1); // 变成根
        update(u); // 重建父子关系后要更新
    }
}

int rk(int v) {
    /** 查询一个数的排名 */
    int p = find(v);
    return spl[ls(p)].sz + 1;
}

template<typename T>
T kth(int k) { 
    /** 查询排名为 k 的数 */
    int x = root; int ret = 0;
    while (true) {
        int used = spl[x].sz - spl[rs(x)].sz;
        if (spl[ls(x)].sz < k && k <= used) { splay(x, root); return spl[x].v; }
        if (k < used) x = ls(x);
        else x = rs(x), k -= used;
    }
}

void print(int x) {
    if (!x) return;
    if (spl[x].ch[0]) print(spl[x].ch[0]);
    cout << spl[x].v << " ";
    if (spl[x].ch[1]) print(spl[x].ch[1]);
}


template<typename T>
T lower(int v) {
    /** 查找 v 的前驱 
     * 先给答案赋个最小值，然后不断提升它
    */
    int x = root; T ret = INT_MIN;
    while (x) {
        if (spl[x].v < v && spl[x].v > ret) ret = spl[x].v; // 取最大值  
        int nxt = v <= spl[x].v ? 0 : 1; // 这里是 <= 
        x = child;
    }
    return ret;
}

template<typename T>
T upper(int v) {
    /** 查找 v 的后继 */
    int x = root; T ret = INT_MAX;
    while (x) {
        if (spl[x].v > v && spl[x].v < ret) ret = spl[x].v;
        int nxt = v < spl[x].v ? 0 : 1; // 这里 <
        x = child;
    }
    return ret;
}

int main() {
    freopen("d.txt","r",stdin);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1;i <= n; ++i) {
        int x, op; cin >> op >> x;
        if (op == 1) ins(x);
        if (op == 2) del(x);
        if (op == 3) cout << rk(x) << endl;
        if (op == 4) cout << kth<int>(x) << endl;
        if (op == 5) cout << lower<int>(x) << endl;
        if (op == 6) cout << upper<int>(x) << endl;  
    }
    return 0;
}

Splay的应用

  1. 求 \(min\{A[i] - k\}\) 的最小值

就是在splay里求 \(k\) 的前驱后继,或者自己

营业额统计

宠物收养厂

单调栈

模板: 求右边第一个比自己大的元素的index

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e6 + 5;
typedef long long ll;

int n, m;
int A[maxn], ans[maxn], st[maxn], tp;

inline bool isempty() {
    return tp == 0;
}

inline int top() {
    return st[tp];
}

inline void push(int x) {
    st[++tp] = x;
}

inline void pop() {
   --tp;
}

int main() {
    freopen("d.txt","r",stdin);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1;i <= n; ++i) cin >> A[i];
    for (int i = n; i >= 1; --i) {
        while (!isempty() && A[top()] <= A[i]) pop();
        ans[i] = isempty() ? 0 : top();
        push(i);
    }

    for (int i = 1;i <= n; ++i) cout << ans[i] << " ";
    cout << endl;
    return 0;
}

差分

入门博客：

https://www.luogu.com.cn/blog/RPdreamer/ci-fen-and-shu-shang-ci-fen

https://www.cnblogs.com/RabbitHu/p/BIT.html

https://www.luogu.com.cn/blog/Chanis/super-BIT

差分支持离线修改，查询。

差分用 \(O(n)\) 的时间来维护，\(O(1)\) 的时间来查询。

注意点

  • 差分的左区间必须严格统计，否则会出错

    见 Lycanthropy

位运算

img

快速fft

https://www.cnblogs.com/zwfymqz/p/8244902.html

习题

逆序对

1430E String Reversal

题意

只能交互字符串相邻位置，求将一个字符串逆置的最小操作次数。

分析

求倒置的次数的一个常用思路是。把原来字符串的位置编号，然后倒置之后求逆序对的数量。但是本题只能交换相邻位置，广义的逆序对是可以交换任意位置的。但是，我们只要使得交换相邻位置的时候保证一定会消除一个逆序对，那么就可以直接求。那么怎样是保证消除一个逆序对呢。比如字符串 \(caba\) 反转之后 \(abac\) 那么 \(a\) 必定是最先出现的那个移过来，如果后面移过来的话肯定不是最优的，而且中间也不是每次移动都能消除逆序对。所以相同的字符在反转之后的顺序是不会发生改变的。所以我们在编号的时候，相同的字符反转后的编号是递增的。然后不同的字符根据原来的位置排列。比如 \(abac\) 编号后就是 \(2341\) ，然后我们求这个序列的逆序对即可

代码

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
#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int) (x).size())
#define len(x) ((int) (x).length())
typedef pair<int, int> pii;
typedef long long ll;
const int maxn = 5e5 + 5;
template<class T> void print(T & x){ cout << x; }
template<class T,class U> void print(pair<T,U> & p){cout << "("; print(p.first); cout << ", "; print(p.second); cout << ")"; }
template<class T> void print(vector<T> & v) {
    cout << "{";
    if (sz(v)) print(v[0]);
    for (int i = 1; i < sz(v); i++) cout << ", ", print(v[i]);
    cout << "}\n";
}

int n;
int sumv[maxn*4];

#define mid ((l+r)>>1)
#define ls (o<<1)
#define rs (o<<1|1)

void insert(int o, int l, int r, int x) {
    if (l == r) sumv[o]++;
    else {
        if (x <= mid) insert(ls, l, mid, x);
        else insert(rs, mid+1, r, x);
        sumv[o] = sumv[ls] + sumv[rs];
    } 
}

ll query(int o, int l, int r, int ql, int qr) {
    if (l > r) return 0;
    if (ql <= l && r <= qr) return sumv[o];
    else {
        ll ret = 0;
        if (ql <= mid) ret += query(ls, l, mid, ql, qr);
        if (qr > mid) ret += query(rs, mid+1, r, ql, qr); 
        return ret;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    string s, res;
    vector<int> B(n);
    vector<int> cnt(26);
    vector<vector<int>> num(26, vector<int>());
    
    cin >> s; res = s; reverse(res.begin(), res.end());
    for (int i = 0;i < len(s); ++i) num[s[i] - 'a'].push_back(i);
    
    for (int c = 0;c < 26; ++c) {
        for (int i = 0;i < len(res); ++i) {
            if (res[i] == c + 'a') B[i] = num[c][cnt[c]++];
        }
    } 
    ll ans = 0;
    for (int i = 0;i < len(res); ++i) {
        ans += query(1, 0, n-1, B[i]+1, n-1);
        insert(1, 0, n-1, B[i]);
    }
    cout << ans << endl;
    return 0;
}

Trie

1416C Xor Inverse

题意

给定一个数组，求最小的 \(x\) 使得 \(x\) 异或数组中的每个元素后，逆序对最小

分析

可以用二进制的角度考虑，从高位往地位贪心。考虑当前的位，因为当前位是 \(0\) 的肯定比是 \(1\) 的小。那么求一下逆序对，就可以知道。如果 \(x\) 这一位是 \(0\) ，就是不变，如果是 \(1\) ，那么就是顺序对和逆序对交换。发现只要前缀相同，每一位的答案互相不影响。所以我们把所有数组插入 \(01-Trie\) 里面，递归把每一位的顺序对和逆序对加起来。然后从高位到底位看，如果逆序对比顺序对大，那么就需要变。

PS： 这个方法可以用来求逆序对。还可以支持修改。

代码

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
#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int) (x).size())
typedef pair<int, int> pii;
typedef long long ll;
const int maxn = 3e5 + 5;
#define _ <<" "<<

template<class T> void print(T & x){ cout << x; }
template<class T,class U> void print(pair<T,U> & p){cout << "("; print(p.first); cout << ", "; print(p.second); cout << ")"; }
template<class T> void print(vector<T> & v) {
    cout << "{";
    if (sz(v)) print(v[0]);
    for (int i = 1; i < sz(v); i++) cout << ", ", print(v[i]);
    cout << "}\n";
}


int n, m, tot;
int ch[maxn*33][2], val[maxn*33];
ll sum[33][2];
vector<int> num[maxn*33]; 
int ans;
ll anssum;
void insert(int x, int ind) {
    int u = 0;
    for (int i = 31; i >= 0; --i) {
        bool nxt = (x & (1 << i)) > 0;
        if (!ch[u][nxt]) ch[u][nxt] = ++tot;
        u = ch[u][nxt];
        num[u].push_back(ind);
    }
    val[u]++;
}

void dfs(int u, int pos) {
    if (sz(num[ch[u][0]]) && sz(num[ch[u][1]])) {
        ll iv = 0;
        for (auto x : num[ch[u][0]]) {
            ll k = lower_bound(num[ch[u][1]].begin(), num[ch[u][1]].end(), x) - num[ch[u][1]].begin() ;
            iv += k;
        }   
        ll another = (ll)sz(num[ch[u][0]]) * sz(num[ch[u][1]]) - iv;
        sum[pos][0] += iv; sum[pos][1] += another;
    }
    if (sz(num[ch[u][0]])) dfs(ch[u][0], pos - 1);
    if (sz(num[ch[u][1]])) dfs(ch[u][1], pos - 1);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1;i <= n; ++i) {
        int x; cin >> x;
        insert(x, i);
    }
    dfs(0, 31);
    for (int i = 31;i >= 0; --i) {
        if (sum[i][0] > sum[i][1]) { anssum += sum[i][1]; ans |= 1<<i; }
        else anssum += sum[i][0];
    }
    cout << anssum << " " << ans << endl;
    return 0;
}