The 2020 ICPC Asia Shenyang Regional Programming Contest

发挥很糟糕，还需继续努力。

（某些题代码不给是因为考场代码不忍直视，然后我又不想写了

[A The Grand Tournament]

solution

题面：给出一个正方形，和两条线段，问正方形内到这两条线段的距离相等的点集面积。

做法：不太想写代码。

经过画几张图，就会发现，要么在端点处相交，要么有重合部分，不然都是。而这两种，我们都可以在对应点处做垂线，那么有效区域就是垂线与正方形的交。于是就是个半平面交，但真的不想写平面几何。

[B Whispers of the Old Gods]

solution

题面：

做法：NFA 题，不太了解。

[C Mean Streets of Gadgetzan]

solution

题面：若干个 bool 变量，给出若干个条件，格式大致有四种：令某变量为真；令某变量为假；若给定的一系列变量均为真，则某变量为真；若给定的一系列变量均为真，则某变量为假。构造一方案或输出无解。

做法：类似的办法，不过注意到这题无环，所以直接按照拓扑序构造即可。

准确来说，就是将已经确定为真的点加入队列，然后按着这样来确定。若无法确定则不妨设为假。时间复杂度。

[D Journey to Un’Goro]

solution

题面：给定，希望你构造出长度为的串，使得满足的数量为奇数的区间个数最多，输出字典序前小的区间。

做法：条件等价于区间异或和为，于是考虑构造前缀异或的序列。假设有个和个，则有（包含第位），最大化。于是分奇偶，就知道的值了。注意到为偶数时的值可以互换。构造可以暴搜，字典序可以靠贪心，即先搜与前一位相等的数。比较恶心的就是，为偶数时，互换后的贪心不好处理，我就暴力地把前两百个区间拿出来排序了。。。时间复杂度。

[E Knights of the Frozen Throne]

solution

题面：个人分别有个要求，分别在时刻提出要求。你的脑子可以记住一个要求秒。每个时刻你会记住当前提出要求的人的要求，若还记得那个人的要求，就更新记忆。设当前需要重新记忆的要求个数为个，那你就要花的代价。同时，一个要求保存在你脑子里需要花的代价。注意，若正好在记忆了第秒有新的要求，也要重新记忆。问最小代价时的。（很难讲清题意，建议自己读题面）

做法：注意到有用的肯定是将两个点合并，于是的数量就是了。因此考虑枚举，注意到从小到大枚举时区间的数量是持续减少的，增加的贡献是可以直接算的。而一个点的贡献是它在作为起点时才有，那么合并两个点的贡献也可以直接开个桶记录相同点的个数来算，这也是。

瓶颈在于离散化和排序，总复杂度是。

[F Kobolds and Catacombs]

solution

题面：给一个长度为的序列，希望你将它分成最多段区间，使得每个区间排序后可以整体递增。

做法：容易想到要把最小的数放在第一个，于是最小数的位置要与第一个位置相连，贪心地，是最靠左的相连。以此类推，那么做的就是一个区间并的操作，可以用线段树维护标记。时间复杂度。

实际上，直接把数组排序后，只要每一次前缀和相等时划分出一个新区间即可。时间复杂度。

[G The Witchwood]

solution

题面：问一个数组前大数的和。

做法：签到。

[H The Boomsday Project]

solution

题面：你可以花钱买游戏币，有种购买方式，一种是用元买一个游戏币，其余的是用元买个游戏币，保质期只有天。现有个订单，分别在第天要消费个游戏币。问最少花费。

做法：注意到很小，于是设消费了个游戏币的最小代价。转移是容易的，只要处理好消费第个游戏币要在第几天即可（注意到这个顺序是固定的）。

坑（队友当时出的锅）：比较大，要做一次映射。以及未必递增，要先排序。

[I Rise of Shadows]

solution

题面：一个时钟，时针走一圈就是一天，现在给定时针走一圈要小时，分针走一圈要分钟，设，求一天中时针和分针夹角小于等于的时刻有几次。

做法：随手一推，就是，其中要求，求的个数。

我是没啥脑子，看到就写了个类欧，稍微注意下边界细节就过了。

实际上，可以直接推出答案为。

[J Descent of Dragons]

solution

题面：初始为的序列，两种操作，一是将区间内的所有值为的数加一，二是询问区间内的最大值。

做法：大致初始为没啥用，然后也可以加一和减一，jly 哥哥太强啦！

就考虑维护的线段树，那么修改操作就变成将的线段树的区间 copy 到上，查询只需要外面二分再在线段树查询即可。总时间复杂度。

不过查询和修改的复杂度不对等啊，是不是可以平衡一下优化到啊，不太会。

//2021.10.4 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=5e5+10;
namespace MAIN{
    int n,q;
    int ls[N*60],rs[N*60],rt[N],va[N*60];
    int tot;
    void build(res &rt,res l,res r){
        rt=++tot,va[rt]=r-l+1;
        if(l==r)return;
        res mid=(l+r)>>1;
        build(ls[rt],l,mid),build(rs[rt],mid+1,r);
    }
    int query(res rt,res l,res r,const res &L,const res &R){
        if(!rt)return 0;
        if(L<=l&&r<=R)return va[rt];
        res mid=(l+r)>>1,ret=0;
        if(L<=mid)ret=query(ls[rt],l,mid,L,R);
        if(R>mid)ret+=query(rs[rt],mid+1,r,L,R);
        return ret;
    }
    void copy(res &rt,res RT,res l,res r,const res &L,const res &R){
        if(!va[RT]||!RT)return;
        if(L<=l&&r<=R){rt=RT;return;}
        res now=++tot;
        ls[now]=ls[rt],rs[now]=rs[rt],va[now]=va[rt],rt=now;
        res mid=(l+r)>>1;
        if(L<=mid)copy(ls[rt],ls[RT],l,mid,L,R);
        if(R>mid)copy(rs[rt],rs[RT],mid+1,r,L,R);
        va[rt]=va[ls[rt]]+va[rs[rt]];
    }
    inline void MAIN(){
        n=read(),q=read(),build(rt[0],1,n);
        res mx=0;
        while(q--){
            res opt=read(),l=read(),r=read();
            if(opt==1){
                res x=read();
                if(x>mx)continue;
                copy(rt[x+1],rt[x],1,n,l,r),mx+=(x==mx);
            }
            else {
                res L=0,R=mx,ret=0;
                while(L<=R){
                    res mid=(L+R)>>1;
                    if(query(rt[mid],1,n,l,r))L=mid+1,ret=mid;
                    else R=mid-1;
                }
                printf("%d\n",ret);
            }
        }
    }
}

[K Scholomance Academy]

solution

题面：给出个带正负的数，对于一个数，它的第一权值定义为 $多少个绝对值不小于的正数多少个绝对值不小于的数$ ，第二权值定义为 $多少个绝对值小于的正数多少个绝对值小于的数$ 。求

$\int_0^1 \max_{x\in \mathbb{R}} \lbrace A(x)|B(x)\leq r\rbrace {\rm d}r$

做法：注意到有用的是级别的（即两个数之间夹住的区间内是一致的）。于是也只有组，那么实际上做的就是后缀最大值了。的时间复杂度。

[L Forged in the Barrens]

solution

题面：长度为的序列，对每一个，将序列分成段，使得每一段的最大值减最小值的和最大。

做法：首先要转换下题意，注意到实际上最大值减最小值这个条件不如改写成区间两个数的差的最大值，于是题意就可以改写成选取，使得最大。

接下来就有两种做法了。一种是注意到这个东西实际是个费用流模型，即向每个点连一条费用为流量为的边，每个点向连一条费用为流量为的边，然后和连一条双向的费用为流量为的边。和大部分模拟费用流的图一样，这张图也满足退流不会退掉已经选择过的点，于是每次增广就可以算出每个答案了。

那么如何模拟费用流呢？注意到每个增广都会让一个区间的边的某个方向的流量加一，另一个方向减一，这让我们想到用线段树来模拟费用流。和这里的第三十题类似，我们维护不/可能跨过最小/大流量的答案，类似地维护那么一坨信息即可。时间复杂度。当然，这题实际上将流量限制在了中，所以可以直接维护跨过这六种情况来讨论。

另一种做法就是暴力分治闵科夫斯基凸包和了。可以注意到这个费用流可以用一个更暴力的区间来维护，而根据费用流的性质，可以知道这个关于流量（选择的区间数）是凸的，然后直接分治加闵科夫斯基凸包和来维护这个的凸包即可。具体是，设表示当前算了选择了对左/右端点是当最大值还是最小值还是不做值的最大值，转移自己推一下即可。仍不能理解的可以看这篇博客。时间复杂度也是，常数是。

坑：转移时可能遇到数组多加个导致 vector 越界，建议多开一个空间。

//2022.1.14 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=2e5+10;
namespace MAIN{
    int n;
    int a[N];
    struct P{
        vector<LL> f[3][3];
        inline void init(const res &p){
            for(res i=0;i<3;i++)for(res j=0;j<3;j++)f[i][j]=vector<LL>(p,-INF);
        }
    };
    //0:-a 2:a 1:0
    P solve(res l,res r){
        P ret;
        ret.init(r-l+3);
        if(l==r){
            ret.f[0][1][0]=ret.f[1][0][0]=-a[l];
            ret.f[2][1][0]=ret.f[1][2][0]=a[l];
            ret.f[1][1][1]=ret.f[1][1][0]=0;
            return ret;
        }
#define ckmx(f,g) ((f)<(g)?(f)=(g):1)
        res mid=(l+r)>>1;
        P L=solve(l,mid),R=solve(mid+1,r);
        for(res i=0;i<3;i++)for(res j=0;j<3;j++){
            for(res k=0;k<=mid-l+1;k++)ret.f[i][j][k]=L.f[i][j][k];
            for(res k=0;k<=r-mid;k++)ckmx(ret.f[i][j][k],R.f[i][j][k]);
        }
        for(res i=0;i<3;i++)for(res j=0;j<3;j++)for(res k=0;k<3;k++)for(res o=0;o<3;o++){
            if(j+k!=2)continue;
            res fl=j!=1;
            LL now=L.f[i][j][0]+R.f[k][o][0];
            ckmx(ret.f[i][o][fl],now);
            res p1=0,p2=0;
            while(p1<mid-l+1&&p2<r-mid){
                LL t1=L.f[i][j][p1+1]-L.f[i][j][p1];
                LL t2=R.f[k][o][p2+1]-R.f[k][o][p2];
                if(t1<t2)now+=t2,p2++;
                else now+=t1,p1++;
                ckmx(ret.f[i][o][p1+p2+fl],now);
            }
            while(p1<mid-l+1)now+=L.f[i][j][p1+1]-L.f[i][j][p1],p1++,ckmx(ret.f[i][o][p1+p2+fl],now);
            while(p2<r-mid)now+=R.f[k][o][p2+1]-R.f[k][o][p2],p2++,ckmx(ret.f[i][o][p1+p2+fl],now);
        }
        return ret;
    }
    inline void MAIN(){
        n=read();
        for(res i=1;i<=n;i++)a[i]=read();
        P ans=solve(1,n);
        for(res k=1;k<=n;k++)printf("%lld\n",ans.f[1][1][k]);
    }
}