Article From:https://www.cnblogs.com/luyouqi233/p/9127342.html

https://www.lydsy.com/JudgeOnline/problem.php?id=5288

https://www.luogu.org/problemnew/show/P4436

https://loj.ac/problem/2508

Look at all the violence in Luo Valley’s solution, and even the only positive solution has been used with ingenious and ingenious skills.

So I will simply say “positive solution” (if there is a mistake, please point out orz).

Start with violence. For every point we find violence, we can find the largest interval [l, r].

An optimization: when we enter the new point, we can merge the answer interval of the point into the interval.

The next is the positive solution, first for each gate I, if the key is add (i+1, I) on the left, otherwise add (I, i+1), where the meaning of the edge is that the point can not be reached from the point of entry.

Then the topological sorting of this graph shows that the answer interval of point u must not contain a point larger than its ranking, and with the help of violence optimization, we can prove that the number of times that we need to be updated is only O (n).

But why do we need to say “initialization sequence will increase faster” in accordance with that question?

I downloaded the data to find a pit.

For points not on a topology, the updated answer interval may cover the answer intervals of the same level or even smaller points, so that the violence optimization is useless, and the complexity is degraded to O (n^2).

So weMust shrink point,The complexity of the algorithm can be guaranteed.

(In other words, it is the people who have worked so hard to get rid of the wrong solution but let the violence AC.

#include<cmath>
#include<queue>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e6+5;
inline int read(){
    int X=0,w=0;char ch=0;
    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
    while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;
}
struct node{
    int to,nxt;
}e[N];
struct data{
    int x,y;
}d[N];
int n,m,p,head[N],cnt,id,to[N];
int key[N],l[N],r[N],deg[N];
inline void add(int u,int v){
    e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;++deg[v];
}
inline bool pan(int x,int y){
    if(y<1||y>id)return 0;
    if(x<y)--y;
    return l[x]<=key[y]&&key[y]<=r[x];
}
queue<int>q;    
void dfs(){
    for(int i=1;i<=id;++i)if(!deg[i])q.push(i);
    while(!q.empty()){
        int u=q.front();q.pop();
        bool flag=1;
        while(flag){
            flag=0;
            while(pan(u,l[u]-1))l[u]=l[l[u]-1],flag=1;
            while(pan(u,r[u]+1))r[u]=r[r[u]+1],flag=1;
        }
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].to;
            if(!(--deg[v]))q.push(v);
        }
    }
}
inline void init(){
    key[n]=-1;id=1;
    for(int i=1;i<=n;++i){
        to[i]=id;
        if(key[i])l[id]=r[id]=id++;
    }--id;
    for(int i=1;i<=m;++i){
        int x=to[d[i].x],y=to[d[i].y];
        key[x]=y;
        if(x<y)add(x,x+1);
        else add(x+1,x);
    }
}
int main(){
    n=read(),m=read(),p=read();
    for(int i=1;i<=m;++i){
        d[i].x=read(),d[i].y=read();
        key[d[i].x]=d[i].y;
    }
    init();dfs();
    for(int i=1;i<=p;++i){
        int x=to[read()],y=to[read()];
        if(l[x]<=y&&y<=r[x])putchar('Y'),putchar('E'),putchar('S'),putchar('\n');
        else putchar('N'),putchar('O'),putchar('\n');
    }
    return 0;
}

+++++++++++++++++++++++++++++++++++++++++++

 +The author of this article: luyouqi233. +

 +Welcome to my blog: http://www.cnblogs.com/luyouqi233/+

+++++++++++++++++++++++++++++++++++++++++++

Similar Posts:

Leave a Reply

Your email address will not be published. Required fields are marked *