动态RMQ问题(区间最值)的O(LogN)线段树解法–TYVJ1039忠诚2

关于静态不修改元素的O(1)查询的RMQ (Range Minimum/Maximum Query)算法区间最大最小值参见我(Comzyh)另一篇文章

用于求区间最值(RMQ问题)的O(1)算法–ST算法

先考虑一道题: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第一题(话说在机房值日的感觉~~爽！)

贴之代码:

/*
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;
}

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++;

{

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;

}

题目在这里,点下箭头展开。

描述 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

描述 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的博客

本文链接地址: 动态RMQ问题(区间最值)的O(LogN)线段树解法–TYVJ1039忠诚2

2 replies on “动态RMQ问题(区间最值)的O(LogN)线段树解法–TYVJ1039忠诚2”

Pingback： poj2777 线段树染色 | Comzyh的博客
internet marketing说道：

2014年05月3日 11:41 上午

Fantastic stuff, I redesigned my site and the serps plummeted
动态RMQ问题(区间最值)的O(LogN)线段树解法-TYVJ1039忠诚2 – The newest addition to my weekly read

回复

发表评论取消回复

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据。

动态RMQ问题(区间最值)的O(LogN)线段树解法–TYVJ1039忠诚2

赞过：

相关

2 replies on “动态RMQ问题(区间最值)的O(LogN)线段树解法–TYVJ1039忠诚2”

发表评论取消回复

共享此文章：

赞过：

相关

2 replies on “动态RMQ问题(区间最值)的O(LogN)线段树解法–TYVJ1039忠诚2”

发表评论 取消回复

发表评论取消回复