钱力古的小博客

切换主题

模板

c++
    int tree[N];
    void update(int pos, int x)
    {
      for (int i = pos; i < N; i += lowbit(i))
        	tree[i] = max(tree[i], x);
    }
    int query(int pos)
    {
      int res = 0;
      for (int i = pos; i; i -= lowbit(i))
        	res = max(res, tree[i]);
     	return res;
    }

LC315.计算右侧小于当前元素的个数

计算右侧小于 nums[i] 元素的数量，可以考虑倒序枚举，然后用树状数组维护

c++
#define lowbit(x) (x & (-x))

vector<int> tree;
int n;
void update(int pos, int x)
{
  for (int i = pos; i <= n; i += lowbit(i))
    	tree[i] += x;
}
int query(int pos)
{
  int res = 0;
  for (int i = pos; i; i -= lowbit(i))
    	res += tree[i];
 	return res;
}

vector<int> countSmaller(vector<int>& nums)
{
  n = nums.size();
  tree.resize(n + 1, 0);
  // 离散化去重
	vector<int> alls(nums);
  sort(alls.begin(), alls.end());
  alls.erase(unique(alls.begin(), alls.end()), alls.end());
  
  vector<int> cnt;
  for (int i = n - 1; i >= 0; i--)
  {
    // 下标从 1 开始
		int idx = lower_bound(alls.begin(), alls.end(), nums[i]) - alls.begin() + 1;
    cnt.push_back(query(idx - 1));
    update(idx, 1);
  }
  reverse(cnt.begin(), cnt.end());
  return cnt;
}

LC327.区间和个数

统计值位于 [lower, upper] 之内的区间和的个数，就是说 sum[j] - sum[i - 1] in [lower, upper] ，暴力做法 枚举，优化做法枚举 ，寻找 ，基于此可以考虑用树状数组维护

c++
#define lowbit(x) (x & (-x))
typedef long long LL;

vector<int> tree;
int n;
void update(int pos, int x) {
    for (int i = pos; i < n; i += lowbit(i))
        tree[i] += x;
}
int query(int pos) {
    int res = 0;
    for (int i = pos; i; i -= lowbit(i)) 
        res += tree[i];
    return res;
}

int countRangeSum(vector<int>& nums, int lower, int upper) 
{
    LL s = 0;
    vector<LL> sum;
    sum.push_back(0);
    for (int x: nums)
    {
        s += x;
        sum.push_back(s);
    }
    // 离散化去重
    set<LL> alls;
    for (LL x: sum)
    {
        alls.insert(x);
        alls.insert(x - lower);
        alls.insert(x - upper);
    }
    unordered_map<LL, int> m;
    int idx = 0;
    for (auto& x: alls) m[x] = idx ++;
    
    int res = 0;
    n = m.size() + 1;
    tree.resize(n);
    for (int i = 0; i < sum.size(); i++)
    {
        // lower ≤ preSums[r+1]−preSums[l] ≤ upper
        // preSums[r+1]−upper ≤ preSums[l] ≤ preSums[r+1]−lower
        int left = m[sum[i] - upper], right = m[sum[i] - lower];
        res += query(right + 1) - query(left);
        update(m[sum[i]] + 1, 1);
    }
    return res;
}

LC2736.最大和查询

遇到下标对 类的查询，可以考虑转换为二维坐标系中的坐标，然后思考它能不能跟前缀拉上关系，还是说要考虑任意区间（线段树） 本题用到的技巧有：树状数组存维护前缀最大值，用 map 对值进行离散化，离线查询时使用 PII 对下标进行处理。

c++
#define lowbit(x) (x & (-x))
typedef pair<int, int> PII;
typedef pair<PII, int> PIII;
class Solution {
public:
    vector<int> tr;
    int total;
    void update(int pos, int x)
    {
        for (int i = pos; i <= total; i += lowbit(i))
            tr[i] = max(tr[i], x);
    }
    int query(int pos)
    {
        int res = 0;
        for (int i = pos; i; i -= lowbit(i))
            res = max(res, tr[i]);
        return res == 0 ? -1 : res;
    }
    vector<int> maximumSumQueries(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {
        // 对所有值离散化
        map<int, int> m;
        for (int x: nums1) m[x] = 1;
        for (int x: nums2) m[x] = 1;
        for (auto& x: queries) m[x[0]] = 1, m[x[1]] = 1;
        total = m.size();
        for (auto& p: m) p.second = total --; // 值越小 映射值越大
        total = m.size();

        int n = nums1.size();
        vector<int> val;
        for (int i = 0; i < n; i++) 
        {
            val.push_back(nums1[i] + nums2[i]);
            nums1[i] = m[nums1[i]];
            nums2[i] = m[nums2[i]];
        }
        int q = queries.size();
        for (int i = 0; i < q; i++)
        {
            queries[i][0] = m[queries[i][0]];
            queries[i][1] = m[queries[i][1]];
        }

        // 树状数组
        tr.resize(total + 10);

        // 将数值点和询问点先按横坐标排序，注意相同坐标的数值点要排在询问点前面
        // 从大到小排序
        vector<PIII> vec;
        for (int i = 0; i < n; i++) vec.push_back(PIII(PII(nums1[i], nums2[i]), -val[i]));
        for (int i = 0; i < q; i++) vec.push_back(PIII(PII(queries[i][0], queries[i][1]), i));
        sort(vec.begin(), vec.end());

        vector<int> res(q);
        for (auto& p: vec)
        {
            int x = p.first.first, y = p.first.second, v = p.second;
            if (v < 0) update(y, -v);
            else res[v] = query(y);
        }
        return res;
    }
};

LC2407.最长递增子序列II

本题在LIS基础上新增限制：相邻元素差值不超过 ，最好用线段树，用树状数组的解法如下： 定义 表示以值 结尾的子序列的最大长度， 转移方程为 ，用树状数组维护 的最大值，令 即可

学习查询操作在求区间最大值的做法：设 求 最大，由于 表示 的最大值，则若 ，则 ；若 ，则

模板为：

c++
const int N = 100010;
int a[N], tr[N];
#define lowbit(x) (x & (-x))
void update(int x)
{
    for (int i = x; i < N; i += lowbit(i))
        tr[i] = max(tr[i], a[x]);
}
int query(int x, int y)
{
    int res = 0;
    while (y >= x)
    {
        res = max(res, a[y]);
        y --;
        for (; y - lowbit(y) >= x; y -= lowbit(y)) res = max(res, tr[y]);
    }
    return res;
}
class Solution {
public:
    int lengthOfLIS(vector<int>& nums, int k) {
        memset(tr, 0, sizeof tr), memset(a, 0, sizeof a);
        for (int x: nums) 
        {
            a[x] = max(a[x], query(max(1, x - k), x - 1) + 1);
            update(x);
        }
        return query(1, N - 1);
    }
};

离散化树状数组 ​

c++
class BIT {
private:
    vector<int> tree;

public:
    BIT(int n) : tree(n) {}

    void add(int x) {
        while (x < tree.size()) {
            ++tree[x];
            x += x & -x;
        }
    }

    int query(int x) {
        int res = 0;
        while (x > 0) {
            res += tree[x];
            x &= x - 1;
        }
        return res;
    }
};

class Solution {
public:
    long long numberOfPairs(vector<int> &a, vector<int> &nums2, int diff) {
        int n = a.size();
        for (int i = 0; i < n; ++i)
            a[i] -= nums2[i];
        auto b = a;
        sort(b.begin(), b.end());
        b.erase(unique(b.begin(), b.end()), b.end()); // 配合下面的二分，离散化

        long ans = 0L;
        auto t = new BIT(n + 1);
        for (int x : a) {
            ans += t->query(upper_bound(b.begin(), b.end(), x + diff) - b.begin());
            t->add(lower_bound(b.begin(), b.end(), x) - b.begin() + 1);
        }
        return ans;
    }
};

要查询下标 0 怎么办？ ​

在这题似乎把 pos 加个 1 ，不影响答案

题目为：所有子数组和的异或和

思路如下：

  • 子数组 +w^

    子数组元素和的异或和：

    • 推荐先完成 ARC092D - Two Sequences
    • 计算出前缀和数组 s。
    • 考虑所有的【两个前缀和相减】的结果，二进制从低到高第 k 位有多少个 11。
    • 例如 k=2 时，相当于减法的结果的低 33 位在 [100,111][100,111] 中。但如果只考虑前缀和的低 3 位，1000-1=111 本来应该满足条件，但是只取低 3 位就变成 0-1 了。
    • 如果前缀和 $$\ge 2^3$$，我们可以在取低 3 位后补一个 2^3，这样 1000-1=111 就是满足要求的。
    • 但是，还有可能出现 1111-1=1110 这样的情况，所以减法的结果应当在 $$[100,111]\cup [1100,1111]$$ 中。
    • 这可以用树状数组/名次树维护统计。
c++
void update(int pos, int x)
{
    for (int i = pos + 1; i < MX; i += lowbit(i))
        tr[i] += x;
}

int query(int pos)
{
    int res = 0;
    for (int i = pos + 1; i; i -= lowbit(i))
        res += tr[i];
    return res;
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        a[i] += a[i - 1];
    }
    int res = 0;
    for (int k = 0; k < 25; k++)
    {
        int l1 = 1 << k, r1 = (1 << (k + 1)) - 1, l2 = 3 << k, r2 = (1 << (k + 2)) - 1;
        int cnt = 0;
        memset(tr, 0, sizeof tr);
        
        update(0, 1); // 注意这里
        for (int i = 1; i <= n; i++)
        {
            int s = a[i] & r1;
            if (a[i] > s) s |= 1 << (k + 1);
            if (s >= l1) cnt += query(s - l1) - query(max(0, s - r1) - 1);
            if (s >= l2) cnt += query(s - l2) - query(max(0, s - r2) - 1);
            update(a[i] & r1, 1);
        }
        if (cnt & 1) res |= 1 << k;
    }
    printf("%d\n", res);
    return 0;
}

蓝桥周赛一 奇怪的线段 ​

n 个区间，q 个询问，每个询问输出有多少个区间包含点 a ，但不包含点 b 。

1 <= n, q, a, b <= 2e5

分析：假设 a < b，那么从左到右扫描整个数轴，对于 i ，把所有以 i 为左端点的右端点加到树状数组中，然后如果有询问的 a 是 i ，那么对于 b ，query(b-1) 就是区间数量（手玩一下就懂），最后把右端点为 i 的区间数量从树状数组中减掉。

由于此题 a b 的大小不定，因此需要分类讨论

c++
vector<int> L[N], R[N];
int n, q, l, r, a, b;
vector<PII> que[N];
int res[N];

int tr[N];
void add(int p, int x)
{
    for (int i = p; i < N; i += lowbit(i)) 
        tr[i] += x;
}
int query(int x)
{
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

void L_to_R()
{
    memset(tr, 0, sizeof tr);
    for (int i = 1; i < N; i++)
    {
        for (int r: L[i]) add(r, 1);
        for (auto &[b, id]: que[i])
            if (b > i) res[id] = query(b - 1);
        add(i, -R[i].size());
    }
}

void R_to_L()
{
    memset(tr, 0, sizeof tr);
    for (int i = N - 1; i; i--)
    {
        for (int l: R[i]) add(l, 1);
        for (auto &[b, id]: que[i])
            if(b < i) res[id] = query(N - 1) - query(b);
        add(i, -L[i].size());
    }
}

int main()
{
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d", &l, &r);
        L[l].push_back(r);
        R[r].push_back(l);
    }
    for (int i = 1; i <= q; i++)
    {
        scanf("%d%d", &a, &b);
        que[a].push_back({b, i});
    }
    L_to_R();
    R_to_L();
    for (int i = 1; i <= q; i++) printf("%d\n", res[i]);
    return 0;
}

离散化树状数组求 LIS 的最大子序和问题 ​

c++
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;

const int N = 100010;

int n, m;
int w[N], q[N];
LL tr[N];

int lowbit(int x)
{
    return x & -x;
}

void add(int x, LL v)
{
    for (int i = x; i <= m; i += lowbit(i))
        tr[i] = max(tr[i], v);
}

LL query(int x)
{
    LL res = 0;
    for (int i = x; i; i -= lowbit(i))
        res = max(res, tr[i]);
    return res;
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &w[i]);
    memcpy(q, w, sizeof w);
    sort(q, q + n);
    m = unique(q, q + n) - q;
    
    LL res = 0;
    for (int i = 0; i < n; i++)
    {
        int x = lower_bound(q, q + m, w[i]) - q + 1;
        LL sum = query(x - 1) + w[i];
        res = max(res, sum);
        add(x, sum);
    }
    
    printf("%lld\n", res);
    return 0;
}

树状数组二维偏序应用 ​

给你一个下标从 0 开始的正整数数组 heights ，其中 heights[i] 表示第 i 栋建筑的高度。

如果一个人在建筑 i ，且存在 i < j 的建筑 j 满足 heights[i] < heights[j] ，那么这个人可以移动到建筑 j 。

给你另外一个数组 queries ，其中 queries[i] = [ai, bi] 。第 i 个查询中，Alice 在建筑 ai ，Bob 在建筑 bi 。

请你能返回一个数组 ans ，其中 ans[i] 是第 i 个查询中，Alice 和 Bob 可以相遇的 最左边的建筑 。如果对于查询 i ，Alice 和 Bob 不能相遇，令 ans[i] 为 -1 。

c++
class Solution {
public:
    vector<int> leftmostBuildingQueries(vector<int>& heights, vector<vector<int>>& queries) {
        int n = heights.size();

        vector<array<int, 3>> vec;
        int q = queries.size();
        vector<int> ans(q, -2);
        for (int i = 0; i < q; i++) {
            int a = min(queries[i][0], queries[i][1]), b = max(queries[i][0], queries[i][1]);
            // 处理两种特殊询问
            if (a == b) ans[i] = a;
            else if (heights[a] < heights[b]) ans[i] = b;
            // 剩下的询问加入二维偏序问题
            // 注意排序方式：首先按 heights 从大到小排序，相同 heights 的询问一定要排在数据点之后
            else vec.push_back({-heights[a] - 1, i, b});
        }
        for (int i = 0; i < n; i++) vec.push_back({-heights[i], -1, i});
        sort(vec.begin(), vec.end());

        // 树状数组模板

        const int INF = 1e9;
        int tree[n + 1];
        for (int i = 1;i <= n; i++) tree[i] = INF;

        auto lowbit = [&](int x) { return x & (-x); };

        auto modify = [&](int pos, int val) {
            for (; pos <= n; pos += lowbit(pos)) tree[pos] = min(tree[pos], val);
        };

        auto query = [&](int pos) {
            int ret = INF;
            for (; pos; pos -= lowbit(pos)) ret = min(ret, tree[pos]);
            return ret;
        };

        // 利用树状数组处理二维偏序问题
        for (auto &arr : vec) {
            int tpe = arr[1], idx = arr[2];
            if (tpe == -1) modify(n - idx, idx);
            else {
                ans[tpe] = query(n - idx);
                if (ans[tpe] == INF) ans[tpe] = -1;
            }
        }
        return ans;
    }
};

Updated at:

If you have any advice, please leave a message:)

Copyright@ 2024 Ricky Daxia