题解归档 - cf813E

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf813E
• 本地来源：problems/cf813E/idea.md
• 题目链接：https://codeforces.com/contest/813/problem/E
• 原始标题：813E Army Creation

思路

813E Army Creation

题意

长度为 (n) 的数组 (a_i) 表示战士类型。平衡军队：每种类型至多选 (k) 个（子集，不要求连续）。

(q) 次查询区间 ([l,r])（输入经 last 混淆），求区间内能组成的最大平衡军队人数。

思路

单次查询答案：

[
\sum_{t} \min(\text{cnt}_t(l,r),\, k)
]

其中 (\text{cnt}_t(l,r)) 为类型 (t) 在 ([l,r]) 中出现次数。

持久化线段树（主席树）：

• 值域为类型 (1..10^5)，叶子存该类型在当前前缀中的出现次数。
• root[i]：处理完前 (i) 个元素后的版本；单点 +1 更新，每次 (O(\log V)) 新节点。
• 查询 ([l,r])：对 root[l-1] 与 root[r] 同步 DFS，在叶子上取 (\min(\text{差值}, k)) 累加。

注意：不能对两棵树的 sum 直接相减，因为 (\min(c_r,k)-\min(c_l,k) \neq \min(c_r-c_l,k))。

模板

见 lib/数据结构(主席树-持久化线段树).cpp（单点改 + 双版本区间查询）。

复杂度

• 建树：(O(n \log V))
• 单次查询：(O(\log V))
• 空间：(O(n \log V))

验证

• 样例：✅
• 对拍：30 组随机（Kali remote）；500 组因 SSH 中断未完成，无 WA 反例

结果

• 待提交 / 待 AC 后更新 lib/ 与 contests/813/state.json

代码

来源：problems/cf813E/solution.cpp

/* Author: likely
 * Time: 2026-06-08 02:41:29
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=100005,maxa=100005,maxnode=4000005;
struct tnode{
    ll ls,rs,sum;
};
tnode t[maxnode+5];
ll ptr,root[maxn+5],a[maxn+5],n,k,q,i,x,y,l,r,last,ans;
ll upd(ll u,ll l,ll r,ll pos){
    ll v=++ptr;
    t[v]=t[u];
    if(l==r){
        t[v].sum++;
        return v;
    }
    ll mid=(l+r)/2;
    if(pos<=mid) t[v].ls=upd(t[u].ls,l,mid,pos);
    else t[v].rs=upd(t[u].rs,mid+1,r,pos);
    t[v].sum=t[t[v].ls].sum+t[t[v].rs].sum;
    return v;
}
ll query(ll u,ll v,ll l,ll r){
    if(l==r) return min(t[v].sum-t[u].sum,k);
    ll mid=(l+r)/2;
    return query(t[u].ls,t[v].ls,l,mid)+query(t[u].rs,t[v].rs,mid+1,r);
}
int main(){
    cin>>n>>k;
    for(i=1;i<=n;i++) cin>>a[i];
    root[0]=0;
    for(i=1;i<=n;i++) root[i]=upd(root[i-1],1,maxa,a[i]);
    cin>>q;
    last=0;
    while(q--){
        cin>>x>>y;
        l=((x+last)%n)+1;
        r=((y+last)%n)+1;
        if(l>r) swap(l,r);
        last=ans=query(root[l-1],root[r],1,maxa);
        cout<<ans<<"\n";
    }
    return 0;
}