[CF2157C] Meximum Array 2 题解

aeiouaoeiu · 2025-11-23 21:52:40 · 题解

翻译一下，(1,l,r) 实际上就是 a[l,r] 中不能有 [0,k-1] 内的数，且必须有 k；(2,l,r) 实际上就是 a[l,r] 中必须有 [0,k-1] 中所有数，且不能有 k。对于 >k 的数没有限制。

若只有 c=1，将 a_i 全部赋值为 k 即可满足。

若只有 c=2，注意到令 a=[0,1,2,\ldots,k-1,0,1,2,\ldots]，即循环填入 [0,k-1] 时可以满足任意情况。

接下来尝试从 c=1 的情况中加入 c=2 的做法，初始时 a 为一个全为 k 的数组。显然若一个点同时被一个 c=1 和一个 c=2 区间包裹，这个点只能 >k，于是这些点直接赋值为 10^9。然后提取出所有没有被任何 (1,l,r) 包裹的点，循环填入 [0,k-1]，这样可以使 c=2 尽可能被满足。

具体实现时，可以通过前缀和求出哪些点被 c=1,c=2 区间包裹，当然暴力找的复杂度也是正确的。

::::info[code]

#include<bits/stdc++.h>
#define pb emplace_back
#define pob pop_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
const ll maxn=100007,ee=1e18;
ll n,k,q,su[maxn],a[maxn];
vector<pair<ll,ll> > vec;
int main(void){
    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll T=1; cin>>T;
    for(;T--;){
        cin>>n>>k>>q,vec.clear();
        for(ll i=1;i<=n;i++) su[i]=0,a[i]=k;
        for(ll i=1,c,l,r;i<=q;i++){
            cin>>c>>l>>r;
            if(c==1) su[l]++,su[r+1]--;
            else vec.pb(l,r);
        }
        for(ll i=1;i<=n;i++) su[i]+=su[i-1];
        for(ll i=1,cur=0;i<=n;i++)if(!su[i]) a[i]=cur,cur=(cur+1)%k;
        for(auto x:vec){
            for(ll i=x.first;i<=x.second;i++)if(su[i]) a[i]=1e9;
        }
        for(ll i=1;i<=n;i++) cout<<a[i]<<" "; cout<<"\n";
    }
    return 0;
}

::::