正文

蓝书4.1-4.4树状数组rmq问题线段树倍增求lca(代码片段)

yyc-jack-0920  yyc-jack-0920  2022-12-20  645

关键词：

这章的数据结构题很真实

T1 排队 bzoj 1699

题目大意：

求静态一些区间的最大值-最小值

思路：

ST表裸题

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<algorithm>
 7 #include<queue>
 8 #include<vector>
 9 #define ll long long
10 #define inf 2139062143
11 #define MAXN 100100
12 using namespace std;
13 inline int read()
14 
15     int x=0,f=1;char ch=getchar();
16     while(!isdigit(ch)) if(ch==‘-‘) f=-1;ch=getchar();
17     while(isdigit(ch)) x=x*10+ch-‘0‘;ch=getchar();
18     return x*f;
19 
20 int n,q,g[MAXN],mn[MAXN][20],mx[MAXN][20];
21 int main()
22 
23     n=read(),q=read();int a,b,t;
24     for(int i=1;i<=n;i++) mn[i][0]=mx[i][0]=g[i]=read();
25     for(int j=1;j<20;j++)
26         for(int i=1;i+(1<<j)-1<=n;i++)
27             mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]),mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
28     while(q--)
29     
30         a=read(),b=read(),t=b-a+1,t=(int)log2(t);
31         printf("%d
",max(mx[a][t],mx[b-(1<<t)+1][t])-min(mn[a][t],mn[b-(1<<t)+1][t]));
32     
33

View Code

T2 选择客栈 luogu 1311

题目大意：

每个点有两个值颜色和最小消费值如果两个点对之间存在一个点最小消费值<=n

求这样的点对的个数

思路：

把每个颜色分别用链表存起来记录上一个<=p的位置

对于每个颜色分别遍历

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<algorithm>
 7 #include<queue>
 8 #include<vector>
 9 #define ll long long
10 #define inf 2139062143
11 #define MAXN 200100
12 using namespace std;
13 inline int read()
14 
15     int x=0,f=1;char ch=getchar();
16     while(!isdigit(ch)) if(ch==‘-‘) f=-1;ch=getchar();
17     while(isdigit(ch)) x=x*10+ch-‘0‘;ch=getchar();
18     return x*f;
19 
20 int n,k,p,g[MAXN],c[MAXN],tmp[60],fst[60],las,cnt,res,ans,l[MAXN],to[MAXN];
21 int main()
22 
23     n=read(),k=read(),p=read();
24     for(int i=1;i<=n;i++)
25     
26         c[i]=read(),g[i]=read();
27         if(g[i]<=p) las=i;l[i]=las;
28         if(!tmp[c[i]]) fst[c[i]]=i,tmp[c[i]]=i;
29         else to[tmp[c[i]]]=i,tmp[c[i]]=i;
30     
31     for(int i=0,pos;i<k;i++)
32     
33         pos=fst[i],cnt=1,res=0;
34         while(to[pos])
35         
36             if(to[pos]>n) break;
37             if(l[to[pos]]>=pos) res=cnt;
38             ans+=res,cnt++,pos=to[pos];
39         
40     
41     printf("%d",ans);
42

View Code

T3 最大值 bzoj 1012

题解链接

T4 花神游历各国 bzoj 3211

题解链接

T5 维护序列 bzoj 1798

bzoj4785[zjoi2017]树状数组|二维线段树

题目链接BZOJ4785题解这道题真是令人头秃==可以看出题面中的九条可怜把求前缀和写成了求后缀和，然后他求的区间和却仍然是sum[r]^sum[l-1]，实际上求的是闭区间[l-1,r-1]的区间和。什么时候[l-1,r-1]的区间和与[l,r]的想等呢？就是位... 查看详情

神犇求解…树状数组能求区间最值吗？时间复杂度是多少啊？…还有就是树状数组在求解啥问题上更有优势？

其实树状数组是可以求区间最值的。区间最值问题一般称作RMQ问题，有树状数组算法，S-T算法，以及线段树算法。对于树状数组，修改的复杂度都是O（nlogn），查询是O（logn）其优势相对于线段树，代码风格整齐，简短，相对于S... 查看详情

线段树/树状数组问题|问题集合

写在前面线段树代码实在冗长，于是乎能用树状数组直接搞的就懒得打线段树了(:溜 1.P2620[QZYZ]校门外的树描述Description校门外有很多树，有苹果树，香蕉树，有会扔石头的，有可以吃掉补充体力的……如今学校... 查看详情

rmq1(代码片段)

...，有好处也有坏处。好处是代码量比其他算法（线段树，树状数组等）稍短（又是很短），坏处是局限性太大，不如线段树灵活。它的目的是求区间最值。我们先看一道简单题。有一个序列，以及一些操作，每次操作给出一个区... 查看详情

acm算法目录

...衡二叉树 ?二叉排序树 ?线段树一维线段树二维线段树 ?树状数组一维树状数组 N维树状数组 ?字典树 ?后缀数组，后缀树 ?块状链表 ?哈夫曼树 ?桶，跳跃表 ?Trie树(静态建树、动态建树) ?AC自动机 ?LCA和RMQ问题查看详情

zjoi2017树状数组（线段树套线段树）(代码片段)

...http://uoj.ac/problem/291思路不难发现，九条カレン醬所写的树状数组，在查询区间\([1,r]\)的时候，其实在查询后缀\([r,n]\)；在查询\([l,r](l\neq1)\)的时候，则是在查询\([l-1,r-1]\)。那么在查询\([1,r]\)的时候，只需要询问\(r\)的前后缀异或... 查看详情

算法分类合集

...识别平衡二叉树二叉排序树线段树一维线段树二维线段树树状数组一维树状数组N维树状数组字典树后缀数组，后缀树块状链表哈夫曼树桶，跳跃表Trie树(静态建树、动态建树)AC自动机LCA和RMQ问题KMP算法图论基本图算法图广度优先... 查看详情

第五讲树状数组与线段树未完结(代码片段)

目录1264.动态求连续区间和【树状数组板子题】1265.数星星【树状数组变种】1270.数列区间最大值【线段树/区间内求最大值】1215.小朋友排队【树状数组】AcWing1228.油漆面积【不会扫描线】AcWing1232.三体攻击【不会三维差分】AcWing12... 查看详情

算法分类合集（转）

uva12299带循环移动的rmq（线段树）

.../vjudge.net/contest/147973#problem/C题意：传统的RMQ是一个不变的数组a求区间最值。现在要循环移动（往前移动）。分析：求区间问题，很容易想到线段树，西东就相当于单点更新。建树，有两种方案，第一种是nlogn，就是不断的更新，... 查看详情

坑

...矩阵快速幂dfs序拓扑排序背包问题并查集线段树树链剖分树状数组大模拟别错kmphashtrie树dfsbfs优先队列单调队列栈手打堆归并排序求逆序对树状数组求逆序对二分答案矩阵乘法最小生成树严格次小生成树匈牙利算法（二分图最大... 查看详情

codeforces889flettersremoving（二分+线段树||树状数组）

LettersRemoving题意：给你一个长度为n的字符串，然后进行m次删除操作，每次删除区间[l,r]内的某个字符，删除后并且将字符串往前补位，求删除完之后的字符串。题解： 1#include<set>2#include<iostream>3#include<string>4using... 查看详情

acwing243.一个简单的整数问题2树状数组线段树(代码片段)

地址 https://www.acwing.com/problem/content/description/244/给定一个长度为N的数列A，以及M条指令，每条指令可能是以下两种之一：1、“Clrd”，表示把A[l],A[l+1],…,A[r]都加上d。2、“Qlr”，表示询问数列中第l~r个数的和... 查看详情

树状数组和线段树有啥区别？

...在效率以及适用问题上的异同两者在复杂度上同级,但是树状数组的常数明显优于线段树,其编程复杂度也远小于线段树.树状数组的作用被线段树完全涵盖,凡是可以使用树状数组解决的问题,使用线段树一定可以解决,但是线段树能... 查看详情

线段树及其基本操作

...步骤：略备注：在线段树里，单点更新与单点累加和树状数组上的单点跟新有区别，树状数组还需与原数组求差值，线段树不用。线段树的区间求最值差别不大，在此贴一份A过题的最值代码，用来对比找bug。#include& 查看详情

rmq问题的四种解法

...ogn)复杂度，那么用在带修的题目上就显得捉襟见肘了。3.树状数组从下向上更新，sum改为max/min即可，但是局限性比较大吧，很少看见用树状数组求最值的题解。4.线段树是基于分治的思想来实现的，建立是o（nlogn）查询为O（logN)... 查看详情

树状数组/线段树

...任意区间(i,j)的元素和；修改任意一元素，实现快速更新树状数组树状数组的主要特点是生成一棵树，树的高度为logN。每一层的高度为k，分布在这一层的序列元素索引的二进制表达有个共同的特点，就是最低二次幂为k。子树间... 查看详情