关于静态不修改元素的O(1)查询的RMQ (Range Minimum/Maximum Query)算法区间最大最小值参见我(Comzyh)另一篇文章
先考虑一道题:TYVJ1039 忠诚2 (看不了的本文末尾有题)
话说TYVJ总是喜欢出这么赤裸裸的算法题，我也喜欢。
很显然 m(m<=100000)笔账,n表示有n个问题，n<=100000 \( \Theta ( N^{2})\)的算法必然是不行的
话说ST(Sparse Table)算法不是查询O(1)么？ST算法的结构表明，ST的查询复杂度永远是O(1)的，但是动态修改基本上每次是O(NlogN)小点的，对于小更新量还可以，大量修改就不行了，事实证明，我写的动态ST算法超时3点。
这时，线段树的修改(Log N)优势就体现出来了。(因为本题更新的是点,比较特殊,是logN)
修改(Insert)时由顶而下以类似二分的方法找到最下面，然后回溯，比较刚更新的点与另一子树，求Min，更新为当前线段的Min值
这个模型比染色用的线段树简单多了，于是它成了我线段树AC第一题(话说在机房值日的感觉~~爽！)
贴之代码:
|
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 |
/* Problem: 1236 User: comzyh Memory: 240K Time: 0MS Language: C++ Result: Accepted */ #include <cstdio> #include <cstring> #include <cstdlib> int tab[101][101]; int DFN[101],LOW[101],stack[200],instack[200]; int f[101]; int belong[101]; int top,RB,RT;//栈顶,最后一个强连通分量编号,最后一个时间戳 int ein[101],eout[101],ans,ans1,ans2; int N; //Function void Tarjan(int x); int getf(int x); inline void add(int x,int y);//add x to y int main() { int i,j,to; scanf("%d",&N); memset(tab,0,sizeof(tab)); for (i=1;i<=N;i++) while (scanf("%d",&to),to) tab[i][++tab[i][0]]=to; // memset(DFN,0,sizeof(DFN)); memset(instack,0,sizeof(instack)); top=RB=RT=0; for (i=1;i<=N;i++) f[i]=i; for (i=1;i<=N;i++) if (!DFN[i]) Tarjan(i); //for (i=1;i<=N;i++)printf("%4d belong to %4d\n",i,belong[i]); memset(ein,0,sizeof(ein)); memset(eout,0,sizeof(eout)); for (i=1;i<=N;i++) if (tab[i][0]) { eout[belong[i]]=1; for (j=1;j<=tab[i][0];j++) if (getf(i)!= getf(tab[i][j]))ein[belong[tab[i][j]]]=1; } ans1=ans2=0; for (i=1;i<=RB;i++) { if (!ein[i] )ans1++; if (!eout[i])ans2++; } ans=(ans1>ans2)?ans1:ans2; if (RB==1)ans=0;//如果就一个分量,显然不用再连接 printf("%d\n%d",ans1,ans); system("pause"); } void Tarjan(int x) { int i,t;//t= top / to 多用途, stack[++top]=x; DFN[x]=LOW[x]=++RT; instack[x]=1; for (i=1;i<=tab[x][0];i++) { t=tab[x][i]; if (!DFN[t]) { Tarjan(t); if (LOW[t] < LOW[x]) LOW[x] = LOW[t]; } else if (instack[t] && DFN[t]<LOW[x]) LOW[x]=DFN[t]; } if (LOW[x] == DFN[x]) { RB++; do { t=stack[top--]; add(t,x); belong[t]=RB; instack[t]=0; }while(t != x); } } int getf(int x) { if (f[x] == x)return x; else return f[x]=getf(f[x]); } inline void add(int x,int y)//add x to y { int fx=getf(x),fy=getf(y); if (fx == fy)return ; f[fx]=fy; } |
题目在这里,点下箭头展开。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
描述 Description 老管家是一个聪明能干的人。他为财主工作了整整10年，财主为了让自已账目更加清楚。要求管家每天记k次账，由于管家聪明能干，因而管家总是让财主十分满意。但是由于一些人的挑拨，财主还是对管家产生了怀疑。于是他决定用一种特别的方法来判断管家的忠诚，他把每次的账目按1，2，3…编号，然后不定时的问管家问题，问题是这样的：在a到b号账中最少的一笔是多少？为了让管家没时间作假他总是一次问多个问题。 在询问过程中账本的内容可能会被修改 输入格式 Input Format 输入中第一行有两个数m,n表示有m(m<=100000)笔账,n表示有n个问题，n<=100000。 接下来每行为3个数字，第一个p为数字1或数字2，第二个数为x，第三个数为y 当p=1 则查询x,y区间 当p=2 则改变第x个数为y 输出格式 Output Format 输出文件中为每个问题的答案。具体查看样例。 样例输入 Sample Input 10 3 1 2 3 4 5 6 7 8 9 10 1 2 7 2 2 0 1 1 10 样例输出 Sample Output 2 0 |
原创文章，转载请注明： 转载自Comzyh的博客
Fantastic stuff, I redesigned my site and the serps plummeted
动态RMQ问题(区间最值)的O(LogN)线段树解法-TYVJ1039忠诚2 – The newest addition to my weekly read