JOISC2024 题解

Day1 T1 Fish 3

题意

有一个 n 个数的序列，初始全为 0。给定常数 D 和一个目标序列 a，q 次查询区间 [l,r] 能否通过下面的两种操作变成目标序列的 [l,r] 子段，如能输出操作 1 执行次数的最小值。操作1：选择一个位置，将它的值增加 D。操作2：给一个后缀每个位置的值增加 1。n,q\le 3\times 10^5。

思路

先进行操作1之后只要让 [l,r] 单调不降即可。由于想使得操作1执行次数最少，所以可以从后向前贪心。为了尽可能合法，最后一个位置一定是越大越好，而较大的最终值意味着较少的操作1，这是相吻合的。所以一个暴力就是从后往前扫描，假设上一个元素为 x，当前元素为 y，则这一步必须做的操作1次数就是 \max(0,\lceil\frac{y-x}D\rceil)。只要判定最后 l 位置的值是否非负即可判定是否合法，如合法则输出答案。这样做复杂度为 O(nq)。

考虑优化，先将序列翻转这样从前往后扫更好看一些。可以先预处理出序列 v_i=\lceil\frac{a_{i+1}-a_i}D\rceil 表示若 i 操作完了之后，那么 i+1 需要比 i 多操作多少次。注意这里是忽略和 0 取 \max 的限制的。设 s 为 v 的前缀和序列，那么此时如果没有这个限制，则答案就是 \displaystyle\sum_{i=l}^r s_i-s_l，可以直接处理。下面考虑加入 0 这个限制怎么办。注意到可以将 v_i 画成折线，则相当于需要把所有 <0 的点后面的部分平移上去。那么一个 s_i<s_l 的位置 i 对答案产生的影响就是 (s_l-s_i)(r-i+1)。然而在这之后 s_i 会变成新的水平线，所以下一次应当找的是第一个 s_j<s_i 的位置 j，对答案的影响为 (s_i-s_j)(r-j+1)。注意到找到一个 i 后下一个 j 和 l,r 无关，所以可以预处理 nxt_i 表示下一个 s_j<s_i 的 j。则可以看作一个 i 对答案的影响为 (s_i-s_{nxt_i})(r-nxt_i+1)，这个等于 w_1(i)+r\times w_2(i)，其中 w_1(i),w_2(i) 只和 i 有关。那么我们一次查询相当于就是从 l 向后跳 nxt 直到跳出 r，对所有经过的 i 求和即可。这个显然可以倍增实现。而判定合法只需要知道整个折线的最小值，就是倍增跳到的最后一个点。这样就做完了，复杂度 O(n\log n)​。

#include <bits/stdc++.h>
#define INF 1000000000
#define LINF 1000000000000000000
#define MOD 1000000007
#define mod 998244353
#define F first
#define S second
#define ll long long
#define N 300010
using namespace std;
ll n,q,d,a[N],v[N],s[N],nxt[N],sum[N],sum1[20][N],sum2[20][N],f[20][N];
int main(){
    ll i,j;
    scanf("%lld%lld",&n,&d);
    for(i=0;i<n;i++)
    {
        scanf("%lld",&a[i]);
    }
    reverse(a,a+n);
    for(i=0;i+1<n;i++)
    {
        __int128 qwq=((__int128)(a[i+1]-a[i]+d-1)+(__int128)LINF*(__int128)d)/(__int128)d;
        v[i]=(ll)(qwq-LINF);
        s[i+1]=s[i]+v[i];
    }
    for(i=1;i<n;i++)
    {
        sum[i]=sum[i-1]+s[i];
    }
    stack<ll> stk;
    stk.push(n);
    for(i=n-1;i>=0;i--)
    {
        while(stk.size()>1)
        {
            ll x=stk.top();
            if(s[x]<s[i])
            {
                break;
            }
            stk.pop();
        }
        nxt[i]=stk.top();
        stk.push(i);
    }
    for(i=0;i<n;i++)
    {
        sum1[0][i]=s[i]-s[nxt[i]];
        sum2[0][i]=(s[i]-s[nxt[i]])*nxt[i];
        f[0][i]=nxt[i];
    }
    f[0][n]=n;
    for(i=1;i<20;i++)
    {
        for(j=0;j<=n;j++)
        {
            sum1[i][j]=sum1[i-1][j]+sum1[i-1][f[i-1][j]];
            sum2[i][j]=sum2[i-1][j]+sum2[i-1][f[i-1][j]];
            f[i][j]=f[i-1][f[i-1][j]];
        }
    }
    scanf("%lld",&q);
    while(q--)
    {
        ll l,r,i;
        scanf("%lld%lld",&l,&r);
        l=n-l,r=n-r;
        swap(l,r);
        ll ans=0,x=l;
        for(i=19;i>=0;i--)
        {
            if(f[i][x]<=r)
            {
                ans+=sum1[i][x]*(r+1);
                ans-=sum2[i][x];
                x=f[i][x];
            }
        }
        ans+=sum[r]-sum[l];
        ans-=(r-l)*s[l];
        if(a[r]-(s[r]-s[x])*d<0)
        {
            puts("-1");
        }
        else
        {
            printf("%lld\n",ans);
        }
    }
    return 0;
}

Day1 T2 Spy 3

Day1 T3 Ski 2

题意

有 n 个点，每个点初始海拔为 h_i，可以以 k 的代价将一个点的海拔增加 1。操作完成后，以海拔最低的点为根建一棵有根树，要求满足每个点的海拔严格大于它父亲的海拔。若点 i 有 x 个儿子，则需要额外付出 \max(0,x-1)c_i 的代价。求总代价的最小值。n\le 300。

思路

如果确定了所有点的海拔，怎么连边代价最小呢？首先这个 \max(0,x-1) 就相当于是每个点有一个免费的额度。那么有一个显然的贪心想法，即按照海拔从小到大考虑，对于每个点，优先占用免费名额，如果没有了再连它能连的费用最小的点。显然这个贪心是对的，因为能连的费用最小的点一定随着海拔的增高而减小，所以在前面优先使用免费名额是更优的。这里为了方便起见不妨假设在无穷小的位置有一个 c_i=\infty 的点，这样可以避免判断是否合法的情况。

那么一个自然的想法就是按照海拔从小往大 dp，但 dp 状态怎么设计是一个问题。因此我们需要发掘一些关键的性质。首先需要注意到，如果我们按照海拔一层一层的考虑，则在任意一层考虑完的时候都不可能不存在免费名额。这是因为如果这一层没有点，那么不会占用免费名额，否则这一层的点就是新的免费名额。这也就意味着，如果按照初始海拔逐层考虑，那么对于有点的层，至少会有一个点留下。这是因为反正留下一个点也不会使得后面能用的免费名额减少，且还可能使得后面有更多的连边选择，所以一定是留下更优。且也容易发现一层的点按照 c_i 从小到大排序之后一定是优先留 c_i 较小的。

这样一来，如果我们考虑完了前 i 层，那么无论我们怎么移动，此时在前面已经固定的点中，最小的 c_i 一定就是原始局面下海拔 \le i 的点中 c_i 最小的那个。这是因为在考虑到这个点那一层的时候，无论前面移上来了多少点，它都一定是最小的一个。由于这一层至少留一个点，所以它一定会被留下。

这样就可以设计出一个 dp 了。记 dp_{i,j,k} 表示考虑完海拔 \le i 的点，当前还剩余 j 的免费名额，最后一层有 k 个点没有被选择（即需要移动到下一层）的答案。考虑转移。假设这一层有 num 个新点，那么如果 k+num\le j，则直接将这些点全留下一定更优，因为此时免费名额个数仍然是 j，且将它们移走不会更优。所以是 dp_{i,j,k}\to dp_{i+1,j,0}。否则枚举有多少个点留下，假设是 p，则一定满足 j\le p\le k+num。此时会额外产生 p-j 个需要用前面的 \min c_i 的点，然后剩余的会移到下一层，所以是 dp_{i,j,k}\to dp_{i+1,p,k+num-p}。看起来复杂度是 O(n^4)，但注意到最优策略中 p 一定不会超过当前层和上一层的 num 的较大值，所以状态数总是其实是 O(n^2) 的。实现时只要保留所有合法状态即可，这样复杂度 O(n^3)。

但这个做法还有一个小问题，就是在离散化海拔之后有可能会存在将点放在两层中间的情况。此时我们先对于高度为 x 的点在 x+1 处进行一次转移。那么此时从 x+1 开始 \min c_i 就不会变了。于是枚举这一层留下的点个数 p，则最优策略一定是将剩余的点向后拉，每一层留 p 个，直到下一个有新点的位置，或者全部放完。首先显然至少放 p 个，而如果多放了，则不如在第一层就放这些，反正它们需要的额外代价 \min c_i 是一样的。这样贡献就容易计算了，所以就做完了，复杂度 O(n^3)。

#include <bits/stdc++.h>
#define INF 1000000000
#define LINF 1000000000000000000
#define MOD 1000000007
#define mod 998244353
#define F first
#define S second
#define ll long long
#define N 310
using namespace std;
ll n,d,mnc[N<<1],num[N<<1],f[N][N],g[N][N];
vector<pair<ll,ll> > allv;
vector<ll> allt;
int main(){
    ll i,j,k,p,x,y;
    cin>>n>>d;
    memset(mnc,63,sizeof(mnc));
    for(i=0;i<n;i++)
    {
        cin>>x>>y;
        x++;
        allv.push_back(make_pair(x,y));
        allt.push_back(x);
        allt.push_back(x+1);
    }
    allt.push_back(0);
    sort(allt.begin(),allt.end());
    allt.erase(unique(allt.begin(),allt.end()),allt.end());
    for(i=0;i<allv.size();i++)
    {
        x=lower_bound(allt.begin(),allt.end(),allv[i].F)-allt.begin(),y=allv[i].S;
        mnc[x]=min(mnc[x],y);
        num[x]++;
    }
    for(i=1;i<allt.size();i++)
    {
        mnc[i]=min(mnc[i],mnc[i-1]);
    }
    memset(f,63,sizeof(f));
    f[1][0]=0;
    for(i=1;i<allt.size();i++)
    {
        for(j=0;j<=n;j++)
        {
            for(k=0;k<=n;k++)
            {
                g[j][k]=LINF;
            }
        }
        for(j=0;j<=n;j++)
        {
            for(k=0;k<=n;k++)
            {
                if(f[j][k]>=LINF)
                {
                    continue;
                }
                if(j>=k+num[i])
                {
                    g[j][0]=min(g[j][0],f[j][k]);
                }
                else
                {
                    ll lim=(i==allt.size()-1?INF:allt[i+1]-allt[i]);
                    if(mnc[i-1]<LINF)
                    {
                        g[k+num[i]][0]=min(g[k+num[i]][0],f[j][k]+(k+num[i]-j)*mnc[i-1]);
                    }
                    if(lim==1)
                    {
                        for(p=j;p<=(mnc[i-1]>=LINF?j:k+num[i]);p++)
                        {
                            g[p][k+num[i]-p]=min(g[p][k+num[i]-p],f[j][k]+(p-j)*mnc[i-1]+(k+num[i]-p)*d);
                        }
                    }
                    else
                    {
                        for(p=j;p<=(mnc[i-1]>=LINF?j:k+num[i]);p++)
                        {
                            ll v=k+num[i]-p;
                            if(p*(lim-1)<=v)
                            {
                                ll cost=f[j][k]+(p-j)*mnc[i-1];
                                cost+=p*d*(lim*(lim-1)/2);
                                cost+=(v-p*(lim-1))*lim*d;
                                g[p][v-p*(lim-1)]=min(g[p][v-p*(lim-1)],cost);
                            }
                            else
                            {
                                ll cost=f[j][k]+(p-j)*mnc[i-1],mx=v/p;
                                cost+=p*d*(mx*(mx+1)/2);
                                cost+=(v%p)*d*(mx+1);
                                g[p][0]=min(g[p][0],cost);
                            }
                        }
                    }
                }
            }
        }
        for(j=0;j<=n;j++)
        {
            for(k=0;k<=n;k++)
            {
                f[j][k]=g[j][k];
            }
        }
    }
    ll ans=LINF;
    for(i=0;i<=n;i++)
    {
        ans=min(ans,f[i][0]);
    }
    cout<<ans<<'\n';
    return 0;
}

Day2 T1 Board Game

题意

一张 n 个点的无向图上有 k 个棋子，每个棋子初始在位置 x_i。图上的点分为中转节点和终止节点两种。定义对棋子 i 做一轮操作为将它向相邻的点移动（至少移动一次），直到移到一个终止节点。现在按照 1\to k 并以此循环的顺序对每个棋子做一轮移动。对每个 t，求将棋子 1 移动到 t 所有棋子的移动距离的总和的最小值。n,k\le 5\times 10^5。

思路

我们先确定一个从 x_1\to t 的路径并让棋子 1 按照这条路径走，则其中经过的终止节点的个数是重要的。假设经过了 d 个终止节点，那么相当于其它的每个棋子都需要移动 d 轮，则我们希望其它每个棋子在移动 d 轮时的最小步数。显然每个棋子是独立的，所以我们先考察一个棋子的这个值应该怎么算。

先不管 d=0 的情况，则注意到这个值有一个显然的下界：即我们第一轮一定会将这个棋子移动到某个终止节点，那我们选择最近的一个，然后后面每一步都向外走一步就立刻回来，这样只需要 2 步，只比理论的 1 步多了一点点，所以只有走 1 步的情形可能比这种走法更优。那什么情况下可以走 1 步呢？如果有两个终止节点相邻，那当棋子走到其中一个的时候，后面就可以来回跳来达到一轮走 1 步的效果。

这种情况看起来是走到最近的一个满足这个条件的终止节点最优，但事实上并非如此。注意到前一种情况中我们走到最近的终止节点，那么路径上一定不存在终止节点，所以一步可以走完。但这种情况中有可能路径上会存在不合法的终止节点，但我们会在那里被强制停下。但假设某一条路径先走 v_1 步到达一个终止节点，再走 v_2 步到达下一个，直到走 v_s 步到达目标。先假设 d 充分大，那么这条路径上走 d 轮的代价就是 (\sum v_i)+d-s。注意到这相当于是说走一条边付出 1 的代价，经过一个终止节点付出 -1 的代价时的最短路。这个最短路可以使用多源 01bfs 来求出。因此这种情况在 d 充分大的答案就是我们求出的这个最短路加上 d。

如果 d 较小怎么办呢？如果最短路对应的 s 超过了 d，那么一定是还没有走到终止点，但按照这种算法一定不会算出来比答案更小。另一方面，如果存在另一条路径在前 d 轮比这条路径更小且已经到达了一个合法的点，那么这条路径的权值应该比我们的最短路更小，矛盾。其余情况所有更优的路径都不如最开始的以 2 的代价移动的路径更优，所以 d 小的情况也是可以处理。

因此对于一个棋子，它对答案的贡献是两种情况的最小值：2d+v_1 或 d+v_2，其中 v_1,v_2 都容易通过 bfs 求出。这个显然存在一个分界点 lim，使得前面 2d+v_1 更优而后面 d+v_2 更优。这样就容易通过差分前缀和求出每个 d 所有棋子的贡献之和了。这样我们得到了一个复杂度 O(n^2) 的做法，可以 dp 求出到达每个点经过 d 个终止节点的路径的最短路，那么对于一个 d 将其它棋子对它的贡献加到答案上即可。

然而这个看起来没法优化了。但注意到 k 较大的时候每多走一轮付出的代价是巨大的，所以看起来不应该经过很多的终止点，否则就不优了。具体来说，由于每个棋子每一轮都会付出额外的至少 1 的代价，所以每多走一轮，额外的代价至少为 k-1。假设对于一个点，从 x_1 到它最少需要经过 l 个终止点，那么对于一条实际经过 r 个终止点的路径，其长度至少要比前者短 (r-l)(k-1) 才可能更优。然而显然最短路长度不超过 n，所以只有 (r-l)(k-1)<n 才可能更优。这意味着我们 dp 的时候只需要记录比最少可能经过终止点个数多至多 O(\frac nk) 个终止点的最短路径长度即可。这样我们得到了一个 O(\frac{n^2}k) 的做法。

那么 k 较小怎么办呢？注意到如果附加贡献是一个一次函数，那么可以将斜率拆到每个终止点上。此时直接跑最短路即可，由于斜率为正所以可以直接做 dijkstra。那么注意到现在这个代价函数是一个上凸壳，有至多 O(k) 段。由于我们只关心最小值，所以如果我们取出每一段，将它无限延伸并假定这条直线就是代价函数，则一定不会比答案更优，但也显然能取到最优答案。于是做 O(k) 次 dijkstra 即可。这样就得到了一个复杂度 O(nk\log n) 的做法。

平衡一下复杂度即可，可以做到 O(n\sqrt{n\log n})。

#include <bits/stdc++.h>
#define INF 1000000000
#define LINF 1000000000000000000
#define MOD 1000000007
#define mod 998244353
#define F first
#define S second
#define ll long long
#define N 50010
using namespace std;
ll n,m,d,tp[N],plc[N],v1[N],v2[N],dis[N],dp[N][550],f[2][N<<1],ans[N];
string s;
vector<ll> vt[N];
void bfs1()
{
    ll i;
    queue<ll> qu;
    for(i=0;i<n;i++)
    {
        dis[i]=LINF;
        if(tp[i]!=-1)
        {
            dis[i]=0;
            qu.push(i);
        }
    }
    while(!qu.empty())
    {
        ll x=qu.front();
        qu.pop();
        for(i=0;i<vt[x].size();i++)
        {
            if(dis[vt[x][i]]>dis[x]+1)
            {
                dis[vt[x][i]]=dis[x]+1;
                qu.push(vt[x][i]);
            }
        }
    }
    for(i=0;i<n;i++)
    {
        v1[i]=max(tp[i]>=0?0ll:-1ll,dis[i]-2);
    }
    return;
}
void bfs2()
{
    ll i;
    deque<ll> qu;
    vector<bool> vis(n,false);
    for(i=0;i<n;i++)
    {
        dis[i]=LINF;
        if(tp[i]==1)
        {
            dis[i]=0;
            qu.push_back(i);
        }
    }
    while(!qu.empty())
    {
        ll x=qu.front();
        qu.pop_front();
        if(vis[x])
        {
            continue;
        }
        vis[x]=true;
        for(i=0;i<vt[x].size();i++)
        {
            if(dis[vt[x][i]]>dis[x]+1-(tp[x]>=0))
            {
                dis[vt[x][i]]=dis[x]+1-(tp[x]>=0);
                if(tp[x]>=0)
                {
                    qu.push_front(vt[x][i]);
                }
                else
                {
                    qu.push_back(vt[x][i]);
                }
            }
        }
    }
    for(i=0;i<n;i++)
    {
        v2[i]=dis[i];
    }
    return;
}
void solve(ll pre,ll k)
{
    ll i;
    for(i=0;i<n;i++)
    {
        dp[i][0]=dp[i][1]=LINF;
    }
    dp[plc[0]][0]=0;
    priority_queue<pair<ll,pair<ll,ll> > > pq;
    pq.push(make_pair(0,make_pair(plc[0],0)));
    while(!pq.empty())
    {
        ll x=pq.top().S.F,y=pq.top().S.S,w=-pq.top().F;
        pq.pop();
        for(i=0;i<vt[x].size();i++)
        {
            ll cost=w+(x!=plc[0]&&tp[x]>=0?k:0)+1,t=(x!=plc[0]&&tp[x]>=0);
            if(dp[vt[x][i]][y|t]>cost)
            {
                dp[vt[x][i]][y|t]=cost;
                pq.push(make_pair(-cost,make_pair(vt[x][i],y|t)));
            }
        }
    }
    for(i=0;i<n;i++)
    {
        ans[i]=min(ans[i],(k==LINF?dp[i][0]:dp[i][1])+pre);
    }
    return;
}
ll mnd[N],wei[N];
void bfs3()
{
    ll i;
    deque<ll> qu;
    vector<bool> vis(n,false);
    for(i=0;i<n;i++)
    {
        mnd[i]=INF;
    }
    qu.push_back(plc[0]);
    mnd[plc[0]]=0;
    while(!qu.empty())
    {
        ll x=qu.front();
        qu.pop_front();
        if(vis[x])
        {
            continue;
        }
        vis[x]=true;
        for(i=0;i<vt[x].size();i++)
        {
            ll w=(x!=plc[0]&&tp[x]>=0);
            if(mnd[vt[x][i]]>mnd[x]+w)
            {
                mnd[vt[x][i]]=mnd[x]+w;
                if(w==0)
                {
                    qu.push_front(vt[x][i]);
                }
                else
                {
                    qu.push_back(vt[x][i]);
                }
            }
        }
    }
    return;
}
ll c1[N],c2[N];
void solve0()
{
    ll i,j;
    for(i=1;i<d;i++)
    {
        ll lim=min(n,max(0ll,v2[plc[i]]-v1[plc[i]]));
        c1[1]+=2,c1[lim+1]-=2;
        c2[1]+=v1[plc[i]],c2[lim+1]-=v1[plc[i]];
        c1[lim+1]++;
        c2[lim+1]+=v2[plc[i]];
    }
    c1[0]=c2[0]=0;
    for(i=1;i<N;i++)
    {
        c1[i]+=c1[i-1];
        c2[i]+=c2[i-1];
    }
    bfs3();
    memset(dp,63,sizeof(dp));
    queue<pair<ll,ll> > qu;
    dp[plc[0]][0]=0;
    qu.push(make_pair(plc[0],0));
    while(!qu.empty())
    {
        ll x=qu.front().F,y=qu.front().S+mnd[x];
        qu.pop();
        for(i=0;i<vt[x].size();i++)
        {
            ll t=(x!=plc[0]&&tp[x]>=0);
            if(dp[vt[x][i]][y+t-mnd[vt[x][i]]]>dp[x][y-mnd[x]]+1&&y+t-mnd[vt[x][i]]<550)
            {
                dp[vt[x][i]][y+t-mnd[vt[x][i]]]=dp[x][y-mnd[x]]+1;
                qu.push(make_pair(vt[x][i],y+t-mnd[vt[x][i]]));
            }
        }
    }
    for(i=0;i<n;i++)
    {
        ans[i]=LINF;
        for(j=0;j<550&&j+mnd[i]<N;j++)
        {
            if(dp[i][j]<LINF)
            {
                ans[i]=min(ans[i],dp[i][j]+c1[j+mnd[i]]*(j+mnd[i])+c2[j+mnd[i]]);
            }
        }
        cout<<ans[i]<<'\n';
    }
    return;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    ll i,j,x,y;
    cin>>n>>m>>d;
    for(i=0;i<m;i++)
    {
        cin>>x>>y;
        x--,y--;
        vt[x].push_back(y);
        vt[y].push_back(x);
    }
    cin>>s;
    for(i=0;i<n;i++)
    {
        if(s[i]=='0')
        {
            tp[i]=-1;
        }
        else
        {
            tp[i]=0;
            for(j=0;j<vt[i].size();j++)
            {
                if(s[vt[i][j]]=='1')
                {
                    tp[i]=1;
                    break;
                }
            }
        }
    }
    for(i=0;i<d;i++)
    {
        cin>>plc[i];
        plc[i]--;
    }
    bfs1();
    bfs2();
    if(d>100)
    {
        solve0();
        return 0;
    }
    memset(f,63,sizeof(f));
    f[0][0]=0;
    for(i=1;i<d;i++)
    {
        ll u=(i&1)^1,v=i&1;
        for(j=0;j<=i*2;j++)
        {
            f[v][j]=LINF;
        }
        for(j=0;j<=i*2;j++)
        {
            f[v][j+2]=min(f[v][j+2],f[u][j]+v1[plc[i]]);
            f[v][j+1]=min(f[v][j+1],f[u][j]+v2[plc[i]]);
        }
    }
    memset(ans,63,sizeof(ans));
    for(i=0;i<=d*2;i++)
    {
        if(f[(d-1)&1][i]<LINF)
        {
            solve(f[(d-1)&1][i],i);
        }
    }
    solve(0,LINF);
    for(i=0;i<n;i++)
    {
        cout<<ans[i]<<'\n';
    }
    return 0;
}

Day2 T2 Tricolor Lights

Day2 T3 Growing Vegetables is Fun 5

题意

给定一个长度为 2n 的序列 a，满足 a_1\le a_2\le\cdots\le a_{n+1}，且 a_1\le a_{2n}\le a_{2n-1}\le\cdots\le a_{n+1}。给定两个长为 n 的序列 b,c。将这 2n 个 a 中的元素与 2n 个 b,c 中的元素两两配对，要求满足要么与 b 配对的元素在原序列中是一段区间，要么与 c 配对的元素是一段区间。求每对元素绝对值之差最大值的最小值。n\le 3\times 10^5。

思路

假如确定了哪些和 b 哪些和 c 匹配，则一定是从小到大配对最优，证明是容易的。不妨设和 b 匹配的是一段连续区间，且左端点满足 1\le l\le n，考虑怎么求出答案。则将 b,c 交换之后再做一次即可得到另一种情形。

二分答案，则只需要检查是否可以让每一对元素之差的绝对值都不超过这个值即可。先将 b,c 排好序，不妨设一个元素和 b 匹配，则它的限制就是和它匹配的数在 b 中形成一段区间。由于我们一定按照大小顺次匹配，所以这个区间就等价于限制了这个元素在 a 中对应区间里的大小排名在一段区间 [l,r]，那我们只需考察这个限制即可。

考虑在移动左端点的时候一个数的排名怎么变化。容易发现每次会删掉一个比它小的点，再加入一个右边的点。而右边加入的点越来越小，所以前面一段这个点的排名会一直减小 1，当加入右边第一个比它小的之后会保持不变。这样若要求这个点的排名在一段区间，那么合法的左端点也在一段区间内，且容易求出。

这样对每个点可以求出两个区间，分别表示左端点在其中的时候这个点可以和 b 匹配以及可以和 c 匹配。那么只需要找到一个位置使得所有点都要么能和 b 匹配，要么能和 c 匹配即可。注意只需要关注总数目是否为 2n 即可，这是因为每个点能否匹配首先受到区间大小的限制，所以一个 l 处两种合法的个数都至多为 n。这样就做完了，可以使用 two pointers 将二分内所有需要求的东西线性求出。复杂度 O(n\log a)。

#include <bits/stdc++.h>
#define INF 1000000000
#define LINF 1000000000000000000
#define MOD 1000000007
#define mod 998244353
#define F first
#define S second
#define ll long long
#define N 300010
using namespace std;
ll n,a[N<<1],b[N],c[N],idx[N<<1][2];
pair<ll,ll> rgl[N<<1],rgr[N<<1];
void update(ll tp,ll lim)
{
    ll i,j,l,r;
    for(i=0,j=n*2-1,l=r=0;i<n;i++)
    {
        while(l<n&&b[l]<a[i]-lim)
        {
            l++;
        }
        while(r<n&&b[r]<=a[i]+lim)
        {
            r++;
        }
        while(j>=n&&a[j]<a[i])
        {
            j--;
        }
        //i,i-1,...,i-(j-n+1),i-(j-n+1),...
        ll lo=max(l,i-(j-n+1)),hi=min(r-1,i);
        rgl[idx[i][tp]].F=i-hi;
        rgl[idx[i][tp]].S=(lo==i-(j-n+1)?i:i-lo);
    }
    for(i=0,j=n*2-1,l=r=0;i<n;i++)
    {
        while(l<n&&c[l]<a[i]-lim)
        {
            l++;
        }
        while(r<n&&c[r]<=a[i]+lim)
        {
            r++;
        }
        while(j>=n&&a[j]<a[i])
        {
            j--;
        }
        //i,i+1,...,i+(n*2-j-1),i+(n*2-j-1),...
        ll lo=max(l,i),hi=min(r-1,i+n*2-j-1);
        if(lo>hi)
        {
            rgr[idx[i][tp]].F=n;
        }
        else
        {
            rgr[idx[i][tp]].F=max(i+1,hi==i+n*2-j-1?i+1:n-(hi-i));
        }
        rgr[idx[i][tp]].S=min(n-1,n-(lo-i));
    }
    return;
}
ll d[N];
bool check(ll lim)
{
    ll i;
    update(0,lim*INF+INF/2);
    vector<ll> tmp(n*2);
    for(i=0;i<n*2;i++)
    {
        tmp[i]=a[i];
    }
    for(i=0;i<n*2;i++)
    {
        a[i]=-tmp[(i+n)%(n*2)];
    }
    for(i=0;i<n;i++)
    {
        b[i]=-b[i];
        c[i]=-c[i];
    }
    reverse(b,b+n);
    reverse(c,c+n);
    swap(b,c);
    update(1,lim*INF+INF/2);
    swap(b,c);
    reverse(b,b+n);
    reverse(c,c+n);
    for(i=0;i<n*2;i++)
    {
        a[i]=tmp[i];
    }
    for(i=0;i<n;i++)
    {
        b[i]=-b[i];
        c[i]=-c[i];
    }
    for(i=0;i<n;i++)
    {
        d[i]=0;
    }
    for(i=0;i<n*2;i++)
    {
        if(rgl[i].F<=rgl[i].S)
        {
            d[rgl[i].F]++;
            d[rgl[i].S+1]--;
        }
        if(rgr[i].F<=rgr[i].S)
        {
            d[rgr[i].F]++;
            d[rgr[i].S+1]--;
        }
    }
    for(i=0;i<n;i++)
    {
        d[i+1]+=d[i];
        if(d[i]==n*2)
        {
            return true;
        }
    }
    return false;
}
bool hahaha(ll lim)
{
    if(check(lim))
    {
        return true;
    }
    swap(b,c);
    bool ret=check(lim);
    swap(b,c);
    return ret;
}
int main(){
    ll i;
    scanf("%lld",&n);
    for(i=0;i<n*2;i++)
    {
        idx[i][0]=i;
        idx[i][1]=(i+n)%(n*2);
        scanf("%lld",&a[i]);
        a[i]=a[i]*INF+i;
    }
    for(i=0;i<n;i++)
    {
        scanf("%lld",&b[i]);
        b[i]*=INF;
    }
    for(i=0;i<n;i++)
    {
        scanf("%lld",&c[i]);
        c[i]*=INF;
    }
    sort(b,b+n);
    sort(c,c+n);
    ll l=0,r=INF;
    while(l<r)
    {
        ll mid=(l+r)>>1;
        if(hahaha(mid))
        {
            r=mid;
        }
        else
        {
            l=mid+1;
        }
    }
    printf("%lld\n",l);
    return 0;
}

Day3 T1 Card Collection

题意

有 n 张卡片排成一排，每张卡片有权值 (a_i,b_i)。一次操作中可以选择两张相邻的卡片 i,j，将它们合并成一张新的卡片。这张卡片的权值要么等于 (\max(a_i,a_j),\max(b_i,b_j))，要么等于 (\min(a_i,a_j),\min(b_i,b_j))。有 m 次询问，给定 (x,y)，问能否通过 n-1 次操作合并出一张权值为 (x,y) 的卡片。n,m\le 2\times 10^5。

思路

考虑一次询问怎么回答。注意到这两维是相对独立的，即它们不会交叉取 \min/\max，所以可以将所有 a_i>x 的 a_i 看作 1，a_i=x 的 a_i 看作 0，a_i<x 的 a_i 看作 -1，b 同理，则只需要判定能否凑出 (0,0) 即可。

先考虑一种比较简单的情形，如果上下各只有一个 0，且它们处于同一个位置，此时怎么做呢？显然这个时候左边和右边是独立的。那么我们希望左右两侧都能凑出来一个 (1,1) 或 (-1,-1)，这样才可以被 (0,0) 消去。那么一个由 1,-1 组成的连续段什么时候能凑出 (1,1) 或 (-1,-1) 呢？注意到如果我们想要凑出 (1,1)，那么可以在合并的过程中每次全部取 \max，这样一定不会更劣。从而如果两维都至少有一个 1，那么就是能合并出 (1,1) 的。否则一定有一维全是 -1，那此时显然无法合并出 (1,1)，(-1,-1) 也是同理。这样我们就得到了合并出 (1,1) 和 (-1,-1) 的充要条件。这样如果 (0,0) 的左右两侧为空或能合并出 (1,1)/(-1,-1) 就一定合法。那如果不能呢？不妨设左侧不合法，这意味着左侧所有的值全部都是 (1,-1) 或全部都是 (-1,1)。但此时左侧不管怎么合并，需要与 (0,0) 合并的时候都一定是 (1,-1) 或 (-1,1)，无论如何都会吃掉一个 0。所以我们得到了这种情形下合法的充要条件。

下面考虑较为一般的情形。首先如果有多个 0 则可以钦定其中一个为 0，然后剩下的分配为 1/-1。这样只需要讨论上下各只有一个 0 的情况。不妨设上面的 0 在下面的左侧。此时先假设上面的 0 在最开始，下面的 0 在最结尾，那么什么时候合法呢？可以分类讨论一下，如果这两个位置的另一个权值相等，例如 (0,1) 与 (1,0) 这种情形，那么可以讨论得出无论中间是什么情况，都一定可以合并出 (0,0)。否则如果权值不等，那么在中间没有点的情况下是不合法的，所以为了合法一定需要将其中一个进行翻转（例如 (0,1) 变成 (0,-1)）。另一方面，只要能够翻转一次，那么就变成了两端相等的情形，立即合法了，所以只需要关注能否完成至少一次翻转即可。假定我们要翻转 (0,1)，那么一定是需要一个 (1,-1) 才行。所以首先如果中间根本没有 (1,-1) 就直接不合法了。而如果中间存在一个 (1,-1)，可以讨论得出一定合法。具体来说，由于 (1,1),(-1,1),(-1,-1) 在和 (0,1) 操作时都能保持 (0,1) 不变，所以可以逐个将最左侧的 (1,-1) 消去，然后用这个 (1,-1) 将左端点的状态改变。注意到在左端点为 (0,1) 时右端点为 (-1,0)，那么它改变所需要的元素也是 (1,-1)。所以不需要讨论到底消去了哪一边，直接判定中间有没有 (1,-1) 即可。

下面考虑两个 0 位置不同，且左右都可能有其它数的情况。一个简单的想法就是判定通过左侧的这些数，能否将左端点变为 (0,1) 或 (0,-1)。这里我们先假定不通过右边的数进行操作。不妨假设这个位置现在是 (0,1)。根据上面的推导，在遇到一个 (1,-1) 时 (0,1) 必须变为 (0,-1)，否则必须不变。这样假如我们希望 (0,1) 保持不变，只要左边能凑出一个不是 (1,-1) 的数即可。根据最开始的推导，只要左边不全是 (1,-1) 就合法。当然如果全是 (1,-1) 那也只能变成 (0,-1)。那么什么时候可以将 (0,1) 变成 (0,-1) 呢？首先左边一定要存在一个 (1,-1)，并且在这个 (1,-1) 操作之后剩余的数还不能全是 (-1,1)，否则 (0,-1) 又得强制变回 (0,1)。因此一定是选择最靠右的 (1,-1) 最优。这样我们就可以判定一个位置能否变为 (0,1) 或 (0,-1) 了。那么可以枚举左右两个端点，再枚举通过左右两侧它们变成的状态，从而转化为上一种只有中间的数的情况，可以直接计算。

当然还有一个小问题，即我们还没有说明不可能出现仅考虑左边无法变成某个状态，但加入右边的数可以变成对应状态的情况。同样不妨假设当前是 (0,1)，如果是不能维持 (0,1) 的情形，那么左边全是 (1,-1)。但无论怎么用右边的操作，一旦和一个 (1,-1) 的合并一次那立即就变成 (0,-1) 了，所以此时在左边操作完之前用右边的进行合并没用，反而会使得后面中间的数减少，更加不可能合法。如果不能变成 (0,-1)，假如是因为 (1,-1) 前面全是 (-1,1)，那么和上一种情况一样。如果是因为没有 (1,-1)，那么可能可以借助右边的 (1,-1) 变成 (0,-1)。但此时这么干的目的一定是因为右端点是 (-1,0)，这样操作完了就即可合法了。然而这种情况下我们不动中间的这个数，保留 (0,1) 进入下一阶段判定时，中间这个 (1,-1)​ 是可以使得最终合法的，所以我们就说明了不需要考虑其它元素对判定左右两部分时的影响。

还有一个问题是多个 0 的情况怎么处理。此时只钦定两个位置为真正的 0，而其它的 0 可以看作同时是 1 和 -1。由于我们只关心形如”一些数中是否有 (x,y) 这个权值“这样的问题，所以若出现了 0，则将它看作 1 算一次，再看作 -1 计入一次贡献即可。这样直接做复杂度是 O(mn^2)。但首先判定一个位置是否能够转化这种东西可以 O(n) 完成，因为可以顺着扫过去然后动态维护每种值的最后一次出现。然后最后枚举的这个部分中，注意到固定了左右端点的状态之后，肯定是左端点尽可能靠左，右端点尽可能靠右最优，所以只用判定 O(1) 次，每次是 O(n) 的，这样复杂度就是 O(nm)​​ 了。

#include <bits/stdc++.h>
#define INF 1000000000
#define LINF 1000000000000000000
#define MOD 1000000007
#define mod 998244353
#define F first
#define S second
#define ll long long
#define N 200010
using namespace std;
ll n,m,a[N],b[N],tp[N][2];
bool pre[N][2][2],suf[N][2][2],okl0[N],okl1[N],okr0[N],okr1[N];
vector<ll> ans;
bool calc(ll l,ll r)
{
    if(l==-1||r==-1||l>=r)
    {
        return false;
    }
    ll i;
    bool hv0=false,hv1=false;
    for(i=l+1;i<r;i++)
    {
        if(tp[i][0]>=0&&tp[i][1]<=0)
        {
            hv1=true;
        }
        if(tp[i][0]<=0&&tp[i][1]>=0)
        {
            hv0=true;
        }
    }
    if(okl0[l]&&okr0[r])
    {
        return true;
    }
    if(okl1[l]&&okr1[r])
    {
        return true;
    }
    if(okl0[l]&&okr1[r]&&hv0)
    {
        return true;
    }
    if(okl1[l]&&okr0[r]&&hv1)
    {
        return true;
    }
    return false;
}
bool check(ll x,ll y)
{
    ll i,j;
    for(i=0;i<n;i++)
    {
        tp[i][0]=(a[i]==x?0:(a[i]>x?1:-1));
        tp[i][1]=(b[i]==y?0:(b[i]>y?1:-1));
    }
    memset(pre,false,sizeof(pre));
    memset(suf,false,sizeof(suf));
    for(i=0;i<n;i++)
    {
        if(tp[i][0]>=0&&tp[i][1]>=0)
        {
            pre[i][1][1]=true;
        }
        if(tp[i][0]>=0&&tp[i][1]<=0)
        {
            pre[i][1][0]=true;
        }
        if(tp[i][0]<=0&&tp[i][1]>=0)
        {
            pre[i][0][1]=true;
        }
        if(tp[i][0]<=0&&tp[i][1]<=0)
        {
            pre[i][0][0]=true;
        }
        pre[i+1][0][0]=pre[i][0][0];
        pre[i+1][0][1]=pre[i][0][1];
        pre[i+1][1][0]=pre[i][1][0];
        pre[i+1][1][1]=pre[i][1][1];
    }
    for(i=n-1;i>=0;i--)
    {
        suf[i][0][0]=suf[i+1][0][0];
        suf[i][0][1]=suf[i+1][0][1];
        suf[i][1][0]=suf[i+1][1][0];
        suf[i][1][1]=suf[i+1][1][1];
        if(tp[i][0]>=0&&tp[i][1]>=0)
        {
            suf[i][1][1]=true;
        }
        if(tp[i][0]>=0&&tp[i][1]<=0)
        {
            suf[i][1][0]=true;
        }
        if(tp[i][0]<=0&&tp[i][1]>=0)
        {
            suf[i][0][1]=true;
        }
        if(tp[i][0]<=0&&tp[i][1]<=0)
        {
            suf[i][0][0]=true;
        }
    }
    for(i=0;i<n;i++)
    {
        if(tp[i][0]==0&&tp[i][1]==0)
        {
            if(i==0||((pre[i-1][1][0]||pre[i-1][1][1])&&(pre[i-1][0][1]||pre[i-1][1][1]))||((pre[i-1][0][0]||pre[i-1][0][1])&&(pre[i-1][0][0]||pre[i-1][1][0])))
            {
                if(i==n-1||((suf[i+1][1][0]||suf[i+1][1][1])&&(suf[i+1][0][1]||suf[i+1][1][1]))||((suf[i+1][0][0]||suf[i+1][0][1])&&(suf[i+1][0][0]||suf[i+1][1][0])))
                {
                    return true;
                }
            }
        }
    }
    ll lst0=-1,lst1=-1;
    for(i=0;i<n;i++)
    {
        if(tp[i][0]==0)
        {
            okl1[i]=okl0[i]=false;
            if(tp[i][1]>=0)
            {
                if(i==0||pre[i-1][0][0]||pre[i-1][0][1]||pre[i-1][1][1])
                {
                    okl1[i]=true;
                }
                j=lst0;
                if(j>=0&&(j==0||pre[j-1][0][0]||pre[j-1][1][0]||pre[j-1][1][1]))
                {
                    okl0[i]=true;
                }
            }
            if(tp[i][1]<=0)
            {
                if(i==0||pre[i-1][0][0]||pre[i-1][1][0]||pre[i-1][1][1])
                {
                    okl0[i]=true;
                }
                j=lst1;
                if(j>=0&&(j==0||pre[j-1][0][0]||pre[j-1][0][1]||pre[j-1][1][1]))
                {
                    okl1[i]=true;
                }
            }
        }
        if(tp[i][0]>=0&&tp[i][1]<=0)
        {
            lst0=i;
        }
        if(tp[i][0]<=0&&tp[i][1]>=0)
        {
            lst1=i;
        }
    }
    lst0=lst1=n;
    for(i=n-1;i>=0;i--)
    {
        if(tp[i][1]==0)
        {
            okr1[i]=okr0[i]=false;
            if(tp[i][0]>=0)
            {
                if(i==n-1||suf[i+1][0][0]||suf[i+1][1][0]||suf[i+1][1][1])
                {
                    okr1[i]=true;
                }
                j=lst1;
                if(j<n&&(j==n-1||suf[j+1][0][0]||suf[j+1][0][1]||suf[j+1][1][1]))
                {
                    okr0[i]=true;
                }
            }
            if(tp[i][0]<=0)
            {
                if(i==n-1||suf[i+1][0][0]||suf[i+1][0][1]||suf[i+1][1][1])
                {
                    okr0[i]=true;
                }
                j=lst0;
                if(j<n&&(j==n-1||suf[j+1][0][0]||suf[j+1][1][0]||suf[j+1][1][1]))
                {
                    okr1[i]=true;
                }
            }
        }
        if(tp[i][0]>=0&&tp[i][1]<=0)
        {
            lst0=i;
        }
        if(tp[i][0]<=0&&tp[i][1]>=0)
        {
            lst1=i;
        }
    }
    ll mn0=-1,mn1=-1;
    for(i=0;i<n;i++)
    {
        if(tp[i][0]==0&&okl0[i])
        {
            mn0=i;
            break;
        }
    }
    for(i=0;i<n;i++)
    {
        if(tp[i][0]==0&&okl1[i])
        {
            mn1=i;
            break;
        }
    }
    ll mx0=-1,mx1=-1;
    for(i=n-1;i>=0;i--)
    {
        if(tp[i][1]==0&&okr0[i])
        {
            mx0=i;
            break;
        }
    }
    for(i=n-1;i>=0;i--)
    {
        if(tp[i][1]==0&&okr1[i])
        {
            mx1=i;
            break;
        }
    }
    if(calc(mn0,mx0))
    {
        return true;
    }
    if(calc(mn1,mx0))
    {
        return true;
    }
    if(calc(mn0,mx1))
    {
        return true;
    }
    if(calc(mn1,mx1))
    {
        return true;
    }
    return false;
}
int main(){
    ll i,x,y;
    scanf("%lld%lld",&n,&m);
    for(i=0;i<n;i++)
    {
        scanf("%lld%lld",&a[i],&b[i]);
    }
    for(i=0;i<m;i++)
    {
        scanf("%lld%lld",&x,&y);
        if(check(x,y))
        {
            ans.push_back(i);
        }
        else
        {
            swap(x,y),swap(a,b);
            if(check(x,y))
            {
                ans.push_back(i);
            }
            swap(x,y),swap(a,b);
        }
    }
    for(i=0;i<ans.size();i++)
    {
        printf("%lld ",ans[i]+1);
    }
    puts("");
    return 0;
}

Day3 T2 JOI Tour

目前只有 71 分的，满分先咕着。

题意

给定一棵 n 个点的树，点有颜色 0,1,2。q 次操作，每次修改一个点的颜色，随后查询有多少个三元组 (i,j,k) 满足 i 颜色为 0，j 颜色为 1，k 颜色为 2 且 j 在 i\to k 的路径上。强制在线。n\le 2\times10^5,q\le 5\times 10^4。

思路

对于固定局面的答案，可以用任意选择一个 0，一个 1，一个 2 的方案减去不合法的。而不合法的可以看作以每个 1 为根，每个子树中 0 的个数和 2 的个数的乘积之和。由于根不固定比较麻烦，所以不妨以点 1 为根，这样这部分需要算的就是每个颜色 1 的节点的每个儿子子树内的 0,2 个数的乘积，以及它们子树外面 0,2 个数的乘积。在带修改的问题中，总答案容易维护，关键在于后面这个东西怎么维护。

先考虑维护子树外部分的答案。若记 v_0,v_2 分别表示一个点子树外面的 0,2 的个数，则一次修改点 x 的颜色相当于是将除了 x 到根的链上以外的部分每个的 v_0/v_2 整体加一个值，可以用树剖转化为区间加。最后需要算的是 \sum {v_0}_x\times {v_2}_x\times [col_x=1]。可以看作是 \sum A_x\times B_x\times C_x，其中 A_x,B_x 需要支持区间加，C_x 支持单点修改，这是可以使用线段树来维护的。

再考虑维护子树中的答案，如果仿照上面一种方式来处理，问题在于此时 C_x=[col_{fa_x}=1]，但这样在修改一个点的时候就会将它所有儿子的 C_x 都修改一遍。在树剖上一个点所有的儿子的编号没有什么很好的性质，所以直接这么做是不可行的。此时需要算的东西本质上是对于每条边 (fa_x,x)，{sz_0}_x\times {sz_2}_x\times [col_{fa_x}=1] 的值。既然对于每条边求和，那么自然可以想到分成轻边与重边分别处理。

对于重边来说，此时一次修改会将一条链上的 sz 进行整体加，同时可能修改单点的 col，那么用第一种方法中的线段树即可维护，因为修改一个 col​ 至多影响一条重边，所以这个在线段树上也是单点加。

对于轻边来说，我们在每个点上维护以它为父亲的所有轻边的 {sz_0}_x\times {sz_2}_x 之和。这样在一次修改时会经过所有需要修改的轻边，因此这个值的更新是容易的。然后再动态维护一个 sum 表示所有颜色为 1 的点的上述权值之和。这个值只需要在修改颜色时对应更新即可。这样就做完了，复杂度 O(n\log n+q\log^2n)。

#include "joitour.h"
#include <bits/stdc++.h>
#define INF 1000000000
#define LINF 1000000000000000000
#define MOD 1000000007
#define mod 998244353
#define F first
#define S second
#define ll long long
#define N 200010
using namespace std;
struct Tag{
    ll va,vb;
    Tag(){va=vb=0;}
    Tag(ll _a,ll _b){va=_a,vb=_b;}
    Tag operator + (const Tag &x)const{
        return Tag(va+x.va,vb+x.vb);
    }
};
struct Node{
    ll ans,va,vb,vc,vac,vbc,len;
    Node(){ans=va=vb=vc=vac=vbc=len=0;}
    Node(ll _s,ll _l,ll _a,ll _b,ll _c,ll _ac,ll _bc){ans=_s,len=_l,va=_a,vb=_b,vc=_c,vac=_ac,vbc=_bc;}
    Node operator + (const Node &x)const{
        return Node(ans+x.ans,len+x.len,va+x.va,vb+x.vb,vc+x.vc,vac+x.vac,vbc+x.vbc);
    }
    Node operator + (const Tag &x)const{
        return Node(ans+x.va*vbc+x.vb*vac+x.va*x.vb*vc,len,va+x.va*len,vb+x.vb*len,vc,vac+x.va*vc,vbc+x.vb*vc);
    }
};
struct SegT{
    ll lo[N<<2],hi[N<<2],pre[N][3];
    Node val[N<<2];
    Tag pd[N<<2];
    void build(ll x,ll l,ll r)
    {
        lo[x]=l,hi[x]=r;
        if(l==r)
        {
            val[x]=Node(pre[l][0]*pre[l][1]*pre[l][2],1,pre[l][0],pre[l][1],pre[l][2],pre[l][0]*pre[l][2],pre[l][1]*pre[l][2]);
            return;
        }
        ll mid=(l+r)>>1,a=x<<1;
        build(a,l,mid);
        build(a|1,mid+1,r);
        val[x]=val[a]+val[a|1];
        return;
    }
    void pushdown(ll x)
    {
        ll a=x<<1;
        val[a]=val[a]+pd[x];
        pd[a]=pd[a]+pd[x];
        val[a|1]=val[a|1]+pd[x];
        pd[a|1]=pd[a|1]+pd[x];
        pd[x]=Tag(0,0);
        return;
    }
    void update(ll x,ll l,ll r,Tag v)
    {
        ll tl=lo[x],tr=hi[x];
        if(l<=tl&&tr<=r)
        {
            val[x]=val[x]+v;
            pd[x]=pd[x]+v;
            return;
        }
        pushdown(x);
        ll mid=(tl+tr)>>1,a=x<<1;
        if(mid>=l)
        {
            update(a,l,r,v);
        }
        if(mid<r)
        {
            update(a|1,l,r,v);
        }
        val[x]=val[a]+val[a|1];
        return;
    }
    void modify(ll x,ll l,ll v)
    {
        ll tl=lo[x],tr=hi[x];
        if(tl==tr)
        {
            ll va=val[x].va,vb=val[x].vb,vc=v;
            val[x]=Node(va*vb*vc,1,va,vb,vc,va*vc,vb*vc);
            return;
        }
        pushdown(x);
        ll mid=(tl+tr)>>1,a=x<<1;
        if(mid>=l)
        {
            modify(a,l,v);
        }
        else
        {
            modify(a|1,l,v);
        }
        val[x]=val[a]+val[a|1];
        return;
    }
}segt1,segt2;
ll n,q,fa[N],col[N],sz[N][3],tothv[3],totsm=0,valsm[N];
ll num[N],hson[N],tp[N],din[N],dout[N],dcnt=0;
vector<ll> vt[N];
void predfs(ll x,ll lst)
{
    ll i;
    sz[x][0]=sz[x][1]=sz[x][2]=0;
    sz[x][col[x]]=1;
    num[x]=1;
    fa[x]=lst;
    hson[x]=-1;
    for(i=0;i<vt[x].size();i++)
    {
        if(vt[x][i]!=lst)
        {
            predfs(vt[x][i],x);
            num[x]+=num[vt[x][i]];
            sz[x][0]+=sz[vt[x][i]][0];
            sz[x][1]+=sz[vt[x][i]][1];
            sz[x][2]+=sz[vt[x][i]][2];
            if(hson[x]==-1||num[hson[x]]<num[vt[x][i]])
            {
                hson[x]=vt[x][i];
            }
        }
    }
    return;
}
void dfs(ll x,ll lst,bool ist=true)
{
    ll i;
    tp[x]=ist?x:tp[lst];
    din[x]=++dcnt;
    if(hson[x]!=-1)
    {
        dfs(hson[x],x,false);
    }
    for(i=0;i<vt[x].size();i++)
    {
        if(vt[x][i]!=lst&&vt[x][i]!=hson[x])
        {
            dfs(vt[x][i],x);
        }
    }
    dout[x]=dcnt;
    return;
}
void init(int _n,vector<int> _f,vector<int> _u,vector<int> _v,int _q)
{
    ll i;
    n=_n,q=_q;
    tothv[0]=tothv[1]=tothv[2]=0;
    for(i=0;i<n;i++)
    {
        col[i]=_f[i];
        tothv[col[i]]++;
    }
    for(i=0;i<n-1;i++)
    {
        vt[_u[i]].push_back(_v[i]);
        vt[_v[i]].push_back(_u[i]);
    }
    predfs(0,-1);
    dfs(0,-1);
    for(i=1;i<=n;i++)
    {
        segt1.pre[i][0]=segt1.pre[i][1]=segt1.pre[i][2]=0;
        segt2.pre[i][0]=segt2.pre[i][1]=segt2.pre[i][2]=0;
    }
    for(i=1;i<n;i++)
    {
        if(i==hson[fa[i]])
        {
            segt1.pre[din[fa[i]]][0]=sz[i][0];
            segt1.pre[din[fa[i]]][1]=sz[i][2];
            segt1.pre[din[fa[i]]][2]=(col[fa[i]]==1);
        }
        else
        {
            valsm[fa[i]]+=sz[i][0]*sz[i][2];
            if(col[fa[i]]==1)
            {
                totsm+=sz[i][0]*sz[i][2];
            }
        }
        segt2.pre[din[i]][0]=tothv[0]-sz[i][0];
        segt2.pre[din[i]][1]=tothv[2]-sz[i][2];
        segt2.pre[din[i]][2]=(col[i]==1);
    }
    segt1.build(1,1,n);
    segt2.build(1,1,n);
    return;
}
void upd(ll x,ll y,ll c)
{
    ll i;
    tothv[col[x]]+=c;
    if(y==1)
    {
        totsm+=valsm[x]*c;
        segt1.modify(1,din[x],max(0ll,c));
        segt2.modify(1,din[x],max(0ll,c));
    }
    else
    {
        vector<pair<ll,ll> > seq;
        while(x>=0)
        {
            seq.push_back(make_pair(din[tp[x]],din[x]));
            if(din[tp[x]]<din[x])
            {
                segt1.update(1,din[tp[x]],din[x]-1,Tag(y==0?c:0,y==0?0:c));
            }
            x=tp[x];
            if(x>0)
            {
                if(col[fa[x]]==1)
                {
                    totsm-=valsm[fa[x]];
                }
                valsm[fa[x]]-=sz[x][0]*sz[x][2];
                sz[x][y]+=c;
                valsm[fa[x]]+=sz[x][0]*sz[x][2];
                if(col[fa[x]]==1)
                {
                    totsm+=valsm[fa[x]];
                }
            }
            x=fa[x];
        }
        sort(seq.begin(),seq.end());
        seq.push_back(make_pair(n+1,INF));
        for(i=1;i<seq.size();i++)
        {
            if(seq[i-1].S+1<=seq[i].F-1)
            {
                segt2.update(1,seq[i-1].S+1,seq[i].F-1,Tag(y==0?c:0,y==0?0:c));
            }
        }
    }
    return;
}
void change(int _x,int _y)
{
    ll x=_x,y=_y;
    if(col[x]==y)
    {
        return;
    }
    upd(x,col[x],-1);
    col[x]=y;
    upd(x,col[x],1);
    return;
}
ll num_tours()
{
    ll ans=tothv[0]*tothv[1]*tothv[2];
    ans-=totsm;
    ans-=segt1.val[1].ans;
    ans-=segt2.val[1].ans;
    return ans;
}

Day3 T3 Tower

题意

有一个无穷大的台阶，一个人初始在 0，可以以 A 的代价向上一步，或以 B 的代价向上 D 步。有 n 个区间 [l_i,r_i] 是不可以经过的。q 次询问给定 x，问能否到达 x，以及到达 x 的最小代价。n,q\le 2\times 10^5。

思路

容易求出 O(n) 个可以经过的区间，则下面假设对这些区间进行考察。显然只需要求得到达每个位置所需要的最少跳的步数和最多跳的步数即可。先考虑最小步数，首先第一个区间所有数的最小步数都是 0。然后考虑从某个区间转移到某个区间，记这两个区间的交为 [l,r]，则相当于将新区间 l 及以后的部分的最小步数都和当前的最小步数取 \min。由于靠后的区间转移到的位置也更加靠后，所以可以归纳说明：1. 每个区间在第一个合法位置的后面所有的最小步数都是一样的。2. 对于所有合法位置而言，最小步数是单调不降的。这样最小步数就可以直接转移了。暴力做是 O(n^2) 的，但容易在区间中二分使得我们只做所有交非空的转移。由于所有的区间不交，所以转移到的区间也不交。而由于一个转移区间除了左右的 O(1) 个区间以外，其它能转移到的区间都是完成包含，但显然一个区间至多被包含一次，所以这样做复杂度是 O(n\log n)。

下面考虑最大步数怎么算。此时比较麻烦的一点在于一段中的最大步数是不一样的。但其实这个的规律性还是比较明显。对于第一个区间而言，一定是每 D 个增加 1，所以只需要维护第一段的左右端点和权值，就容易查询一个位置的最大步数是多少。考虑转移，此时可能会从前面截一段放到后面，并在后面进行每 D 个为一个周期的延伸。这样的一个问题就是原本可能只有第一段不满，但现在可能在中间直接插入一个不满的段，会使得一个区间中有至多 O(n) 个段。当然我们可以先不管复杂度，直接暴力来做这个更新。具体来说，对每个段维护一个序列 (l,r,v)，表示区间 [l,r] 的权值为 v，然后 [r+1,r+D] 的权值为 v+1 等等，一直到下一个区间的 l 之前为止。那么我们对每个这样的段进行转移，转移的时候如果左右端点的权值相等，说明它们在同一个段内。此时对于新段的影响是一个形如 (l,l+D-1,v) 这样的段。否则假设左端点距离下一个和它权值不同的点剩余 len 的距离，则影响是一个形如 (l,l+len-1,v) 这样的段。在比较段之间的大小的时候，如果 v 不等则 v 更大的显然更优。否则 r 更小的更优，因为这意味着可能更快地进入下一个权值。

不过直接这样写只做所有交非空的转移就过了，那么这是为什么呢？其实原因就是两个大段之间转移至多会产生 O(1) 个有用的段，这是因为两个段之间的交长度至多为 D（考虑后一个区间的左端点 l，前一个区间只有 \ge l-D 的位置才可能转移，但前一个区间的右端点又 <l，所以交至多为 D），而若有超过两个有用的段，则至少会完成包含一个长度为 D 的段，则矛盾。这样复杂度其实就是 O(n)，加上二分是 O(n\log n)。

#include <bits/stdc++.h>
#define INF 1000000000
#define LINF 1000000000000000000
#define MOD 1000000007
#define mod 998244353
#define F first
#define S second
#define ll long long
#define N 200010
using namespace std;
ll n,q,D,A,B,mnp[N],f[N];
vector<pair<pair<ll,ll>,ll> > g[N];
pair<ll,ll> badp[N];
vector<pair<ll,ll> > seq;
pair<ll,ll> ask(ll p,ll x)
{
    pair<pair<ll,ll>,ll> fd=make_pair(make_pair(x+1,-INF),-INF);
    ll i=lower_bound(g[p].begin(),g[p].end(),fd)-g[p].begin()-1;
    if(i<0)
    {
        return make_pair(i,-LINF);
    }
    ll l=g[p][i].F.F,r=g[p][i].F.S,w=g[p][i].S;
    if(l<=x&&x<=r)
    {
        return make_pair(i,w);
    }
    return make_pair(i,w+(x-r-1)/D+1);
}
int main(){
    ll i,j;
    scanf("%lld%lld%lld%lld%lld",&n,&q,&D,&A,&B);
    for(i=0;i<n;i++)
    {
        scanf("%lld%lld",&badp[i].F,&badp[i].S);
    }
    seq.push_back(make_pair(0,badp[0].F-1));
    for(i=1;i<n;i++)
    {
        seq.push_back(make_pair(badp[i-1].S+1,badp[i].F-1));
    }
    seq.push_back(make_pair(badp[n-1].S+1,LINF));
    for(i=0;i<seq.size();i++)
    {
        mnp[i]=LINF+5;
    }
    mnp[0]=0;
    for(i=0;i<seq.size();i++)
    {
        ll l=mnp[i]+D,r=seq[i].S+D;
        pair<ll,ll> fd=make_pair(l+1,-INF);
        ll p=lower_bound(seq.begin(),seq.end(),fd)-seq.begin()-1;
        p=max(p,i+1);
        while(p<seq.size()&&seq[p].F<=r)
        {
            ll lo=max(l,seq[p].F),hi=min(r,seq[p].S);
            if(lo<=hi)
            {
                mnp[p]=min(mnp[p],lo);
            }
            p++;
        }
    }
    vector<pair<ll,ll> > rgs;
    for(i=0;i<seq.size();i++)
    {
        if(mnp[i]<=seq[i].S)
        {
            rgs.push_back(make_pair(mnp[i],seq[i].S));
        }
    }
    sort(rgs.begin(),rgs.end());
    memset(f,63,sizeof(f));
    f[0]=0;
    g[0].push_back(make_pair(make_pair(0,min(D-1,rgs[0].S)),0));
    for(i=0;i<rgs.size();i++)
    {
        ll l=rgs[i].F+D,r=rgs[i].S+D;
        pair<ll,ll> fd=make_pair(l+1,-INF);
        ll p=lower_bound(rgs.begin(),rgs.end(),fd)-rgs.begin()-1;
        p=max(p,i+1);
        while(p<rgs.size()&&rgs[p].F<=r)
        {
            ll lo=max(l,rgs[p].F),hi=min(r,rgs[p].S);
            if(lo<=hi)
            {
                f[p]=min(f[p],f[i]+1);
            }
            p++;
        }
        for(j=0;j<g[i].size();j++)
        {
            l=g[i][j].F.F+D,r=(j==g[i].size()-1?rgs[i].S:g[i][j+1].F.F-1)+D;
            fd=make_pair(l+1,-INF);
            p=lower_bound(rgs.begin(),rgs.end(),fd)-rgs.begin()-1;
            p=max(p,i+1);
            while(p<rgs.size()&&rgs[p].F<=r)
            {
                ll lo=max(l,rgs[p].F),hi=min(r,rgs[p].S);
                if(lo<=hi)
                {
                    ll tl=lo-D,tr=hi-D,len,w;
                    if(ask(i,tr)==ask(i,tl))
                    {
                        len=D;
                        w=ask(i,tl).S;
                    }
                    else if(tl<=g[i][j].F.S)
                    {
                        len=g[i][j].F.S-tl+1;
                        w=g[i][j].S;
                    }
                    else
                    {
                        len=D-((tl-g[i][j].F.S-1)%D);
                        w=g[i][j].S+(tl-g[i][j].F.S-1)/D+1;
                    }
                    pair<ll,ll> cur=ask(p,lo);
                    if(cur.S<w+1)
                    {
                        if(cur.F>=0&&g[p][cur.F].F.S>=lo)
                        {
                            g[p][cur.F].F.S=lo-1;
                        }
                        g[p].push_back(make_pair(make_pair(lo,min(lo+len-1,rgs[p].S)),w+1));
                    }
                    else if(cur.S==w+1)
                    {
                        ll lft;
                        if(g[p][cur.F].F.F<=lo&&lo<=g[p][cur.F].F.S)
                        {
                            lft=g[p][cur.F].F.S-lo+1;
                        }
                        else
                        {
                            lft=D-((lo-g[p][cur.F].F.S-1)%D);
                        }
                        if(len<lft)
                        {
                            if(cur.F>=0&&g[p][cur.F].F.S>=lo)
                            {
                                g[p][cur.F].F.S=lo-1;
                            }
                            g[p].push_back(make_pair(make_pair(lo,min(lo+len-1,rgs[p].S)),w+1));
                        }
                    }
                }
                p++;
            }
        }
    }
    while(q--)
    {
        ll x;
        scanf("%lld",&x);
        pair<ll,ll> fd=make_pair(x+1,-INF);
        ll p=lower_bound(rgs.begin(),rgs.end(),fd)-rgs.begin()-1;
        if(p>=0&&rgs[p].F<=x&&rgs[p].S>=x)
        {
            ll ans=(x-f[p]*D)*A+f[p]*B;
            ll y=ask(p,x).S;
            ans=min(ans,(x-y*D)*A+y*B);
            printf("%lld\n",ans);
        }
        else
        {
            puts("-1");
        }
    }
    return 0;
}

Day4 T1 Escape Route 2

题意

有 n 个点，点 i 向点 i+1 有 m_i 个航线，第 j 个航线从 a_{i,j} 时刻出发，b_{i,j} 时刻到达。一天有 T 个时刻，保证 a_{i,j}<b_{i,j}，即航线一定不会跨越一天。可以在每个点等待任意长时间，包括跨越一天。q 次询问 l\to r 的最少时间。n\le 10^5,\sum m_i\le 10^5,q\le 3\times 10^5。

思路

显然若 a_{i,j}<a_{i,k} 而 b_{i,j}>b_{i,k}，那么 j 不再有用了。则此时按照 a 将 i 的每条出边排序，那么 b 也是递增的。同样显然到达一个点之后一定是走它能走的下一条航线离开，可以对每条航线，二分求出它下一条航线是什么，不妨设为 nxt_i，则如果知道最开始使用的是哪个航线，那么答案就是它一直向后走到 r 的代价之和。然而我们不能枚举起点的航线，所以需要考虑一些别的方法。

若从 i 向 nxt_i 连边，则构成一个内向树状结构，可以反过来 dfs 求出每个点的深度，那么一次查询相当于是问 r 对应的所有点的子树中 l 对应的所有点的深度减去它在 r 这一层的祖先的深度的最小值是什么。维护一个子树内每种颜色的深度最小值可以用启发式合并来做。但此时仍然需要每个 r 对应的每个点。不过注意到我们实际上只需要枚举子树中存在至少一个 l 的点，而若要存在一个 l，则子树中至少有 r-l+1 个点，这样需要枚举的点数量是 O(\frac n{r-l+1}) 的。则如果 r-l+1 较大，问题就被解决了。另一方面，若 r-l+1 较小，则显然可以预处理每个左端点向后一段距离的答案。这样当 r-l+1>\sqrt n 时启发式合并回答，否则用预处理的结果回答。复杂度 O(n\sqrt n+n\log n)。

#include <bits/stdc++.h>
#define INF 1000000000
#define LINF 1000000000000000000
#define MOD 1000000007
#define mod 998244353
#define F first
#define S second
#define ll long long
#define N 100010
using namespace std;
ll n,q,T,cnt=0,fa[N],par[N],dep[N],res[N][400],ans[300010];
vector<ll> idx[N],curhv[N];
vector<pair<ll,ll> > eds[N],vt[N],qry[N];
void dfs(ll x)
{
    ll i;
    for(i=0;i<vt[x].size();i++)
    {
        dep[vt[x][i].F]=dep[x]+vt[x][i].S;
        dfs(vt[x][i].F);
    }
    return;
}
bool cmp(ll x,ll y)
{
    return curhv[x].size()>curhv[y].size();
}
int main(){
    ll i,j,k,x;
    scanf("%lld%lld",&n,&T);
    for(i=0;i+1<n;i++)
    {
        scanf("%lld",&x);
        eds[i].resize(x);
        for(j=0;j<x;j++)
        {
            scanf("%lld%lld",&eds[i][j].F,&eds[i][j].S);
        }
        sort(eds[i].begin(),eds[i].end());
        vector<pair<ll,ll> > nw;
        for(j=0;j<x;j++)
        {
            while(!nw.empty())
            {
                if(nw.back().S<eds[i][j].S)
                {
                    break;
                }
                nw.pop_back();
            }
            if((!nw.empty())&&eds[i][j].F<=nw.back().F)
            {
                continue;
            }
            nw.push_back(eds[i][j]);
        }
        eds[i]=nw;
        for(j=0;j<eds[i].size();j++)
        {
            idx[i].push_back(cnt++);
        }
    }
    for(i=0;i<n-1;i++)
    {
        for(j=x=0;j<eds[i].size();j++)
        {
            while(x<eds[i+1].size()&&eds[i+1][x].F<eds[i][j].S)
            {
                x++;
            }
            if(x>=eds[i+1].size())
            {
                if(eds[i+1].empty())
                {
                    fa[idx[i][j]]=cnt;
                    par[idx[i][j]]=0;
                    vt[cnt].push_back(make_pair(idx[i][j],0));
                }
                else
                {
                    fa[idx[i][j]]=idx[i+1][0];
                    par[idx[i][j]]=eds[i+1][0].S+T-eds[i][j].S;
                    vt[idx[i+1][0]].push_back(make_pair(idx[i][j],eds[i+1][0].S+T-eds[i][j].S));
                }
            }
            else
            {
                fa[idx[i][j]]=idx[i+1][x];
                par[idx[i][j]]=eds[i+1][x].S-eds[i][j].S;
                vt[idx[i+1][x]].push_back(make_pair(idx[i][j],eds[i+1][x].S-eds[i][j].S));
            }
        }
    }
    dfs(cnt);
    memset(res,63,sizeof(res));
    for(i=0;i<n;i++)
    {
        for(j=0;j<eds[i].size();j++)
        {
            ll cur=eds[i][j].S-eds[i][j].F,id=idx[i][j];
            for(x=i+1;x<i+400&&x<n;x++)
            {
                res[i][x-i]=min(res[i][x-i],cur);
                cur+=par[id];
                id=fa[id];
            }
        }
    }
    scanf("%lld",&q);
    for(i=0;i<q;i++)
    {
        ll l,r;
        scanf("%lld%lld",&l,&r);
        l--,r--;
        if(r-l<380)
        {
            ans[i]=res[l][r-l];
        }
        else
        {
            ans[i]=LINF;
            qry[r-1].push_back(make_pair(l,i));
        }
    }
    for(i=0;i<n;i++)
    {
        for(j=0;j<eds[i].size();j++)
        {
            curhv[idx[i][j]].push_back(dep[idx[i][j]]+eds[i][j].S-eds[i][j].F);
        }
        vector<ll> ord=idx[i];
        sort(ord.begin(),ord.end(),cmp);
        for(j=0;j<qry[i].size();j++)
        {
            ll l=qry[i][j].F,id=qry[i][j].S;
            for(x=0;x<ord.size()&&curhv[ord[x]].size()>=i-l+1;x++)
            {
                ans[id]=min(ans[id],curhv[ord[x]][curhv[ord[x]].size()-(i-l+1)]-dep[ord[x]]);
            }
        }
        for(j=0;j<eds[i].size();j++)
        {
            x=idx[i][j];
            if(curhv[fa[x]].size()<curhv[x].size())
            {
                swap(curhv[fa[x]],curhv[x]);
            }
            for(k=0;k<curhv[x].size();k++)
            {
                curhv[fa[x]][curhv[fa[x]].size()-(curhv[x].size()-k)]=min(curhv[fa[x]][curhv[fa[x]].size()-(curhv[x].size()-k)],curhv[x][k]);
            }
        }
    }
    for(i=0;i<q;i++)
    {
        printf("%lld\n",ans[i]);
    }
    return 0;
}

Day4 T2 Island Hopping

题意

有一棵 n 个点的树，需要通过询问得知其每条边的信息。可以询问 (x,k)，交互库会返回与 x 距离第 k 小的点，距离相等时按照点的编号排序，至多询问 2n 次。n\le 300。

思路

想要确定树的形态则肯定需要通过某种方式遍历整棵树。如果我们想采用类似 dfs 的方式，那么问题在于无法确定什么时候一个点的儿子被访问完了。注意到这个题目给出的距离第 k 小本身很像一个 bfs 的过程，所以我们考虑利用 bfs 来确定这棵树。

具体来说，不妨设 1 为根，则当前我们的树只有 1 一个点。考虑从小到大依次询问距离 1 第 k 小的点，那么每次询问到的点一定会接在一个已知的点上。则我们从小到大进行查询，如果问到了一个已知的点则连边即可。由于这个点与所有已知的点中一定恰好有 1 条边，所以这么做一定能找到这条边。

这样朴素实现的话最坏需要 O(n^2) 次操作，但显然我们还没有利用好中间查询的信息。具体来说，如果在中途尝试将一个点加入这棵树的时候问到了一个不是已知的点，那么由于按照距离排序，所以这条边一定存在。那我们自然可以直接将这条边连起来。这样如果在后面需要将这个点连入树中，那么就没有必要再进行查询了。考虑这样做需要多少步呢？首先需要 n-1 步问 1 的距离排名为 k 的点。然后对于每个点，将它连入树中需要一步。注意到所有失败的查询都会将一个点连入树中，所以失败的查询不会带来额外步数。这样总步数是 2n-2。

#include "island.h"
#include <bits/stdc++.h>
#define INF 1000000000
#define LINF 1000000000000000000
#define MOD 1000000007
#define mod 998244353
#define F first
#define S second
#define ll long long
#define maxn 310
using namespace std;
ll n,res[maxn][maxn];
bool vis[maxn];
ll ask(ll x,ll k)
{
    if(res[x][k]!=-1)
    {
        return res[x][k];
    }
    return res[x][k]=query(x,k);
}
void solve(int _n,int lim)
{
    ll i,j;
    memset(res,-1,sizeof(res));
    n=_n;
    vis[1]=true;
    for(i=1;i<n;i++)
    {
        ll x=ask(1,i);
        if(vis[x])
        {
            continue;
        }
        vis[x]=true;
        for(j=1;j<n;j++)
        {
            ll y=ask(x,j);
            answer(x,y);
            if(vis[y])
            {
                break;
            }
            vis[y]=true;
        }
    }
    return;
}

Day4 T3 Table Tennis

题意

构造一个恰好有 m 个三元环的 n 个点的竞赛图，或输出无解。n\le 5000。

思路

竞赛图的三元环数量是一个经典问题，它等于 \displaystyle\binom n3-\sum_{i}\binom{out_i}2，其中 out_i 为 i 的出度。那么我们只需要让 \displaystyle\sum_{i}\binom{out_i}2 等于某个 k 即可。如果是任意 out 序列那么是很简单的，但显然不是每个 out 序列都合法。而一个竞赛图的合法出度序列又是一个经典问题，若序列 a 满足 0\le a_i<n,\sum a_i=\binom n2，且不妨设 a_1\le\cdots\le a_n 时，\displaystyle \forall k,\sum_{i=1}^k a_i\ge \binom k2，则序列 a 是某个竞赛图的出度序列。且构造也是容易的，直接贪心将出度最大的点向出度最小的若干个点连边，消去最大的若干个出度即可。

这样我们只需要求出一个序列 a，满足上面的条件，且 \displaystyle\sum_i\binom{a_i}2=k。先考虑一下什么时候有解。注意到后面这个式子显然能取到 \binom n3 的上界，但是不能取到 0 的下界。求下界是一个固定若干数的和，求平方和的最小值的问题，可以根据均值不等式或直接感性理解发现当 a_i=\dfrac{\binom n2}n 时这个式子取到最小值。当然实际中 a_i 必须是整数，所以部分向下取整，部分向上取整即可。证明可以通过调整法完成。而更一般地，若 \sum a_i=s，则 a_i=\dfrac sn 时取到最小值，在整数中同样是部分上取整部分下取整。当然容易说明这么取一定可以满足前缀和下界的这个限制。

然后通过打表或根据直觉可以猜测只符合这个下界和上界的限制就一定有解。这个可以通过后面的构造的过程来完成证明。先考虑怎么构造。我们从大往小来确定每个 a_i。显然我们是希望当前的这个 a_i 越大越好，前提是前面的部分合法。而根据我们的结论，只要前面的和满足可以取到的理论下界与上界包含了剩余需要的 k，就一定是合法的，当然前提是满足度数前缀和下界的限制。事实上可以分析出若后面也满足这个条件，则一定能找到一个这样的 a_i。不过比较偷懒的办法就是打个表发现确实是这样的。

于是就做完了，直接贪心尝试每种权值是否可行即可。复杂度 O(n^2) 或 O(n^2\log n)。

#include <bits/stdc++.h>
#define INF 1000000000
#define LINF 1000000000000000000
#define MOD 1000000007
#define mod 998244353
#define F first
#define S second
#define ll long long
#define N 5010
using namespace std;
ll n,m,d[N];
bool ans[N][N];
ll calc(ll x,ll y)
{
    ll tot=(y/x)*(y/x-1)/2;
    tot*=(x-y%x);
    tot+=(y%x)*(y/x)*(y/x+1)/2;
    return tot;
}
bool cmp(pair<ll,ll> x,pair<ll,ll> y)
{
    return x.F==y.F?x.S>y.S:x.F<y.F;
}
int main(){
    ll T,i,j;
    cin>>T;
    while(T--)
    {
        cin>>n>>m;
        m=n*(n-1)*(n-2)/6-m;
        if(m<calc(n,n*(n-1)/2))
        {
            puts("No");
            continue;
        }
        ll lft=n*(n-1)/2,lst=n-1;
        for(i=n-1;i>0;i--)
        {
            for(j=lst;j>=0;j--)
            {
                if(lft-j>=i*(i-1)/2&&m-j*(j-1)/2>=calc(i,lft-j))
                {
                    break;
                }
            }
            assert(j>=0);
            m-=j*(j-1)/2;
            d[i]=j;
            lst=j;
            lft-=j;
        }
        assert(lft<=lst&&m==lft*(lft-1)/2);
        d[0]=lft;
        puts("Yes");
        for(i=0;i<n;i++)
        {
            for(j=0;j<n;j++)
            {
                ans[i][j]=false;
            }
        }
        priority_queue<pair<ll,ll> > pq;
        for(i=0;i<n;i++)
        {
            pq.push(make_pair(d[i],i));
        }
        for(i=n-1;i>=0;i--)
        {
            vector<pair<ll,ll> > nds;
            for(j=0;j<i;j++)
            {
                nds.push_back(make_pair(d[j],j));
            }
            sort(nds.begin(),nds.end(),cmp);
            for(j=0;j<d[i];j++)
            {
                ans[i][nds[j].S]=true;
            }
            for(j=d[i];j<nds.size();j++)
            {
                ans[nds[j].S][i]=true;
                d[nds[j].S]--;
            }
        }
        for(i=1;i<n;i++)
        {
            for(j=0;j<i;j++)
            {
                putchar(ans[i][j]?'0':'1');
            }
            puts("");
        }
    }
    return 0;
}