题解：CF356A Knight Tournament

wjr_jok · 2024-05-31 17:38:40 · 题解

分块，但由于是区间修改，并且自己不会被自己打败，所以有相当多细节要处理。

首先肯定要逆序处理，这样才能保证取得每个骑士最先打败他的骑士编号。

开一个数组 xg 记录整块的修改，对于整块直接对 xg 数组所对应的值进行修改即可。

对于散块，我们直接将它所处的整块的单块值全部修改，否则我们后面输出时无法判断单块值与整块修改值的先后顺序，所以我们要保证单块值和整块修改值只有一个生效。

还有一种情况就是含有胜利者的块，由于自己不会被自己打败，所以这个块也要单独处理，方法同散块。

每次处理完散块和含有胜利者的块我们都将这个块的整块修改值清零，以便后面更新值。

输出时注意判断单块值和整块修改值那个生效。

Code

#include<bits/stdc++.h>
using namespace std;
int n,m,jl,cnt=1;
int l[300001],r[300001],s[300001],cc[300001];
int x[300001],y[300001],fk[300001],xg[300001];
int main(){
    cin>>n>>m;
    for(int i=1;i<=(int)sqrt(n);i++){
        cnt++;
        x[cnt]=y[cnt-1]+1;
        y[cnt]=x[cnt]+(int)sqrt(n)-1;
        for(int j=x[cnt];j<=y[cnt];j++){
            fk[j]=cnt;
        }
    }
    if(y[cnt]<n){
        cnt++;
        x[cnt]=y[cnt-1]+1;
        y[cnt]=n;
        for(int i=x[cnt];i<=y[cnt];i++){
            fk[i]=cnt;
        }
    }
    for(int i=m;i>=1;i--){//逆序处理
        cin>>l[i]>>r[i]>>s[i];
    }
    for(int i=1;i<=m;i++){
        for(int j=l[i];j<=min(r[i],y[fk[l[i]]]);j++){//左散块
            if(j==s[i]){
                if(xg[fk[l[i]]]){//判断整块修改值是否生效
                    cc[j]=xg[fk[l[i]]];
                }
            }
            else{
                cc[j]=s[i];
            }
        } 
        if(xg[fk[l[i]]]){//这个整块剩下的部分
            for(int j=x[fk[l[i]]];j<l[i];j++){
                cc[j]=xg[fk[l[i]]];
            }
        }
        if(r[i]<y[fk[l[i]]]&&xg[fk[l[i]]]){
            for(int j=r[i]+1;j<=y[fk[l[i]]];j++){
                cc[j]=xg[fk[l[i]]];
            }
        }
        xg[fk[l[i]]]=0;
        if(fk[l[i]]!=fk[r[i]]){
            for(int j=x[fk[r[i]]];j<=r[i];j++){//右散块
                if(j==s[i]){
                    if(xg[fk[r[i]]]){//同上
                        cc[j]=xg[fk[r[i]]];
                    }
                }
                else{
                    cc[j]=s[i];
                }
            } 
            if(xg[fk[r[i]]]){//这个整块剩下的部分
                for(int j=r[i]+1;j<=y[fk[r[i]]];j++){
                    cc[j]=xg[fk[r[i]]];
                }
            }
            xg[fk[r[i]]]=0;
        }
        if(fk[l[i]]!=fk[s[i]]&&fk[r[i]]!=fk[s[i]]){
            for(int j=x[fk[s[i]]];j<=y[fk[s[i]]];j++){//含有胜利者的块
                if(j==s[i]){
                    if(xg[fk[s[i]]]){//还是同上
                        cc[j]=xg[fk[s[i]]];
                    }
                }
                else{
                    cc[j]=s[i];
                }
            }
            xg[fk[s[i]]]=0;
        }
        for(int j=fk[l[i]]+1;j<fk[r[i]];j++){//整块
            if(j==fk[s[i]]){
                continue;
            }
            xg[j]=s[i];
        }
    }
    for(int i=1;i<=n;i++){//输出
        if(!xg[fk[i]]){
            cout<<cc[i]<<" ";
        }
        else{
            cout<<xg[fk[i]]<<" ";
        }
    }
    return 0;
}