题解：P12399 「FAOI-R9」少年游

· · 题解

题目链接

P12399 「FAOI-R9」少年游

解题思路 & 参考代码

提供一个和官解不一样的做法。

好像比官解要优秀。

设修改前的最大子段和为 lst。

注意到我们修改单个数字后，设此时最大子段和为 now，则会有以下三种情况：

那么我们可以 2n 次扫一遍得到此时的最大子段和的值及其选取哪个子段。

然后我们考虑把整个序列都变成正数即可，这里操作次数为 2n 次。

此时由于整个序列都为正数，则可以依次询问每个下标找出 a 序列每个数的值，这里询问次数为 n 次。

总询问次数 5n 次，不过事实上这个是跑不满的。

下面是这个部分的参考代码：

ll n;
ll tag[1010];
ll ans[1010];
ll lst[1010];
ll get(ll l,ll r)
{
    forl(i,l,r)
        ans[i]*=-1;
    ll S=0,aa=0;
    forl(i,1,n)
        S=max(0ll,S+ans[i]),
        Max(aa,S);
    forl(i,1,n)
        cout<<ans[i]<<' ';
    cout<<endl;
    return aa;
}
ll ask(ll l,ll r,ll pd=1)
{
    cout<<"? "<<l<<' '<<r<<endl;
    if(pd)
        tag[l]^=1,tag[r+1]^=1;
//  ll num=get(l,r);
//  cout<<"get: "<<num<<endl;
    return rd();
}
ll num;
ll l,r;
ll my_ans[100010];
void _clear(){}
/*
2
1 2
1 -2

*/
void solve()
{
    _clear();
    cin>>n;
//  n=3;
//    forl(i,1,n)
//      lst[i]=ans[i]=rand_lr(-1e6,1e6);
//    cout<<"REAL: ";
//    forl(i,1,n)
//      cout<<ans[i]<<" ";
//    cout<<endl;
    forl(i,1,n)
//      lst[i]=ans[i]=rd(),
        my_ans[i]=0;
    forl(i,0,n+5)
        tag[i]=0;
    ask(1,1);
    num=ask(1,1);
    l=n+1,r=0;
    forl(i,1,n)
    {
        ll now=ask(i,i);
        if(now>num)
        {
            Min(l,i),
            Max(r,i);
            num=now;
        }
        if(now<num)
        {
            Min(l,i),
            Max(r,i),
            ask(i,i);
        }
    }
//    cout<<"part 2:\n";
    ask(1,1);
    num=ask(1,1);
    forr(i,l-1,1)
    {
        ll now=ask(i,i);
        if(now>num)
        {
            num=now;
            continue;
        }
        num=ask(i,i);
    }
//    cout<<"part 3:\n";
    forl(i,r+1,n)
    {
        ll now=ask(i,i);
        if(now>num)
        {
            num=now;
            continue;
        }
        num=ask(i,i);
    }
//    cout<<"now------\n";
    forl(i,1,n)
    {
        ll now=ask(i,i,0);
        my_ans[i]=num-now;
        num=now;
    }
    forl(i,1,n)
        tag[i]^=tag[i-1];
    forl(i,1,n)
        if(tag[i])
            my_ans[i]*=-1;
    cout<<"! ";
    forl(i,1,n)
        cout<<my_ans[i]<<' ';
    cout<<endl;
//    forl(i,1,n)
//    {
//      if(my_ans[i]!=lst[i])
//      {
//          cout<<"Wrong Answer!\n";
//          cout<<n<<endl;
//          forl(j,1,n)
//              cout<<lst[j]<<" ";
//          cout<<endl;
//          exit(0);
//      }
//  }
//  cout<<"AC!\n";
}

这部分显然不够优秀，我们考虑如何将前 4n 次询问优化到 2n 次的级别。

考虑随机化。

考虑设置一个随机的轮数 B，在这里我们取 B = 12。

此时我们只需要找到任意一个可以影响最大子段和的数字即可。

对于每轮我们随机 5 次下标 pos，若 5 次都没随到一个会影响最大子段和的下标，说明最大子段和长度较小，此时我们直接进行一次 1 n 即可，进行这种操作后，最大子段和长度一定变大，因此一定能随出来这样的一个下标。

剩下的我们直接往左往右扩展即可，由于此时正负数分布较均匀，因此询问次数显然严格小于 2n 次（跑满是 2n 次）。

上文随机化部分实际上 60 次之内就能随到。

那么再加上计算答案的 n 次，我们询问总次数是 n + 2n + 60 次，实际上完全跑不满，最终最大点只用了 2965 次询问。

此部分参考代码：

ll n;
ll tag[1010];
ll ans[1010];
ll lst[1010];
ll get(ll l,ll r)
{
    forl(i,l,r)
        ans[i]*=-1;
    ll S=0,aa=0;
    forl(i,1,n)
        S=max(0ll,S+ans[i]),
        Max(aa,S);
    forl(i,1,n)
        cout<<ans[i]<<' ';
    cout<<endl;
    return aa;
}
ll ask(ll l,ll r,ll pd=1)
{
    cout<<"? "<<l<<' '<<r<<endl;
    if(pd)
        tag[l]^=1,tag[r+1]^=1;
//  ll num=get(l,r);
//  cout<<"get: "<<num<<endl;
    return rd();
}
ll num;
ll l,r;
ll my_ans[100010];
void _clear(){}
/*
2
1 2
1 -2

*/
void solve()
{
    _clear();
    cin>>n;
//  n=3;
//    forl(i,1,n)
//      lst[i]=ans[i]=rand_lr(-1e6,1e6);
//    cout<<"REAL: ";
//    forl(i,1,n)
//      cout<<ans[i]<<" ";
//    cout<<endl;
    forl(i,1,n)
//      lst[i]=ans[i]=rd(),
        my_ans[i]=0;
    forl(i,0,n+5)
        tag[i]=0;
//    ask(1,1);
//    num=ask(1,1);
    l=n+1,r=0;
//    forl(i,1,n)
//    {
//        ll now=ask(i,i);
//        if(now>num)
//        {
//            Min(l,i),
//            Max(r,i);
//            num=now;
//        }
//        if(now<num)
//        {
//            Min(l,i),
//            Max(r,i),
//            ask(i,i);
//        }
//    }
//    cout<<"part 2:\n";
    ll B=12;
    forl(__,1,B)
    {
        ask(min((__-1)*((1000+B-1)/B)+1,n),min(__*((1000+B-1)/B),n));
//      ask(1,n);
        num=ask(1,n);
        ll pd=0;
        forl(_,1,5)
        {
            ll pos=rand_lr(1,n);
            ll A=ask(pos,pos);
            if(A>num)
            {
                l=r=pos;
                pd=1;
                break;
            }
            if(A<num)
            {
                ask(pos,pos);
                l=r=pos;
                pd=1;
                break;
            }
        }
        if(pd)
            break;
    }
    // B=20;
    // forl(__,1,B)
    // {
    //  ask(min((__-1)*((1000+B-1)/B)+1,n),min(__*((1000+B-1)/B),n));
    //  ask(1,n);
    //  num=ask(1,n);
    //  ll pd=0;
    //  forl(_,1,400/B)
    //  {
    //      ll pos=rand_lr(1,n);
    //      ll A=ask(pos,pos);
    //      if(A>num)
    //      {
    //          l=r=pos;
    //          pd=1;
    //          break;
    //      }
    //      if(A<num)
    //      {
    //          ask(pos,pos);
    //          l=r=pos;
    //          pd=1;
    //          break;
    //      }
    //  }
    //  if(pd)
    //      break;
    // }
    if(r==0)
        l=r=rand_lr(1,n);
    ask(1,1);
    num=ask(1,1);
    forr(i,l-1,1)
    {
        ll now=ask(i,i);
        if(now>=num)
        {
            num=now;
            continue;
        }
        num=ask(i,i);
    }
//    cout<<"part 3:\n";
    forl(i,r+1,n)
    {
        ll now=ask(i,i);
        if(now>num)
        {
            num=now;
            continue;
        }
        num=ask(i,i);
    }
//    cout<<"now------\n";
    forl(i,1,n)
    {
        ll now=ask(i,i,0);
        my_ans[i]=num-now;
        num=now;
    }
    forl(i,1,n)
        tag[i]^=tag[i-1];
    forl(i,1,n)
        if(tag[i])
            my_ans[i]*=-1;
    cout<<"! ";
    forl(i,1,n)
        cout<<my_ans[i]<<' ';
    cout<<endl;
//    forl(i,1,n)
//    {
//      if(my_ans[i]!=lst[i])
//      {
//          cout<<"Wrong Answer!\n";
//          cout<<n<<endl;
//          forl(j,1,n)
//              cout<<lst[j]<<" ";
//          cout<<endl;
//          exit(0);
//      }
//  }
//  cout<<"AC!\n";
}