三道线段树题解

原题链接

A Simple Problem With Integers

• 题意：给定一个数组，有两种操作：第一种操作将该数组某段都加上一个数，第二种操作询问某段数之和。数组非常大，故而采用线段树求解。
• 线段树的每个结点存储了区间的左位置，右位置；以及这段区间上的数字和。用一个标记flag来为整个区间增加一个值，直到必要的时候才将子树的区间也增加flag。
• 在为一个区间增加一个值的时候，递归地进行操作。要注意若flag需要传递给子树，不应该覆盖，而应该让子树的flag加上目前的值，再对子树进行增加操作，之后将原结点的flag清零。
  Query操作类似。
• 每次操作的时间复杂度为O(logn),故总的时间复杂度为O(qlogn)
• 代码如下

#include<iostream>
#define MAXN 100000
using namespace std;
long long int a[MAXN+1];
struct segTreeNode {
    long long int a, b;
    long long int val;
    long long int flag;
}segTree[4*MAXN+5];
void buildTree(int id, int l, int r) {
    segTree[id].a = l;
    segTree[id].b = r;
    segTree[id].flag = 0;
    if (l == r) {
        segTree[id].val = a[l];
    }
    else {
        int mid = (l + r) / 2;
        buildTree(2 * id, l, mid);
        buildTree(2 * id + 1, mid + 1, r);
        segTree[id].val = segTree[2 * id].val + segTree[2 * id + 1].val;
    }
}
void change(int id, int l, int r, int plus) {
    long long int a = segTree[id].a;
    long long int b = segTree[id].b;
    if (a >= l&&b <= r) {
        segTree[id].flag += plus;//注意是+=不是等于！可能有叠加的情况的！
        segTree[id].val += (b - a + 1)*plus;
    }
    else {
        if (segTree[id].flag != 0) {
            segTree[2 * id].flag+=segTree[id].flag;//仔细考虑flag的事情！
            segTree[2 * id + 1].flag += segTree[id].flag;
            segTree[2 * id].val += (segTree[2 * id].b - segTree[2 * id].a + 1)*segTree[id].flag;
            segTree[2 * id+1].val += (segTree[2 * id+1].b - segTree[2 * id+1].a + 1)*segTree[id].flag;
            segTree[id].flag = 0;
        }
        long long int mid = (a + b) / 2;
        if (l <= mid) change(2 * id, l, r, plus);
        if (r > mid) change(2 * id + 1, l, r, plus);
        segTree[id].val = segTree[2 * id].val + segTree[2 * id + 1].val;
    }
}
long long int query(int id, int l, int r) {
    long long int a = segTree[id].a;
    long long int b = segTree[id].b;
    if (a >= l&&b <= r) return segTree[id].val;
    else {
        if (segTree[id].flag != 0) {
            segTree[2 * id].flag+=segTree[id].flag;
            segTree[2 * id + 1].flag += segTree[id].flag;
            segTree[2 * id].val += (segTree[2 * id].b - segTree[2 * id].a + 1)*segTree[id].flag;
            segTree[2 * id + 1].val += (segTree[2 * id + 1].b - segTree[2 * id + 1].a + 1)*segTree[id].flag;
            segTree[id].flag = 0;//重要！恢复成0
        }
        long long int mid = (a + b) / 2;
        long long int ans = 0;
        if (l <= mid) ans += query(id * 2, l, r);
        if (r > mid) ans += query(id * 2 + 1, l, r);
        return ans;
    }
}
int main() {
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    buildTree(1, 1, n);
    for (int i = 0; i < q; i++) {
        char op;
        cin >> op;
        if (op == 'Q') {
            int x, y;
            cin >> x >> y;
            cout << query(1, x, y) << endl;
        }
        else {
            int x, y, plus;
            cin >> x >> y >> plus;
            change(1, x, y, plus);
        }
    }
}

K-th Number

• 题目大意：给定n个数，进行m次查询，查询其在某一区间上第k大的数。其中1 <= n <= 100 000, 1 <= m <= 5 000。
• 可以用划分树求解，划分树是一种基于线段树的数据结构，其构造过程类似于快速排序。树的第一层保存原数组，之后每一层二分，左子树中元素都比右子树中小，且每个子树中元素保有原来的顺序，直到只有一个元素为止。易知每一层的大小和原数组大小一样，且树的高度为O(log(n))，故可以用二维数组来表示划分树。
• 如何用这样的数据结构来计算某个区间上第k大的数呢？很重要的是，在每一层计算一个长为n的数组，其第i个值表示，这一层的第i个结点所在子树中，第i个结点及之前将被分入左子树的元素数目。我们记这个二维数组为sum[layer][i]。我们可以在构造划分树的过程中，用动态规划的思想，从sum[layer][i-1]计算sum[layer][i]。
  值得注意的一点是，在二分每一层的时候要考虑中间值的情况，即使有多个数等于中间值，也要保证正好是二分（左右等长或左子树只比右子树大一）。
• 在划分树构造完成，sum数组计算完毕之后考虑如何查询。不妨假设要查询的区间是askl,askr，而正在查询的这棵子树的左端是l，右端是r。由于第一次访问的是第一层的根节点，故而l<=askl<=askr<=r，接下来的递归过程中我们始终保证这一点。考虑[askl,askr]这一段上将被分到左子树的元素数目sum1，如果它大于等于k,那么说明在[askl,askr]这一段上第k个元素被分到了左子树，我们要在左子树上继续查询；如果小于k，那么我们要在右子树上继续查询。
• 递归时新的参数计算是个难点。
  考虑查询左子树的情况，记sum0为[l,askl)被分到左子树的元素数目。原先的[l,r]映射成为[l,(l+r)/2]，原先的[askl,askr]映射到左子树，变成了[l+sum0,l+sum0+sum1-1]。用新的参数递归地进行查询即可。
  类似地，对于右子树，原先的[l,r]映射成为[(l+r)/2+1,r]，原先的[askl,askr]映射成为[(l+r)/2+1+(askl-l-sum0),(l+r)/2+1+(l-r+1-sum0-sum1)-1]，k变成了k-sum1，递归地进行查询即可。
• 由于查询操作的时间复杂度为O(logn)，故总的时间复杂度为O(mlogn)
• 代码如下

#include<iostream>
#include<cstdio>
#include<algorithm>
#define MAXN 100005
#define LOGN 20
using namespace std;
int n, m;
int a[MAXN] = { 0 };            //原数组
int sorted[MAXN] = { 0 };       //记录排序后的数组
int tree[LOGN][MAXN] = { 0 };   //记录每层的元素序列
int sum[LOGN][MAXN] = { 0 };    //记录每层的[1,j]被划分到左子树的数目
void build(int layer,int l, int r) {
    int mid = (l + r) / 2;
    int lp = l;                                 //left pointer
    int rp = mid + 1;                           //right pointer
    int equalToMid = (mid - l + 1);             //为了让等于sorted[mid]的数相对均匀地分给两个子树
    /*for (int i = l; i <= mid; i++) {          //用equalToMid记录左半边等于mid的个数
        if (a[i] ==sorted[mid])
            equalToMid--;
    }*/
    for (int i = l; i <= r; i++) {
        if (i == l) sum[layer][i] = 0;
        else {
            sum[layer][i] = sum[layer][i-1];    //用dp来维护每层的sum数组
        }
        if (tree[layer][i] == sorted[mid]) {//为了让等于sorted[mid]的数相对均匀地分给两个子树
            /*if (equalToMid) {
                equalToMid--;
                sum[layer][i]++;
                tree[layer + 1][lp] = a[i];
                lp++;
            }
            else {
                tree[layer + 1][rp] = a[i];
                rp++;
            }*/
            if (lp <= mid) {
                sum[layer][i]++;
                tree[layer + 1][lp] = tree[layer][i];
                lp++;
            }
            else {
                tree[layer + 1][rp] = tree[layer][i];
                rp++;
            }
        }
        else if (tree[layer][i] < sorted[mid]){//tree[layer][i]会被分入左子树
            sum[layer][i]++;
            tree[layer + 1][lp] = tree[layer][i];
            lp++;
        }
        else {//tree[layer][i]会被分入右子树
            tree[layer + 1][rp] = tree[layer][i];
            rp++;
        }
    }
    if (l != r) {
        build(layer + 1, l, mid);
        build(layer + 1, mid + 1, r);
    }
}
int query(int layer, int l, int r, int askl, int askr,int k) {
    if (l == r) return tree[layer][l];
    int mid = (l + r) / 2;
    int sum0;                                   //[l,askl)被划分到左子树的数目
    int sum1;                                   //[askl,askr]被划分到左子树的数目
    if (l == askl) {
        sum0 = 0;
        sum1 = sum[layer][askr];
    }
    else {
        sum0 = sum[layer][askl - 1];
        sum1 = sum[layer][askr] - sum[layer][askl - 1];
    }
    if (k <= sum1) {//在左子树中查找，注意查找区间变更情况！
        //原先[l,ask1)被划分到左子树的部分肯定不在查找范围内，原先askr以后的数字也肯定不在查找范围内
        return query(layer + 1, l, mid, l+sum0, l+sum0+sum1-1, k);
    }
    else {//在右子树中查找
        //原先[l,ask1)被划分到右子树的部分(askl-l-sum0)不在查找范围内，原先askr以后的数字也肯定不在查找范围内
        //mid+1+askr-l+1-sum0-sum1
        //return query(layer + 1, mid + 1, r, mid+1+askl-l-sum0, (mid+1+askl-l-sum0)+(askr-askl+1-sum1), k - sum1);
        return query(layer + 1, mid + 1, r, mid + 1 + askl - l - sum0, mid + 1 - l - sum0 - sum1 + askr, k - sum1);
    }
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", a + i);
        tree[0][i] = a[i];
        sorted[i] = a[i];
    }
    sort(sorted + 1, sorted + n + 1);
    build(0,1, n);
    int askl, askr, k;
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &askl, &askr, &k);
        int ans = query(0, 1, n, askl, askr, k);
        printf("%d\n", ans);
    }
}

Lost Cows

• 题意：一个1..n的全排列数组，已知任一位置前比该位置的数小的数的个数，还原这个数组
• 记比每个位置小的数的个数的数组为a,不难看出ans[n]=a[n]+1，标记a[n]+1为访问过的数字。从后向前看，可以知道ans[n-1]是第a[n-1]+1个未被访问过的数字。由此可以利用双重循环，时间复杂度为O(n^2)的从后向前扫描的算法解决问题。
• 由于n<=8000，所以O(n^2)的复杂度足以解决问题。但是思考后发现，为了获知第a[n-1]+1个未被访问过的数字进行一重循环开销很大，其实可以通过线段树将时间缩减到O(nlogn)。具体做法是建立线段树，每一个区间对应一个值，这个值意味着一个区间内未被访问的数字个数。
• 两种实现的代码如下，通过时长分别为175ms与44ms

/*
    第n个人的序号就是a[i]+1，标记vis[a[i]+1]=1
    从后往前，第n-1个人的序号就是第a[n-1]个未被访问的值
    时间为O(n^2)
*/
#include<iostream>
using namespace std;
int a[10000] = { 0 };
bool vis[10000] = { 0 };
int ans[10000] = { 0 };
int main() {
    int n;
    cin >> n;
    a[1] = 0;
    for (int i = 2; i <= n; i++) {
        cin >> a[i];
    }
    vis[0] = 1;
    for (int i = n; i >= 1; i--) {
        int beg = 0;
        //while (vis[beg]!=0) beg++;//考虑a[1]的情况

        //找到第a[i]+1个未被访问的数，即ans[i]
        for (int t = 1; t <= a[i]+1; t++) {
            beg++;
            while (vis[beg]!=0) beg++;
        }
        ans[i] = beg;
        vis[beg] = 1;
    }
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << endl;
    }
}

/*
第n个人的序号就是a[i]+1，标记vis[a[i]+1]=1
从后往前，第n-1个人的序号就是第a[n-1]个未被访问的值
时间为O(n^2)
*/
#include<iostream>
using namespace std;
int a[10000] = { 0 };
bool vis[10000] = { 0 };
int ans[10000] = { 0 };
/*
    线段树[a,b]段表示此段上未被访问的数目
*/
struct node {
    int a, b;
    int val;
}tree[40000];
void build(int id, int l, int r) {
    tree[id].a = l;
    tree[id].b = r;
    tree[id].val = r - l + 1;
    if (l == r) return;
    else {
        int mid = (l + r) / 2;
        build(2 * id, l, mid);
        build(2 * id + 1, mid + 1, r);
    }
}
int query(int id, int x) {//query与change操作合而为一
    tree[id].val -= 1;
    int l = tree[id].a;
    int r = tree[id].b;
    if (l == r) return l;
    else {
        //int mid = (l + r) / 2;
        int lv = tree[2 * id].val;
        if (x > lv) {//右子树
            return query(2 * id + 1, x - lv);
        }
        else return query(2 * id, x);
    }
}
int main() {
    int n;
    cin >> n;
    a[1] = 0;
    for (int i = 2; i <= n; i++) {
        cin >> a[i];
    }
    build(1, 1, n);
    for (int i = n; i >= 1; i--) {
        ans[i] = query(1,a[i] + 1);//查找第a[i]+1个不为0的index
    }
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << endl;
    }
}