题解 CF1687C【Sanae and Giant Robot】

· · 题解

考虑设 c_i=a_i-b_i。原题的操作相当于：当某个 [l_i,r_i] 满足 \sum_{j=l_i}^{r_i}c_j=0 时，可以将 c_{l_i\sim r_i} 全部清零；目标则变成让 c_i 全部清零。

初看起来仍然有些无从下手。观察到条件 \sum_{j=l_i}^{r_i}c_j=0 是一个连续子段和的形式，可以去试着构造前缀和 s_i=\sum_{j=1}^ic_j。此时操作变为：当某个 s_{l_i-1}=s_{r_i} 时，可以将 s_{l_i\sim r_i} 全部赋值为 s_{r_i}；目标仍是让 s 全部清零。

可以注意到，当 s_{l_i-1}=s_{r_i}\neq 0 时，执行这个操作是不优的，我们只应该在 s_{l_i-1}=s_{r_i}=0 时进行操作。证明较为直观，读者可以稍微暂停一下，仔细想想这个过程。

接下来的事情就简单了：我们每次找一对 s_{l_i-1}=s_{r_i}=0，然后将 s_{l_i\sim r_i} 全部清零，直到不能执行操作为止。如果最终 s 全 0 则输出 YES，否则输出 NO。

考虑怎样快速维护上面的过程。一种做法是：用一个 set / 线段树维护所有还不是 0 的位置，每次区间清 0 时提取区间里剩下的非 0 位置，并考虑它们能否扩展新区间。每个区间只会被考虑 2 次，这样即可做到 O((n+m)\log n) 的时间复杂度。

#include<cstdio>
#include<vector>
#include<queue>
#include<set>

using namespace std;

typedef set<int>::iterator IT;
long long a[300000],b[300000],c[300000],s[300000];
vector<int> ed[300000];

int main()
{
    int TT=0;scanf("%d",&TT);
    while(TT--)
    {
        int n=0,m=0;scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
        for(int i=1;i<=n;i++)scanf("%lld",&b[i]);
        for(int i=1;i<=n;i++)c[i]=a[i]-b[i];
        for(int i=1;i<=n;i++)s[i]=s[i-1]+c[i];

        queue<int> q;set<int> S;
        for(int i=0;i<=n;i++)if(s[i])S.insert(i);else q.push(i);

        for(int i=1,l=0,r=0;i<=m;i++)
        {
            scanf("%d%d",&l,&r);ed[l-1].push_back(r),ed[r].push_back(l-1);
        }

        while(!q.empty())
        {
            int u=q.front();q.pop();
            for(int i=0;i<ed[u].size();i++)
            {
                if(s[ed[u][i]])continue;
                int l=min(ed[u][i],u),r=max(ed[u][i],u);
                IT it=S.lower_bound(l);
                while(it!=S.end()&&*(it)<=r)
                {
                    int p=*it;s[p]=0;q.push(p);
                    IT f=it;it++;S.erase(f);
                }
            }
        }
        puts(S.empty()?"YES":"NO");
        for(int i=0;i<=n;i++)ed[i].clear(); // 第一次这里写成 i = 1...n 然后 WA on test 4
    }
}

后记

挺有意思的题，感觉是整场里最有意思的题。后面的几个题要么有些钻牛角尖，要么太常规了。个人见解，欢迎交流。