算法笔记 | 从零开始的线段树
perm_identity  query_builder
list文章,算法  comment评论

线段树(Segment tree) 即解决区间问题的数据结构 常用于算法竞赛中
可以说是一种典型以空间换取时间的数据结构

举个栗子

区间求和问题
给定 n 个数,将会有 m 次操作
每次进行以下两种操作其中的一种:

  • 求出区间 (l,r) 内所有数的加和
  • 将位置 i 上的数增加 x

数据范围:

  • 1 <= n <= 100000
  • 1 <= l <= r <= 100000
  • 1 <= m <= 10000

时间:1000MS 空间限制:128000KB

题目链接:CodeVS 1080 线段树练习

朴素做法

就是很简单的去维护一个一维数组
每次求和操作对数组 arr[l],arr[l+1]....,arr[r] 相加处理,时间复杂度 O(m)
每次增加操作直接修改 arr[x] 时间复杂度 O(1)
最极端的情况下这道题目的时间复杂度就变成了 O(m*n)
肯定是过不去的...所以这个时候就要介绍我们今天的主角线段树了

线段树

首先看到线段树,其实我是拒绝的...
因为直接看代码的话,神仙们写的代码一个人一种写法...

先介绍一下线段树的简单实现(我知道我讲话水平不好...所以文字描述看不懂的话请结合图片和代码来看):

线段树是一颗完全二叉树
我们给定一个节点存储区间(l,r)的信息
那么这个节点的左儿子则记录区间(l,(l+r)/2)的信息 右儿子记录了区间((l+r)/2+1,r)的信息

实现这个数据存储的过程 就是一个建树的过程

首先让我们先定义一下各个函数以及所用到的变量

//宏定义方便写代码 其中 << 为位运算 <<1 相当于乘二 <<1|1相当于乘二加1
#define leftSon left,mid,curr<<1
#define rightSon mid+1,right,curr<<1|1

long long int arrSum[maxN << 2];    //使用O(4*n)的空间建树

//更新当前节点的区间和
void pushUp(int curr);
//递归建树
void buildTree(int left, int right, int curr);
//对节点 node 增加 value
void addNode(int node, int value, int left, int right, int curr);
//查询区间(leftSection,rightSection)的和
unsigned long long int querySection(int leftSection, int rightSection, int left, int right, int curr);

让我们先来模拟递推一下线段树的构建过程
首先我们将数据读入 记作原数组Array

1.png

结合题意 我们需要求的区间的和 所以节点的记录的信息就是区间的和
既有以下的结构

2.png

此时让我们思考两个问题:

  1. 如何快速简便的建立线段树
  2. 如果题目给出的数据不满足2^n 那么如何建树

这个时候就要介绍一下二叉树的数组表示方法 也是在算法竞赛中常用到的方法

3.png

通过对图的观察可以知道 对于父亲节点arrSum[x] 它的左儿子即为arrSum[x<<1] 右儿子为arrSum[x<<1|1]
此时对于这道题线段树中的任意节点arrSum[x],它的值就是arrSum[x<<1]+arrSum[x<<1|1] 也就是一个从底向上递推当前区间和的过程
而利用这种方法建树 在之后的查询更新过程中利用这种性质也规避数据不满足 2^n 时访问越界的情况
这个时候就可以写出pushUp函数了

//pushUp向上更新节点(更新curr节点的值为它的两个儿子的加和)
void pushUp(int curr) {
    arrSum[curr] = arrSum[curr << 1] + arrSum[curr << 1 | 1];
    return;
}

之后利用递归来建树 先递归到树的最下面 之后更新上一层的节点
此时建树的时间复杂度是O(nlogn)
4.png

//这里我的习惯写法是在线地去建树 直接去掉了文中的Array数组
//建树函数 left为当前的左区间 right为当前的右区间 curr为当前对应的数组下标(节点)
//调用的话就是buildTree(1,n,1) 意味着建立一个(1,n)区间的线段树 当前的数组下标(节点)为1
void buildTree(int left, int right, int curr) {
        //先计算出中值 方便后续的二分
    int mid = (left + right) >> 1;
        //如果当前的左区间等于右区间,也就是满足了(x,x)的情况,获取第x个数据并存放于对应的节点中
    if (left == right) {
        scanf("%lld", &arrSum[curr]);
        return;
    }
        //递归建左右的节点
    buildTree(leftSon);
    buildTree(rightSon);
        //建完子树之后使用pushUp函数更新当前节点的值(区间和)为左右儿子节点的加和
    pushUp(curr);
    return;
}

接下来就是对位置 i 上的数进行更改,这个过程类似于建树的过程,查找这个节点是在当前的左或者右区间上,然后二分,直到到对应的位置上,对其进行加减操作之后,在递归的过程中向上pushUp,更新对应节点的值
时间复杂度为O(logn)

5.png

//对位置为node的节点增加value的值 等同于对区间(node,node)增加value的值
//调用方法就是addNode(node,value,1,n,1)
void addNode(int node, int value, int left, int right, int curr) {
    int mid = (left + right) >> 1;
        //如果左区间等于右区间 已经到达位置 对节点进行相加操作
    if (left == right) {
        arrSum[curr] += value;
        return;
    }
        //判断要操作的节点node在自己的左右区间 并进行二分
    if (node <= mid)
        addNode(node, value, leftSon);
    else
        addNode(node, value, rightSon);
        //儿子节点已经更新完了 用新的儿子节点的数据来更新当前节点的值 注意这是一个递归的函数
    pushUp(curr);
    return;
}

接下来也就是最后一个操作了
查询区间(l,r)
时间复杂度是O(logn)

6.png

//查询区间(leftSection,rightSection)
long long int querySection(int leftSection, int rightSection, int left, int right, int curr) {
    int mid = (left + right) >> 1;
        //如果当前区间在查询范围内 返回当前区间的值
    if (leftSection <= left && right <= rightSection)
        return arrSum[curr];
    long long int ret = 0;
        //判断查询区间的范围在当前区间的左或者右侧 二分
    if (leftSection <= mid)
        ret += querySection(leftSection, rightSection, leftSon);
    if (rightSection > mid)
        ret += querySection(leftSection, rightSection, rightSon);
        //返回当前已经查询到的值
    return ret;
}

最后 附上AC代码

Accepted 46ms 2 MB

/**
 * @author    Moe_Sakiya        sakiya@tun.moe
 * @date        2018-04-08 20:43:37
 *
 */

#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>

using namespace std;

#define leftSon left,mid,curr<<1
#define rightSon mid+1,right,curr<<1|1

const int maxN = 100005;

long long int arrSum[maxN << 2];

void pushUp(int curr) {
    arrSum[curr] = arrSum[curr << 1] + arrSum[curr << 1 | 1];
    return;
}

void buildTree(int left, int right, int curr) {
    int mid = (left + right) >> 1;
    if (left == right) {
        if(left==9)
            printf("[%d]\n",curr );
        scanf("%lld", &arrSum[curr]);
        return;
    }
    buildTree(leftSon);
    buildTree(rightSon);
    pushUp(curr);
    return;
}

void addNode(int node, int value, int left, int right, int curr) {
    int mid = (left + right) >> 1;
    if (left == right) {
        arrSum[curr] += value;
        return;
    }
    if (node <= mid)
        addNode(node, value, leftSon);
    else
        addNode(node, value, rightSon);
    pushUp(curr);
    return;
}

long long int querySection(int leftSection, int rightSection, int left, int right, int curr) {
    int mid = (left + right) >> 1;
    if (leftSection <= left && right <= rightSection)
        return arrSum[curr];
    long long int ret = 0;
    if (leftSection <= mid)
        ret += querySection(leftSection, rightSection, leftSon);
    if (rightSection > mid)
        ret += querySection(leftSection, rightSection, rightSon);
    return ret;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int i, n, q, arg1, arg2, arg3;
    scanf("%d", &n);
    buildTree(1, n, 1);
    scanf("%d", &q);
    for (i = 0; i < q; i++) {
        scanf("%d", &arg1);
        switch (arg1) {
        case 1:
            scanf("%d %d", &arg2, &arg3);
            addNode(arg2, arg3, 1, n, 1);
            break;
        case 2:
            scanf("%d %d", &arg2, &arg3);
            printf("%lld\n", querySection(arg2, arg3, 1, n, 1));
            break;
        }
    }
    return 0;
}

牛客网暑期ACM多校训练营(第四场) D - Another Distinct Values
perm_identity  query_builder
listACM之路,文章  comment评论

啊 摸鱼真棒 实验室有空调 爽死了(就是蚊子有点多)

1.png

大致题意是使用1,0,-1构建一个N*N的矩阵,并且使矩阵的每行每列的和都不相等,如果存在这样的矩阵,输出"possible"并输出任意种情况,如果不存在输出"impossible"

首先在纸上模拟了一下,当N是奇数的时候是必然无解的
而当N是偶数时,我们可以先构建一个对称的矩阵,但由于对角线位置特殊,所以我们使用0填充,其余部分用1与-1填充

2.png

此时的话矩阵是关于对角线对称的,行列和存在相等,不符合题意,所以要想办法打破这种对称,所以对于对角线的另一半0的位置上可以使用其他数字来填充,则必定能构建一个合法的矩阵

3.png

附代码

Accepted 72ms 3632KB C++

/**
 * @author      Moe_Sakiya      i@tun.moe
 * @date        2018-07-30 23:58:37
 *
 */
 
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
 
using namespace std;
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t, n, i, j;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        if (n % 2 == 0) {
            printf("possible\n");
            for (i = 0; i < n; i++) {
                for (j = 0; j < i; j++) {
                    putchar('1');
                    if (j != n - 1)
                        putchar(' ');
                }
                if (j < n / 2)
                    putchar('0');
                else
                    printf("-1");
                if (j != n - 1)
                    putchar(' ');
                j++;
                for (; j < n; j++) {
                    printf("-1");
                    if (j != n - 1)
                        putchar(' ');
                }
                putchar('\n');
            }
        } else
            printf("impossible\n");
    }
    return 0;
}

牛客练习赛19 A - 托米的简单表示法
perm_identity  query_builder
listACM之路,文章  comment评论

打完比赛...
突然就想水篇文了......

1.png

官方题解给的是DFS或者树形DP...
比赛的时候突然想到的是递归
或者说是模拟栈....Emmm

将问题转化一下 每次计算矩形面积的时候 记录当前矩形"完整的"面积 然后做加和
这样就会得到白色矩形和黑色矩形的面积 做差即可得出最后的图形面积

定义递归体
传入参数为当前矩形的颜色
返回的是当前矩形的长度与宽度
如果当前是最内层的一对括号返回1
否则返回当前括号内的所有括号的长度加和加上当前递归匹配到括号的个数(两个矩形中的间隔),高度为当前递归内最高高度+1

注意下数据范围...当时用Int类型爆了...
改着改着递归就乱了...

Accepted 16ms 5460KB C++

/**
 * @author  Moe_Sakiya      i@tun.moe
 * @date    2018-06-01 20:19:54
 *
 */
  
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>
  
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
  
using namespace std;
  
struct Area {
    unsigned long long int width;
    unsigned long long int height;
    Area(void) {
        width = height = 0;
    }
};
  
unsigned long long int blackArea;
unsigned long long int whiteArea;
char str[400005];
unsigned long long int strPtr;
  
Area calArea(unsigned long long int pre) {
    //pre==0 Black else White
    //cout << strPtr << endl;
    Area ret, tmp;
    unsigned long long int blockCnt = 0;
    unsigned long long int width = 0, maxHeight = 0;
    strPtr++;
    while(str[strPtr] != ')') {
        tmp = calArea((pre + 1) % 2);
        if(pre == 0)
            whiteArea += tmp.height * tmp.width;
        else
            blackArea += tmp.height * tmp.width;
        maxHeight = max(maxHeight, tmp.height);
        width += tmp.width;
        blockCnt++;
    }
    if(str[strPtr - 1] == '(') {
        ret.width = 1;
        ret.height = 1;
    } else {
        ret.width = width + 2;
        ret.height = maxHeight + 1;
        if(blockCnt >= 2)
            ret.width += blockCnt - 1;
    }
    strPtr++;
    return ret;
}
  
 int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    unsigned long long int n;
    Area ret;
    scanf("%llu", &n);
    getchar();
    while(n--) {
        gets(str);
        gets(str);
        //INIT
        strPtr = 0;
        blackArea = whiteArea = 0;
        while(str[strPtr] != '\0') {
            ret = calArea(0);
            blackArea += ret.height * ret.width;
        }
        printf("%llu\n", blackArea - whiteArea);
    }
    return 0;
}

IPSC 1999 H - Remeo
perm_identity  query_builder
listACM之路,文章  comment3 条评论

前天团队训练赛的题...
不得不吐槽老师从哪里弄到的题...拿到手里还是.webarchieve格式...折腾了一阵才打开
真羡慕那些用Mac的土豪...QwQ(留下了贫穷的泪水)

来源 IPSC 1999

1.png
2.png

题意大致如下:
罗密欧要去打篮球,朱丽叶要去教堂,他们同时从两个起点出发,向两个不同的终点前进,所走的路径都是最短路径,问是否存在某一情况,两人在一点上相遇,存在输出相遇的时间,不存在输出-1

思路:
如果存在这种情况的话,这个点一定被两人都走过,而且是两人最短路径上的公共点
看到最短路首先想到Dijkstra算法,最短路问题解决之后就是对走过的最短路打标记,之后判断被标记的点到两人起点距离是否相同即可,看到数据范围并不是很大,直接两遍Dijkstra加上BFS标记即可,BFS时从终点开始,注意入队的判断是否是最短路径,这里我用的方法是判断当前点减去下个点的路径是否和最短路径相等

Accept 2/2 C++ 3ms 3MB:

/**
 * @author    Moe_Sakiya        i@tun.moe
 * @date    2018-05-15 17:25:06
 *
 */

#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>

using namespace std;

const int maxN = 105;
const int INF = 2333333;

struct Time {
    int pos;
    int time;
};

int disarr[maxN][maxN];
int disRomeo[maxN];
int disJuliet[maxN];
bool vis[maxN];
int n, m, sJuliet, sRemeo, eJuliet, eRemeo;

void dijkstra(int start, int dis[]) {
    int i, j, minPos, minDis;
    //Init
    for(i = 1; i <= n; i++) {
        dis[i] = disarr[start][i];
        vis[i] = false;
    }
    vis[start] = true;
    dis[start] = 0;
    //Dijkstra
    for(i = 1; i <= n; i++) {
        minDis = INF;
        for(j = 1; j <= n; j++)
            if(vis[j] == false && dis[j] < minDis) {
                minDis = dis[j];
                minPos = j;
            }
        vis[minPos] = true;
        for(j = 1; j <= n; j++)
            if(disarr[minPos][j] != INF && dis[j] > dis[minPos] + disarr[minPos][j])
                dis[j] = dis[minPos] + disarr[minPos][j];
    }
    return;
}

void BFS(int start, int dis[]) {
    Time t;
    queue<Time> que;
    int i;
    //Init
    for(i = 1; i <= n; i++)
        vis[i] = false;
    vis[start] = true;
    que.push({start, dis[start]});
    //BFS
    while(!que.empty()) {
        t = que.front();
        que.pop();
        for(i = 1; i <= n; i++)
            if(vis[i] == false && t.time - disarr[t.pos][i] == dis[i]) {
                vis[i] = true;
                que.push({i, dis[i]});
            }
    }
    //Mark
    for(i = 1; i <= n; i++)
        if(vis[i] == false)
            dis[i] = INF;
    return;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int i, j, u, v, val, ans;
    while(~scanf("%d", &n) && n != -1) {
        scanf("%d", &m);
        scanf("%d %d %d %d", &sJuliet, &eJuliet, &sRemeo, &eRemeo);
        //Init
        for(i = 1; i <= n; i++)
            for(j = 1; j <= n; j++)
                if(i == j)
                    disarr[i][j] = 0;
                else
                    disarr[i][j] = INF;
        for(i = 1; i <= n; i++)
            disJuliet[i] = disRomeo[i] = INF;
        //Scan
        for(i = 1; i <= m; i++) {
            scanf("%d %d %d", &u, &v, &val);
            disarr[u][v] = val;
            disarr[v][u] = val;
        }
        //Dijkstra
        dijkstra(sJuliet, disJuliet);
        dijkstra(sRemeo, disRomeo);
        //BFS to Mark
        BFS(eJuliet, disJuliet);
        BFS(eRemeo, disRomeo);
        //Solve
        ans = INF;
        for(i = 1; i <= n; i++)
            if(disJuliet[i] == disRomeo[i])
                ans = min(ans, disJuliet[i]);
        //Output
        if(ans == INF)
            printf("-1\n");
        else
            printf("%d\n", ans );
    }
    return 0;
}

CodeForces 977D - Divide by three, multiply by two
perm_identity  query_builder
listACM之路,文章  comment评论

CF第一次Div3的题...
因为当天晚上CF直接炸了十多分钟加上忘了注册...所以鸽了...
事后补题秒A三道...emmm果然还是我太弱了

今早上卡在这道题了....本来打算搜索....
刚好看到官方的题解....发现竟然可以这么做emmmm
CF不愧是脑洞题

来源 Codeforces Round #479 (Div. 3)

1.png
2.png

结论:
对于原序列(未被打乱的答案序列)来说,对每一个数进行整数拆分,可以得到的3的个数应该是递减的,在此基础之上在进行乘2的操作,并不影响当前元素中3的个数

以第一个样例举例
原序列:
9 3 6 12 4 8
整数拆分后3的个数
2 1 1 1 0 0

所以进行排序,将元素反复对3相除,对元素中得到的3的个数进行递减排序,对元素中3的个数相同的元素来说,递增排序

Accept GNU G++17 7.2.0 30ms 3600kB

/**
 * @author    Moe_Sakiya        i@tun.moe
 * @date    2018-05-08 18:04:10
 *
 */

#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>

using namespace std;

vector<pair<int, long long int> > arr;

int cal3(long long int tmp) {
    int ret = 0;
    while(tmp % 3 == 0) {
        tmp /= 3;
        ret++;
    }
    return ret;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    arr.resize(n);
    for(int i = 0; i < n; i++) {
        cin >> arr[i].second;
        arr[i].first = -cal3(arr[i].second);
    }
    sort(arr.begin(), arr.end());
    for(int i = 0; i < n; i++) {
        if(i != 0)
            putchar(' ');
        printf("%lld", arr[i].second);
    }
    putchar('\n');
    return 0;
}

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. ...
  7. 11