AT_abc470_c

· · 题解

题意简述

有序列 (A_1,A_2,\dots,A_N)，初始时所有值都为 0，接下来有 Q 个操作。每次操作为以下两种操作之一：

对于每次操作，输出操作后序列的异或和。

1 \le N \le 5 \times 10^5 1 \le Q \le 5 \times 10^5

思路

众所周知，异或结合上加减法并没有太好的性质，异或应该只是用来减少输出的工具，所以这道题的关键不是异或。

考虑到这是一个序列问题，算法复杂度大概可以做到 O(Q\log{N}) 的量级，加之异或具有结合律，那么很容易想到使用线段树维护区间异或和。

然后你发现第一个操作非常容易解决，线段树单点修改即可。

但是第二个操作有些复杂，线段树不容易直接维护，我们考虑挖掘这道题目的更多性质。

然后我们发现操作一每次最多将一个变量增加 1，而操作二事实上只对值不为 0 的变量进行操作，并且每次操作都将值减少 1。

由于值的总和从 0 开始，最多到 Q，如果我们能只对值不为 0 的变量操作，可以发现操作二的单点修改最多操作 Q 次。因为每操作一次值的总和就减 1，而值的总和又恒为自然数。这里运用到了均摊复杂度的思想。

那么怎么让我们的线段树只修改值不为 0 的位置呢？如果你做过上帝造题的七分钟 2 /花神游历各国的话，你会发现这道题也可以用类似的方法。记录区间内有没有不为 0 的值，如果在操作二修改时发现进入了值全为 0 的区间，直接返回，这样就保证了复杂度正确。

代码

赛时代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll f[2000010][2];
ll a[500010];
ll n;
//void build(ll l,ll r,ll i)
//{
//  if(l==r)
//  {
//      f[i][0]=a[l];
//      if(a[l]>=1)
//          f[i][1]=1;
//      return;
//  }
//  ll m=(l+r)/2;
//  build(l,m,i*2);
//  build(m+1,r,i*2+1);
//  f[i][0]=f[i*2][0]^f[i*2+1][0];
//  f[i][1]=f[i*2][1]||f[i*2+1][1];
//}
void out()
{
    for(int i=1;i<=n*2;i++)
        cout<<i<<':'<<f[i][0]<<' '<<f[i][1]<<'\n';
    //  cout<<'\n';
}
void add(ll l,ll r,ll L,ll R,ll i,ll x)
{

    //out();
    if(r<l)
        return;
    if(R<l||r<L)
        return;
    if(x==-1&&f[i][1]==0)
        return;

    if(l==r)
    {
        //out();
        //cout<<l<<' '<<r<<' '<<i<<' '<<'\n'; 
        f[i][0]+=x;
        //out();
        if(f[i][0]>=1)
            f[i][1]=1;
        else
            f[i][1]=0;
        //out();
        //cout<<l<<' '<<r<<' '<<i<<' '<<f[i][0]<<' '<<f[i][1]<<'\n';
        return;
    }
    //out();
    int m=(l+r)/2;
    add(l,m,L,R,i*2,x);
    add(m+1,r,L,R,i*2+1,x);
    //cout<<i*2<<' '<<f[i*2][0]<<' '<<i*2+1<<' '<<f[i*2+1][0]<<'\n';
    f[i][0]=f[i*2][0]^f[i*2+1][0];
    f[i][1]=f[i*2][1]||f[i*2+1][1];
    //cout<<l<<' '<<r<<' '<<i<<' '<<f[i][0]<<' '<<f[i][1]<<'\n';
}
int main() 
{
    ll q;
    cin>>n>>q;
    //build(1,n,1);
    while(q--)
    {
        ll op;
        cin>>op;
        if(op==1)
        {
            ll p;
            cin>>p;
            add(1,n,p,p,1,1);
        }
        else
            add(1,n,1,n,1,-1);
        cout<<f[1][0]<<'\n';
    }
    return 0;   
}

写的很乱，不适合学习，主要是因为一不小心把 f 数组的第二维开成了 0，导致调试了半天。

注意到通过时间 520 ms

通过记录

整理后的代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll f[2000010][2];
ll a[500010];
ll n;
void add(ll l,ll r,ll L,ll R,ll i,ll x)
{
    //把两个操作和一起了，x=1就是操作1，x=-1就是操作2
    if(r<l)
        return;
    if(R<l||r<L)
        return;
    if(x==-1&&f[i][1]==0)//保证了复杂度正确
        return;
    if(l==r)
    {
        f[i][0]+=x;
        if(f[i][0]>=1)
            f[i][1]=1;
        else
            f[i][1]=0;
        return;
    }
    int m=(l+r)/2;
    add(l,m,L,R,i*2,x);
    add(m+1,r,L,R,i*2+1,x);
    f[i][0]=f[i*2][0]^f[i*2+1][0];//区间异或和
    f[i][1]=f[i*2][1]||f[i*2+1][1];//记录区间是否有非0值
}
int main() 
{
    ll q;
    cin>>n>>q;
    //build(1,n,1);
  //不需要build函数，因为初始值都是0
    while(q--)
    {
        ll op;
        cin>>op;
        if(op==1)
        {
            ll p;
            cin>>p;
            add(1,n,p,p,1,1);
        }
        else
            add(1,n,1,n,1,-1);
        cout<<f[1][0]<<'\n';//f[1][0]就是区间1到n的异或和
    }
    return 0;   
}

结语

还是一道不错的复杂度均摊加势能线段树的题目的，通过这道题目后可以尝试一下花神游历各国这道类似的题目。希望这篇题解对你有帮助。

感谢@Seauy老师帮我检查题解。

辛苦管理员审核了。