赛时题解

Cowreography G

首先考虑$k=1$，用队列维护位置即可$O(n)$解决，直接依次统计$1$位置的差即可。

然后$k=t$时，似乎不能这么匹配，因为计算距离时有：

ceil((double)(i-t)/k)

所以我们要将余数相同的匹配。

考虑一下，余数不同的数是否会互相干扰，似乎不会，因为区间不一样，但相同的数是会的，所以还要按距离排一下。相交必然不劣于包含（交换常见规则）。

lower_bound要用set自带的。因为algorithm库里的复杂度$O(n)$

代码是简单的：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
int n,k,ans;
char a[2][N];
multiset<pair<int,int> > q[2];
signed main(){
    cin>>n>>k>>a[0]+1>>a[1]+1;
    for(int i=1;i<=n;i++){
        if(a[0][i]==a[1][i]) continue;
        if(a[0][i]=='1'){
            if(q[1].size()){
                auto it=q[1].lower_bound({i%k,0});
                if(it==q[1].end()) it=q[1].begin();
                q[1].erase(it);
                ans+=ceil((double)(i-(it->second))/k);
            }
            else q[0].insert({i%k,i});
        }
        if(a[1][i]=='1'){
            if(q[0].size()){
                auto it=q[0].lower_bound({i%k,0});
                if(it==q[0].end()) it=q[0].begin();
                q[0].erase(it);
                ans+=ceil((double)(i-(it->second))/k);
            }
            else q[1].insert({i%k,i});
        }
    }
    cout<<ans;
}

后记，写出题后证明一下结论，

为什么要选择>=模数的最小值，或者+k满足的。

分析两次询问间的贡献，贡献首先是增长的，则将贡献最容易加一的值删掉，即使这个值与后面同余，那更难加一的值也不会更劣，而前面的无论如何都会加一。

例子

5 4
11000
00011

Grass Segments

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,ans[N],b[N];
struct Eg{
    int l,r,k,op;
    bool operator < (const Eg& B) const{
        if(l==B.l) return r<B.r;
        return l<B.l;
    }
}e[N];
vector<int> g;
vector<int> nums;
struct Node
{
    int l, r;
    int cnt;
}tr[N * 40];
int root[N], idx;
int find(int x)
{
    return lower_bound(nums.begin(), nums.end(), x) - nums.begin();
}
int build(int l, int r)
{
    int p = ++ idx;
    if (l == r) return p;
    int mid = l + r >> 1;
    tr[p].l = build(l, mid), tr[p].r = build(mid + 1, r);
    return p;
}
int query(int q, int p, int l, int r, int k)
{
    if(k>nums[r]) return tr[q].cnt-tr[p].cnt;
    if(k<=nums[l]) return 0;
    int cnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt;
    int mid = l + r >> 1, ans=0;
    if (k <= nums[mid]) ans+=query(tr[q].l, tr[p].l, l, mid, k);
    else {
        ans+=cnt;
        ans+=query(tr[q].r, tr[p].r, mid + 1, r, k);
    }
    return ans;
}
int insert(int p, int l, int r, int x)
{
    int q = ++ idx;
    tr[q] = tr[p];
    if (l == r)
    {
        tr[q].cnt ++ ;
        return q;
    }
    int mid = l + r >> 1;
    if (x <= mid) tr[q].l = insert(tr[p].l, l, mid, x);
    else tr[q].r = insert(tr[p].r, mid + 1, r, x);
    tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt;
    return q;
}

int main(){
    scanf("%d", &n);
    for(int i=1;i<=n;i++){
        int l,r,k;
        scanf("%d%d%d", &l,&r,&k);
        e[i]={l,r,k,i};
    }
    sort(e+1,e+n+1);
    for (int i = 1; i <= n; i ++ )
    {
        b[i]=e[i].r-e[i].l;
        nums.push_back(b[i]);
    }
    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());
    root[0] = build(0, n - 1);
    for (int i = 1; i <= n; i ++ )
        root[i] = insert(root[i - 1], 0, nums.size() - 1, find(b[i]));
    for(int i=1;i<=n;i++){
        if(i!=n){
            int l=i,r=n;
            while(l<r){
                int mid=(l+r+1)/2;
                if(e[i].k<=e[i].r-e[mid].l) l=mid;
                else r=mid-1;
            }
            ans[e[i].op]+=l-i;
            int ww=e[i].k;
            ans[e[i].op]-=query(root[l], root[i], 0, nums.size() - 1, ww);
        }
        int rks=lower_bound(g.begin(),g.end(),e[i].l+e[i].k)-g.begin();
        ans[e[i].op]+=g.size()-rks;
        auto pt=lower_bound(g.begin(),g.end(),e[i].r);
        g.insert(pt,e[i].r);
    }
    for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
}