The Kouga Ninja Scrolls & Rikka with Sorting Networks ICPC 2018 Shenyang R & Xuzhou R

WZH2026-09-142026-09-14

[ICPC 2018 Shenyang R] The Kouga Ninja Scrolls

题目链接： [ICPC 2018 Shenyang R] The Kouga Ninja Scrolls 。

题目描述：

故事围绕着 $n$ 个互为对手的忍者氏族展开，氏族编号从 $1$ 到 $n$ ，同样也有 $n$ 名忍者，编号从 $1$ 到 $n$ 。对每一名忍者，其家族决定了他/她最初的信念与所属的氏族。但故事中会发生一些冲突，例如两个年轻的灵魂，面对各自家族的敌对却坠入爱河，可能会改变心意，一些忍者也可能叛逃至其他敌对的氏族。

这些忍者生活在一个相当宁静的小镇，镇上的小径简单明了，但他们却像一群野兽，时刻盯着其他氏族的忍者，不停逃亡并伺机杀戮。这片区域的领主知道，他们之间战争的终结取决于那些分属不同氏族且相距最远的忍者。

这正是作为领主忠实仆人的一只高贵秃鹫应当做的事情。现在你需要扮演这只秃鹫，实时向领主报告：在编号属于某个指定连续范围内的忍者中，分属不同氏族的两名忍者之间的最大距离是多少。具体而言，平面上两点之间的距离定义为曼哈顿距离，也就是它们笛卡尔坐标差的绝对值之和。

答案求的是 $\max\limits_{l\le i<j\le r}\{|x_i-x_j|+| y_i-y_j|\}$ ，利用三角不等式必定取等的性质得答案为 $\max\{||x_i-y_i|-|x_j-y_j||,||x_i+y_i|-|x_j+y_j||\}$ 。使用线段树维护：

最大值及颜色。
颜色不同的次大值及颜色。
最小值及颜色。
颜色不同的次小值及颜色。

然后就没了。代码真难写。

#include <bits/stdc++.h>
using namespace std;
const int N=100100,M=4000010;
#define int long long
using ll=long long;
using pii=pair<ll,ll>;
int T,n,m;
ll X[N],Y[N],C[N];
struct node{
    pii mx,mx2,mn,mn2;
}a[M];
int idx,ls[M],rs[M],rtA,rtB;
const pii inf_max={-1e18,0},inf_min={1e18,0};
pii Max(pii x,pii y,int c){
    if(x.second==c&&y.second==c)return inf_max;
    if(x.second==c)return y;
    if(y.second==c)return x;
    return x.first>y.first?x:y;
}
pii Min(pii x,pii y,int c){
    if(x.second==c&&y.second==c)return inf_min;
    if(x.second==c)return y;
    if(y.second==c)return x;
    return x.first<y.first?x:y;
}
node up(node l,node r){
    node p;
    if(l.mx.first>r.mx.first)p.mx=l.mx,p.mx2=Max(r.mx,Max(l.mx2,r.mx2,l.mx.second),l.mx.second);
    else p.mx=r.mx,p.mx2=Max(l.mx,Max(l.mx2,r.mx2,r.mx.second),r.mx.second);
    if(l.mn.first<r.mn.first)p.mn=l.mn,p.mn2=Min(r.mn,Min(l.mn2,r.mn2,l.mn.second),l.mn.second);
    else p.mn=r.mn,p.mn2=Min(l.mn,Min(l.mn2,r.mn2,r.mn.second),r.mn.second);
    return p;
}
void insert(int &p,int l,int r,int x,int y,int z){
    if(!p)p=++idx,a[p]={inf_max,inf_max,inf_min,inf_min};
    if(l==r){
        a[p].mx=a[p].mn={y,z};
        return ;
    }
    int mid=(l+r)>>1;
    if(mid>=x)insert(ls[p],l,mid,x,y,z);
    else insert(rs[p],mid+1,r,x,y,z);
    a[p]=up(a[ls[p]],a[rs[p]]);
}
node query(int p,int l,int r,int ql,int qr){
    if(!p)return {inf_max,inf_max,inf_min,inf_min};
    if(ql<=l&&r<=qr)return a[p];
    int mid=(l+r)>>1;
    if(mid>=ql&&mid<qr)return up(query(ls[p],l,mid,ql,qr),query(rs[p],mid+1,r,ql,qr));
    if(mid>=ql)return query(ls[p],l,mid,ql,qr);
    return query(rs[p],mid+1,r,ql,qr);
}
ll calc(node p){
    if(p.mx.second!=p.mn.second)return p.mx.first-p.mn.first;
    ll t=max(p.mx.first-p.mn2.first,p.mx2.first-p.mn.first);
    return max(0ll,t);
}
void WZH(int Case){
    printf("Case #%lld:\n",Case);
    for(int i=0;i<=idx;i++)ls[i]=rs[i]=0;
    rtA=rtB=idx=0;
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++){
        ll x,y,z;
        scanf("%lld%lld%lld",&x,&y,&z);
        insert(rtA,1,n,i,x+y,z);
        insert(rtB,1,n,i,x-y,z);
        X[i]=x,Y[i]=y,C[i]=z;
    }
    while(m--){
        int opt,x,y;ll z;
        scanf("%lld%lld%lld",&opt,&x,&y);
        if(opt==1){
            scanf("%lld",&z);
            X[x]+=y,Y[x]+=z;
            insert(rtA,1,n,x,X[x]+Y[x],C[x]);
            insert(rtB,1,n,x,X[x]-Y[x],C[x]);
        }
        if(opt==2){
            C[x]=y;
            insert(rtA,1,n,x,X[x]+Y[x],C[x]);
            insert(rtB,1,n,x,X[x]-Y[x],C[x]);
        }
        if(opt==3){
            node t1=query(rtA,1,n,x,y),t2=query(rtB,1,n,x,y);
            printf("%lld\n",max(calc(t1),calc(t2)));
        }
    }
}
signed main(){
    a[0]={inf_max,inf_max,inf_min,inf_min};
    scanf("%lld",&T);
    for(int i=1;i<=T;i++)WZH(i);
    return 0;
}

[ICPC 2018 Xuzhou R] Rikka with Sorting Networks

不知道为啥能评蓝……感觉最多黄。

题目链接： [ICPC 2018 Xuzhou R] Rikka with Sorting Networks 。

题目描述：

有 $k$ 个按顺序的比较器，第 $i$ 个比较器会将序列第 $u_i 和 v_i$ 个数经行排序。求有多少个排列经过这 $k$ 个比较器之后最长上升子序列至少为 $n-1$ 。

$n\le 50,k\le 10$ 。

由于最终的排列只能 $(n-1)^2+1$ 种。于是我们枚举每一个最终序列。然后对于每一个合法排列 $p$ ，倒着枚举 $i=k\sim 1$ ：

若 $p_{u_i}>p_{v_i}$ ，不合法，舍去。
否则，经过比较器之前的序列既可以是 $p_{u_i}$ 和 $p_{v_i}$ ，也可以是 $p_{v_i}$ 和 $p_{u_i}$ ，搜索即可。

容易发现最多有不超过 $n^22^k$ 种合法序列。所以复杂度 $O(n^22^k)$ 。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=51,M=2510;
int n,k,P,u[N],v[N],a[N],ans;
void init(){for(int i=1;i<=n;i++)a[i]=i;}
void dfs(int x){
    if(!x){ans=(ans+1)%P;return ;}
    if(a[u[x]]>a[v[x]])return ;
    swap(a[u[x]],a[v[x]]);dfs(x-1);
    swap(a[u[x]],a[v[x]]);dfs(x-1);
}
void WZH(){
    scanf("%d%d%d",&n,&k,&P);
    for(int i=1;i<=k;i++)scanf("%d%d",u+i,v+i);
    ans=0;init();dfs(k);
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++)swap(a[j-1],a[j]),dfs(k);
        init();swap(a[i],a[i-1]);
        for(int j=i-2;j>=1;j--)swap(a[j+1],a[j]),dfs(k);
        init();
    }
    printf("%d\n",ans);
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--)WZH();
    return 0;
}