题解：CF2006D Iris and Adjacent Products

wrkwrkwrk · 2024-10-05 17:32:49 · 题解

相关人员：验题人

先考虑对于一次询问如何做。根据数论分块知识可以知道本质不同的数的种类是 O(\sqrt k) 个。改变一个数一定是贪心地改成 1。

考虑模拟构造过程。倒数第 i 类数旁边的数一定是正数第 i 类数前。从最大和最小的数贪心连接。贪心取得最大的数在最前面，如果前面放下的最后一个数是大数，则将其放入这个周期处理。之后交替计算放入，小的数放完大的数变化，直到计算完成就是答案。

对于每次询问，只需要计算出每类数各有几个即可。

考虑到直接用前缀和计算答案也许会 MLE，故以大小为 B 分块即可。

时间复杂度 O(q(B+\sqrt R))。

验题代码：

#include<bits/stdc++.h>
using namespace std;
namespace _wrk{;
#define int long long
int b[100005];
const int B=32;
signed p[101005/B][2503];
int re[2503];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n,q,R;
        cin>>n>>q>>R;
        for(int i=1;i<=n;i++){
            cin>>b[i];
        }
        vector<int>u;
        for(int l=1;l<=R;l=(R/(R/l))+1){
            u.push_back(l);
        }
        for(int i=B;i<=n;i+=B){
            int h=i/B;
            for(int j=1;j<=u.size();j++){
                p[h][j]=p[h-1][j];
            }
            for(int w=i-B+1;w<=i;w++){
                p[h][upper_bound(u.begin(),u.end(),b[w])-u.begin()]++;
            }
        }
        while(q--){
            int l,r;
            cin>>l>>r;
            for(int i=1;i<=u.size();i++)re[i]=0;
            for(;l%B!=1&&l<=r;l++){
                re[upper_bound(u.begin(),u.end(),b[l])-u.begin()]++;
            }
            for(;r%B&&l<=r;r--){
                re[upper_bound(u.begin(),u.end(),b[r])-u.begin()]++;    
            }

            if(l<=r)for(int i=1;i<=u.size();i++){
                re[i]+=p[r/B][i]-p[(l-1)/B][i];
            }

            int a=0,ans=0;
            int h=0;
            int ll=1,rr=u.size();
            while(ll<rr){

                a+=re[ll];
                if((re[rr]||re[ll])){
                    if(h){
                        ans++;a++;h=0;
                    }
                    int w=re[rr];
                    int c=min(a,w);
                    a-=c;w-=c;
                    int p=w/2;
                    ans+=p;
                    h=w-p*2;
                }
                ll++;rr--;
            }
            if(ll==rr){
                if(re[ll]&&h) ans++;
            }
            cout<<ans<<' '; 

        }
        cout<<'\n';
    }
    return 0;
}
}
signed main(){
       return _wrk::main();
}

（注：本题原来空间限制 128MB，之后出题人看到我的代码想搞成32MB，但是上面的 B=32，正好卡进去。）