Description

Input

Output

Sample Input

Sample Input1 25 4 4 1 2 3 2 1 1 1 2

Sample Output

Sample Output1 2 10 6?

Data Constraint

Solution

這題需要找到三個結(jié)論。

1.在最優(yōu)劃分中，某個眾數(shù)只會在不同集合中出現(xiàn)最多一次（同一個眾數(shù)只能出現(xiàn)在相同集合中），否則可以將相同眾數(shù)的兩個集合合并來減小答案。

2.若首先選出了若干的數(shù)作為每個集合的眾數(shù)，那么這個劃分方案合法當且僅當這些眾數(shù)的個數(shù)之和大于等于其余沒選的數(shù)中個數(shù)的最大值，因為如果最多個數(shù)的數(shù)都能被分成若干個集合，那么其他的數(shù)也一定存在一種方案將它們放進眾數(shù)集合中。

3.所有刪去的數(shù)字形成的連續(xù)段數(shù)不超過

證明：

對于某個刪去的數(shù)字，若它右邊的數(shù)字沒有被刪掉，那么右邊的這個數(shù)字一定大于前面刪去的數(shù)字之和，否則它就會被刪去。而未被刪去的數(shù)字之和大于等于V且小于等于2V（由值域決定），而刪去的數(shù)字在其中共出現(xiàn)了平方次，因此刪去的數(shù)字形成的連續(xù)段只有根號級別。

這樣，為了優(yōu)化在序列上暴力找刪除的連續(xù)段，我們改為在線段樹上找刪除的連續(xù)段：在線段樹上的沒一個節(jié)點維護區(qū)間的a[i]的和，所有a[i]的價值和（2^i），a[i]的最大值和最小值。若刪去當前節(jié)點中的最小值都不能滿足條件，直接退出；然后先遍歷右節(jié)點，能刪就刪（這時用a[i]的和以及價值刪），再遍歷左節(jié)點。

總復(fù)雜度，實際上很難卡滿。

總結(jié)：審清題->找結(jié)論->推式子/轉(zhuǎn)化條件->得出算法

?

Code?

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define I int #define ll long long #define ls x<<1 #define rs ls|1 #define F(i,a,b) for(I i=a;i<=b;i++) #define Fd(i,a,b) for(I i=a;i>=b;i--) #define mem(a,b) memset(a,b,sizeof a) #define N 200004 #define mo 998244353 using namespace std; ll n,a[N],s[N],g[N],mx,q,p,x,y,tot,ans; struct seg{I mx,mn;ll s,v;}f[N*4]; void R(ll &x){x=0;I w=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-') w=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}x*=w; } void up(I x){f[x]=seg{max(f[ls].mx,f[rs].mx),min(f[ls].mn,f[rs].mn),f[ls].s+f[rs].s,(f[ls].v+f[rs].v)%mo}; } void cge(I k,I v,I x=1,I l=1,I r=n){if(l==r){f[x]=seg{v,v,v,g[l]};return;}I M=l+r>>1;if(k<=M) cge(k,v,ls,l,M);else cge(k,v,rs,M+1,r);up(x); } void del(I x=1,I l=1,I r=n){if(tot-f[x].mn<f[1].mx) return;if(tot-f[x].s>=f[1].mx){tot-=f[x].s;ans=(ans-f[x].v+mo)%mo;return;}I M=l+r>>1;del(rs,M+1,r),del(ls,l,M); } I main(){freopen("imperishable.in","r",stdin);freopen("imperishable.out","w",stdout);R(n),R(n);g[0]=1;F(i,1,n){R(a[i]);g[i]=g[i-1]*2%mo;cge(i,a[i]);}tot=f[1].s,ans=g[n+1]=(g[n]*2-2+mo)%mo;del();printf("%lld\n",ans);R(q);F(i,1,q){R(x),R(y);cge(x,y);tot=f[1].s,ans=g[n+1];del();printf("%lld\n",ans);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的6846. 【2020.11.02提高组模拟】旅人1970的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。