[atAGC049F]Happy Sequence

定义$L=2\cdot 10^{5}$，$g(x)=\sum_{i=1}^{n}|b_{i}-x|-|a_{i}-x|$，则合法当且仅当$\forall 0\le x\le L,g(x)\ge 0$，由此也可以得到$0\le a'_{i}\le L$（证明略）

初始令$a'_{i}=0$（即带来初始代价$\sum_{i=1}^{n}c_{i}a_{i}^{2}$）让$a'_{i}$增加1的代价为$c_{i}(2(a'_{i}-a_{i})+1)$，而这个操作的效果是让$g(x)$（$0\le x\le a'_{i}$）减小1，让$g(x)$（$a'_{i}<x\le L$）增加1（注意：以上$a'_{i}$都指操作前的数）

定义$C_{i,x}$表示让$a'_{i}=x$再增加1的代价，观察到$a'_{i}$增加1的代价单调递增，同时效果单调递减（减小的范围增大，而增加的范围减小），因此我们不需要限制只有选择了$C_{i,x-1}$才能选择$C_{i,x}$，最优方案下自然会选择$C_{i,x-1}$

换言之，即有$o(nL)$个操作，操作之间没有限制，每一个操作有代价和效果，使得$g(x)\ge 0$

记$f_{x}$表示$x$操作使用次数，则有$g(x)=g'(x)+\sum_{i=0}^{x-1}f(i)-\sum_{i=x}^{L}f(i)\ge 0$，令$S=\sum_{i=0}^{L}f(i)$，即$\sum_{i=x}^{L}f(i)\le \lfloor\frac{S+g'(x)}{2}\rfloor$，记作$\lim_{x}$

$g'(x)$很好求，然后有$S=\sum_{i=1}^{n}b_{i}$（即$\sum_{i=1}^{n}a'_{i}=\sum_{i=1}^{n}b_{i}$），证明也比较简单，考虑$g(0)$和$g(L)$即可，因此$\lim_{x}$的值就可以确定，同时这也就是合法的充要条件

换言之，题意又简化为有$nL$个物品$C_{i,x}$，使得每一个后缀所选的物品数小于等于限制，最终选择$S$个物品，最小化费用和

不难得到一个$o(nL\log_{2}nL)$的做法，即维护一个可重集$S$，从后往前枚举$x$，将这对应的$n$个物品加入集合中，然后再从$S$中删除最大的若干个数直至集合大小小于等于$\lim_{x}$，最终剩下的$S$个元素和即为答案

但这样的复杂度仍然太大，我们需要利用$c_{i}$比较小的性质，考虑用以下方法来描述$S$：

记$mx$表示当前$S$中最大值，$sz$表示当前集合大小，$sum_{x}$表示数字$x$已经被删除的次数（特别的，对于$x>mx$的部分不保证正确性，但此时必然已经删光）

定义$calc(x,v)$表示求$\sum_{i=1}^{n}[C_{i,x}=v]$，可以通过预处理$o(5)$求出其关于$x$的后缀和和$v$的前缀和

令$sz+=\sum_{i=0}^{mx}calc(x,i)$，对$sz$与$\lim_{i}$大小关系分类讨论：

1.$sz\ge \lim_{i}$，则统计$\sum_{i=x}^{n}calc(i,mx)-sum_{mx}$，判断是否大于$sz-\lim_{i}$，若大于则直接删除$sz-\lim_{i}$个，否则全部删除并重复此过程

2.$sz<\lim_{i}$，先令$sum_{mx}=\sum_{i=x+1}^{n}calc(i,mx)$，然后若$calc(x,mx)\ge lim_{i}-sz$，则加入$\lim_{i}-sz$个（删除$calc(x,mx)-(\lim_{i}-sz)$个），否则全部加入并重复此过程

考虑时间复杂度，以下证明复杂度为$o(n+LK^{2})$（其中$K$为常数，$K=\max c_{i}\le 5$）

预处理复杂度显然为$o(n)$，然后令$mx_{i}$表示第$i$后$mx$的值，计算复杂度考虑$mx$的改变，由于每一次$mx$加减都会带来$o(K)$的复杂度，因此总复杂度即为$o(K\sum_{i=1}^{L}|mx_{i}-mx_{i-1}|)$

令$nd_{x}=\lim_{x}-\lim_{x+1}$，根据$g(x)$的计算过程，不难得到$0\le nd_{x}\le n$和$nd_{x}\le nd_{x-1}$

令$f_{x}$为$C_{i,x}$中的第$nd_{x}$小，$f'_{x}$为$C_{i,x}$中第$nd_{x+1}$小，先考虑$\sum_{i=1}^{L}|f_{i}-f_{i-1}|$：

考虑$C_{i,x-1}$和$C_{i,x}$，即为前者中每一个数再加上$2c_{i}$，假设$f'_{x-1}<f_{x}-2K$，那么严格比$f'_{x}$小的数至少有$nd_{x}$个（即$f'_{x}$以及小于等于其的数），与其为第$nd_{x}$小矛盾，因此即可以得到$f_{x}-2K\le f'_{x-1}$

然后根据$nd_{x}\le nd_{x-1}$，可以得到$f'_{x-1}\le f_{x-1}$，代入即$f_{x}-2K\le f_{x-1}$，即$f_{x}-f_{x-1}\le 2K$

将$f_{i}$看成一条折线，由于$|f_{i}|\le o(LK)$，因此下降的部分小于等于上升的部分+$o(LK)$，而由于上面的式子，就可以得到$\sum_{i=1}^{L}|f_{i}-f_{i-1}|\le o(Lk)$

可以证明$mx_{i}$在$mx_{i+1}$和$f_{i}$之间（类似于偏移，虽然不一定偏到$f_{i}$，但总会偏一点），如果把这个过程反过来，类似的，也可以得到$mx_{i+1}$在$mx_{i}$和$f_{i+1}$之间

对四个数的情况模拟，不难发现一定是$f_{i}$和$f_{i+1}$包含了$mx_{i}$和$mx_{i+1}$，因此$|mx_{i}-mx_{i+1}|\le f_{i}-f_{i+1}|$，而后者累加为$o(LK)$，前者也是$o(LK)$，总复杂度即为$o(n+LK^{2})$

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define L 200000

 4 #define N (L+5)

 5 #define ll long long

 6 int n,a[N],b[N],c[N],suma[11][N],sumb[N],sum[N*20];

 7 ll ans,g[N],lim[N];

 8 int calc(int x,int v){

 9     int ans=0;

10     for(int i=1;i<=5;i++){

11         if ((v%i==0)&&(v%(2*i))){

12             int s=x-(v/i-1)/2;

13             if ((s<0)||(s>L))continue;

14             if (!s)ans+=suma[i][0];

15             else ans+=suma[i][s]-suma[i][s-1];

16         }

17     }

18     return ans;

19 }

20 int calc_sufx(int x,int v){

21     int ans=0;

22     for(int i=1;i<=5;i++)

23         if ((v%i==0)&&(v%(2*i))){

24             int s=(v/i-1)/2;

25             if (L-s>=0){

26                 if (x-s<=0)ans+=suma[i][min(L-s,L)];

27                 else ans+=suma[i][min(L-s,L)]-suma[i][min(x-s-1,L)];

28             }

29         }

30     return ans;

31 }

32 int divdn(int x,int y){

33     if (x>=0)return x/y;

34     return (x-y+1)/y;

35 }

36 int calc_prev(int x,int v){

37     int ans=0;

38     for(int i=1;i<=5;i++){

39         int s=x-divdn(divdn(v,i)-1,2);

40         if (s>L)continue;

41         if (s<=0)ans+=suma[i][L];

42         else ans+=suma[i][L]-suma[i][s-1];

43     }

44     return ans;

45 }

46 int main(){

47     scanf("%d",&n);

48     for(int i=1;i<=n;i++)scanf("%d",&a[i]);

49     for(int i=1;i<=n;i++)scanf("%d",&b[i]);

50     for(int i=1;i<=n;i++)scanf("%d",&c[i]);

51     for(int i=1;i<=n;i++)suma[c[i]][a[i]]++;

52     for(int i=1;i<=5;i++)

53         for(int j=1;j<=L;j++)suma[i][j]+=suma[i][j-1];

54     ll s=0;

55     for(int i=1;i<=n;i++)s+=b[i];

56     for(int i=1;i<=n;i++)sumb[b[i]]++;

57     for(int i=1;i<=L;i++)sumb[i]+=sumb[i-1];

58     g[0]=s;

59     for(int i=1;i<=L;i++)g[i]=g[i-1]+sumb[i-1]-(n-sumb[i-1]);

60     for(int i=0;i<=L;i++)g[i]-=1LL*i*n;

61     for(int i=0;i<=L;i++)lim[i]=(s+g[i])/2;

62     int mx=0;

63     ll sz=0;

64     for(int i=L;i>=0;i--){

65         sz+=calc_prev(i,mx);

66         while (sz>lim[i]){

67             int las=calc_sufx(i,mx)-sum[mx+L*10];

68             if (las>sz-lim[i]){

69                 sum[mx+L*10]+=sz-lim[i];

70                 sz=lim[i];

71                 break;

72             }

73             mx--;

74             sz-=las;

75         }

76         while (sz<lim[i]){

77             mx++;

78             sum[mx+L*10]=calc_sufx(i+1,mx);

79             int las=calc(i,mx);

80             if (las>=lim[i]-sz){

81                 sum[mx+L*10]+=las-(lim[i]-sz);

82                 sz=lim[i];

83                 break;

84             }

85             sz+=las;

86         }

87     }

88     for(int i=-L*10;i<=mx;i++)ans+=1LL*(calc_sufx(0,i)-sum[i+L*10])*i;

89     for(int i=1;i<=n;i++)ans+=1LL*c[i]*a[i]*a[i];

90     printf("%lld",ans);

91 }

巴特西

[atAGC049F]Happy Sequence

最新文章

热门文章