题解：CF2006D Iris and Adjacent Products

· · 题解

这个题初始的 idea 是 irris 的（关于“可以重排使得邻项积不超过 i”的重排方案）。后来讨论了一下出到了序列上，做法是我给的。

这个题卡空间是因为开二维数组常数太大了，做法几乎不变的同时，隐形强制要求小常数避免卡常。当然莫队可以直接解决。

题意：对于一个序列，你可以做单点修改（任何时刻值域都是 [1,k]）或序列重排。定义权值为最小的单点修改次数使得任意相邻两个数的乘积不超过 k。区间查询权值。1\le \sum n,\sum q\le 10^5,1\le k\le 10^6。

解法：考虑最优的重排方式，先放最大值，然后最小值，然后次大值等等地交替放。于是序列合法当且仅当每个 i 大值和 i 小值的乘积都不超过 k（\bf{1\le i\le \frac n2}）。

上述结论的证明：

先证明最大值放第一个更优。如果存在一个同样可行的方法最大值不在第一个，我们可以把以最大值结尾的这个前缀 reverse，直接达成不劣的效果。

再考虑最小值放第二个更优。如果存在一个同样可行的解最小值不在第二个，我们考虑当前的第二个和最小值，由于都可以放在 max 旁边，所以对于所有数都可以放它们旁边，是等价的。于是交换这两个数结果不变。

所有数都可以放到最小值旁边，于是变成 n'=n-2 的子问题，于是得证。

设 c(l,r) 表示值域在 [l,r] 的值的个数。考虑转化：对于每个 i\le \sqrt k，都有 cnt(1,i)\ge cnt(\frac{k}{i},k)。这个 cnt 本质不同只有 2\sqrt k 个，暴力前缀和求出来，然后列个式子就好了（修改显然是把 \max 改成 1，这是容易的），需要注意长度为奇数时最中间一项不需要考虑，也就是上面的 cnt 需要和 \frac n2 取 \min。推推式子就能算出来了，而且每个 i 独立。

考虑卡空间，由于各 i 独立，离线后枚举 i 再枚举询问，空间 O(n+q+\sqrt k)。时间复杂度 O((n+q)\sqrt k)。莫队也是可以的，空间线性。

#include<bits/stdc++.h>
using namespace std;
#define MOD         998244353
#define speMOD      2933256077ll
#define pii         pair<int,int>
#define all(v)      v.begin(),v.end()
#define pb          push_back
#define REP(i,b,e)  for(int i=(b);i<(int)(e);++i)
#define over(x)     {cout<<(x)<<endl;return;}
#define lowbit(x)   ((x)&(-(x)))
#define cntbit(x)   __builtin_popcount(x)
#define rf(v)       shuffle(all(v),sd);
#define deal(v)     sort(all(v));v.erase(unique(v.begin(),v.end()),v.end())
#define lbound(v,x) lower_bound(all(v),x)-v.begin()
int n,q,r;
int a[300005];
int sum[300005];
int ql[300005],qr[300005];
int ans[300005];
int cnt[300005],cnt2[300005];
void Main() {
    cin>>n>>q>>r;
    REP(i,0,n)cin>>a[i];
    sum[0]=0;
    int B=sqrt(r);
    REP(i,0,n)sum[i+1]=sum[i]+(a[i]<=B);
    REP(i,0,q){
        int x,y;
        cin>>x>>y;
        --x,--y;
        ql[i]=x;qr[i]=y;
        ans[i]=0;
        if(sum[y+1]-sum[x]<(y-x+1)/2)ans[i]=(y-x+1)/2-sum[y+1]+sum[x];
    }
    REP(i,0,B){
        REP(j,0,n+1)cnt[j]=cnt2[j]=0;
        REP(j,0,n){
            cnt[j+1]=cnt[j]+(a[j]<=i);
            cnt2[j+1]=cnt2[j]+(a[j]<=r/(i+1));
        }
        REP(j,0,q){
            int x=ql[j],y=qr[j],l=y-x+1;
            int c1=cnt2[y+1]-cnt2[x],c2=cnt[y+1]-cnt[x];
            ans[j]=max(ans[j],min((l-c1-c2+1)/2,l/2-c2));
        }
    }
    REP(i,0,q)cout<<ans[i]<<' ';
    cout<<endl;
}
void TC() {
    int tc=1;
    cin>>tc;
    while(tc--){
        Main();
        cout.flush();
    }
}
signed main() {
    return cin.tie(0),cout.tie(0),ios::sync_with_stdio(0),TC(),0;
}
/*
1. CLEAR the arrays (ESPECIALLY multitests)
2. DELETE useless output
 */