题解归档 - cf2230D

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

• 本地编号：cf2230D
• 本地来源：problems/cf2230D/idea.md
• 题目链接：https://codeforces.com/contest/2230/problem/D
• 原始标题：cf2230D

思路

cf2230D

pattern: online state buckets.

claim: For any valid left endpoint, the whole state is only k, the number of episodes both have already watched. When processing day i, a new left endpoint starts with k=0. If a_i=b_i=x, all active starts with k=x-1 advance to k=x. If a_i!=b_i, active starts with k=a_i-1 or k=b_i-1 become invalid. The number of active starts after day i is exactly the number of good segments ending at i.

necessary: As long as a segment is valid, Alice and Bob have watched the same prefix 1..k. On the next day, exactly one watches iff exactly one schedule value equals k+1, which invalidates the segment.

sufficient: The bucket transition simulates the process for every still-valid left endpoint. Equal values move both together; unequal values only remove the states where one side would advance.

brute/check: For small n, enumerate all L,R and simulate the watching process directly, then compare with the online bucket result.

edge: States with k=n remain active forever because no schedule value can be n+1.

代码

来源：problems/cf2230D/solution.cpp

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=500005;
ll a[maxn+5],b[maxn+5],cnt[maxn+5];
int main(){
    ll t,n,i,x,y,zc,cur,ans;
    scanf("%lld",&t);
    while(t--){
        scanf("%lld",&n);
        for(i=1;i<=n;i++) scanf("%lld",&a[i]);
        for(i=1;i<=n;i++) scanf("%lld",&b[i]);
        for(i=0;i<=n;i++) cnt[i]=0;
        cur=ans=0;
        for(i=1;i<=n;i++){
            cnt[0]++;
            cur++;
            x=a[i];
            y=b[i];
            if(x==y){
                zc=cnt[x-1];
                cnt[x-1]=0;
                cnt[x]+=zc;
            }
            else{
                zc=cnt[x-1];
                cur-=zc;
                cnt[x-1]=0;
                zc=cnt[y-1];
                cur-=zc;
                cnt[y-1]=0;
            }
            ans+=cur;
        }
        printf("%lld\n",ans);
    }
    return 0;
}