[CF2157C] Meximum Array 2 题解

翻译一下，

(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

区间包裹，当然暴力找的复杂度也是正确的。

code

CPP

#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;
}

[CF2157C] Meximum Array 2 题解

文章操作

相关推荐

评论

[CF2157C] Meximum Array 2 题解