bzoj5277: [Usaco2018 Open]Out of Sorts

被tkj大爷艹爆了5555整套模拟赛都是神仙思路题

那么这题题解

还有一个神仙做法，zory巨神在考场上找规律AC，自己都不会证。。我证明了一下(然而这货还是不认可自己的做法)

按照分割点的思路，我们for循环一次，每次找到比当前点小且最远的点，ans+=j-i+1。毫无疑问，当前点的位移到该点之后停止，分割点的产生时间也就是距离。对于一个数，停下当且仅当它撞到了比他大的数，考虑计数和实际走的差别，对于两个数x,y,x在前且<y，设a是x的目标点，b是y的目标点，必有a<b，可以发现对于计数，第一次加上的是x~y y~a，第二次加上的是y~a a~b的贡献，而实际上，第一次加的是x~y y~a a~b，第二次加的是y~a，而这两个值是相等的。

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

typedef long long LL;

const LL mod=1e9+;

int read()

{

    int x=,f=;char ch=getchar();

    while(ch<''||''<ch){if(ch=='-')f=-;ch=getchar();}

    while(''<=ch&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

LL a[],up[],lw[];

LL l[],suml[],sumli[];

int main()

{

    int n,x,y;

    n=read();

    for(int i=;i<=n;i++)

        x=read(), y=read(), a[x]=y;

    //-----------------------------------------------------

    up[n-]=a[n-];for(int i=n-;i>=;i--)up[i]=max(up[i+],a[i]);

    lw[]=a[];    for(int i=;i<n;i++)   lw[i]=min(lw[i-],a[i]);

    int now=n;

    for(int i=;i<n;i++)

        while(now>lw[i])l[--now]=i;

    while(now>)l[--now]=n-;

    for(int i=n-;i>=;i--)

    {

        suml[i]=(suml[i+]+l[i])%mod;

        sumli[i]=(sumli[i+]+l[i]*(n-i)%mod)%mod;

    }

    //-----------------------------------------------------

    LL ans=,d;

    for(int i=;i<=n;i++)

    {

        d=(i*(up[i]-lw[i])*(up[i]+lw[i]+)/)%mod;

        ans=(ans+d)%mod;

        d=i*lw[i]%mod*(up[i]-lw[i])%mod;

        ans=((ans-d)%mod+mod)%mod;

        d=(sumli[lw[i]]-sumli[up[i]])%mod-(suml[lw[i]]-suml[up[i]])*(n-up[i])%mod;

        ans=((ans-d)%mod+mod)%mod;

    }

    printf("%lld\n",ans);

    return ;

}