RT 退役一年之后回来复建，发现PJ的C都切不动力（悲）

思路是利用树状数组维护区间标记（ $a_i=1$ 表示 $a_{i-1}>a_{i+1},-1$ 相反）

若某个 $i$ 被同时打上 $-1$ 和 $1$ 的标记即证明无解。否则按 $1$ 或 $-1$ 建边，按每条链最靠前的部分顺序作为跑查分约束的顺序。

code:

#include <bits/stdc++.h>
using namespace std;
inline char nc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
template <typename _Tp>
inline _Tp read(_Tp &x){
    int f=1;x=0;char ch=nc();
    while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=nc();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=nc();}
    return x*=f;
}
template <typename _Tp,typename... Args>
inline auto read(_Tp&x,Args&... args){read(x),read(args...);return make_tuple(x,args...);}
template <typename _Tp>
inline void write(_Tp n){
    if(n<0)n=-n,putchar('-');
    static char s[40],top=0;
    do s[top++]=n%10,n/=10;
    while(n);
    while(top)putchar(s[--top]^'0');
}
template <typename _Tp,typename... Args>
inline void write(const _Tp&x,const Args&... args){write(x),putchar(' '),write(args...);}
class Bit{
    private:
    #define N 100005
    int n;
    long long c[2][N];
    inline int lowbit(int x){return x&(-x);}
    inline void _add(bool flag,int x,int k){
        while(x<N)c[flag][x]+=k,x+=lowbit(x);
    }
    inline long long _ask(bool flag,int x){
        long long res=0;
        while(x)res+=c[flag][x],x-=lowbit(x);
        return res;
    }
    public:
    inline void add(int l,int r,long long k){
        _add(0,l,k);
        _add(0,r+1,-k);
        _add(1,l,l*k);
        _add(1,r+1,-k*(r+1));
    }
    inline void add(int x,long long k){
        add(x,x,k);
    }
    inline long long ask(int l,int r){
        return _ask(0,r)*(r+1)-_ask(1,r)-_ask(0,l-1)*l+_ask(1,l-1);
    }
}bit1,bit2;
int n,m,dis[300005],h[300005],l,r,top,k,now=1,f[300005],mn[300005],a[300005];
bool vis[300005];
struct Edge{
    int v,nxt;
}e[300005];
inline int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
inline void add(int u,int v){
    e[++top]={v,h[u]};
    h[u]=top;f[v]=u;mn[find(v)]=min(mn[find(v)],v);//连边的同时建链，用并查集维护每条链所延伸到的最靠前的位置
}
inline bool cmp(int a,int b){return mn[a]<mn[b];}//根据每条链所延伸到的最靠前的位置排序作为若干次查分约束的顺序
priority_queue<int>q;
int main(){
    #ifndef ONLINE_JUDGE
        #define FILE_OUTPUT
        #ifdef FILE_OUTPUT
        freopen("qed3.in","r",stdin);
        freopen("qed.out","w",stdout);
        #endif
        long long c1=clock();
    #endif
    read(n,m);
    if(n==2){cout<<"1 2";return 0;}
    for(int i=1;i<=m;i++){
        read(l,r);
        if(l<r)l==1?l++:l,r--,bit2.add(l,r,1),bit1.add(l,r,1);//从左向右传，即从l开始到r-1的左右邻居都有大小关系（l=1除外）
        else l==n?l--:l,r++,bit2.add(r,l,1),bit1.add(r,l,-1);//从右向左传，从r+1到l的左右邻居都有大小关系（l=n除外）
    }
    for(int i=1;i<=n;i++)if(abs(bit1.ask(i,i))!=bit2.ask(i,i)){cout<<"QED";return 0;}//若某个点被标记次数不等于标记和，即是该点同时要求ai-1<ai+1和ai-1>ai+1，矛盾，无解
    for(int i=1;i<=n;i++)f[i]=mn[i]=i;//并查集&链的初始化
    for(int i=1;i<=n;i++)if(bit1.ask(i,i)>0)add(i+1,i-1);//连边i+1->i-1（即i+1<i-1）
    else if(bit1.ask(i,i)<0)add(i-1,i+1);
    top=0;
    // for(int i=1;i<=n;i++)cout<<find(i)<<' ';puts("");
    // for(int i=1;i<=n;i++)cout<<mn[i]<<' ';puts("");
    for(int i=1;i<=n;i++)mn[find(i)]=min(mn[find(i)],i);//强制更新链最靠前的点
    for(int i=1;i<=n;i++)if(f[i]==i)a[++top]=i;
    sort(a+1,a+top+1,cmp);//排序，跑若干次查分约束
    // for(int i=1;i<=top;i++)cout<<a[i]<<' ';puts("");
    for(int i=1;i<=top;i++){
        dis[a[i]]=++k;q.push(a[i]);
        while(!q.empty()){
            int x=q.top();q.pop();vis[x]=0;
            for(int i=h[x];i;i=e[i].nxt)if(dis[e[i].v]<dis[x]+1&&!vis[e[i].v])dis[e[i].v]=dis[x]+1,vis[e[i].v]=1,q.push(e[i].v),k=max(k,dis[e[i].v]);
            else if(dis[e[i].v]<dis[x]+1){cout<<"QED";return 0;}
        }//查分约束过程
    }
    for(int i=1;i<=n;i++)write(dis[i]),putchar(' ');
    #ifndef ONLINE_JUDGE
        //#define DEBUG
        #ifdef DEBUG
            freopen("CON","w",stdout);
        #endif
        puts("\n--------------------------------");
        printf("Process exited after %g seconds with return value 0\n",(clock()-c1)/1000.0);
        #ifdef DEBUG
            system("pause");
        #endif
    #endif
    return 0;
}