【loj 3059】【hnoi 2019】シーケンス
4809 ワード
テーマ
長さ\(n\)のシーケンス\(A\)を与えます.
新しいシーケンスを作成する必要があります.満足:$B_{i}\le B_｛i＋1｝(1\le i\lt n)$ $\sum_｛i=1｝^{n}(Aui-Bui)^2$最小 問題を解く出題者と題解はここにあります.http://15283746.blog.uoj.ac/blog/4966 証明書を整理してセットしただけです. Part 1 主に最適な戦略を議論する: 引理一:すべての\(Bui\)が同じ\(x\)に等しいと要求されたら、$x = \fraac{\sum_{i=1}{n}A i}{n}$証明:\(x\)について書く二次関数で証明できます. の定理の1:解答はきっと多くの厳格な上昇の等値の段で、つまり各段の\(B\)は同じで、しかもこの\(A\)の平均値\(v(A)\)に等しいです.証明:隣接する等値ブロックの値が厳密に異なるため、二次関数の性質によって、平均値に近い方向に調整できることは間違いない. は、任意のシーケンスを延長した後、元のシーケンスが拡張されたシーケンスの答えに対する貢献は、元のシーケンスの最適な答えより小さくないことを意味する.証明:最適なので明らかでないと矛盾します. 引用三:等値区間の区分が一意である.証明:(-u-)リニア計画モデルを構築し、$B_i\le B_｛i＋1｝という不等式グループの空間における解は凸状であり、最適な点は和円(((((((((℃、A_2、...))\)の接点に相当する. の定理二:下記の構造方法は最適である.平均値を重みとする単調なスタックを維持し、一つの点を加えると、単調性を満たさないなら、スタックの最後と現在の区間を結合し、このプロセスを繰り返し、最後に区間を単調なスタックに追加する.証明:最適な区分は\(H[x,y]\)となり、上記のような戦略の区分を\(H'[x,y]\)とし、要約を考慮する.両方とも\(H=H'\)を満足すると仮定し、\(i=n\)の場合:1.\(H'\)の中に二つ以上の等値ブロックが含まれていれば、二つの長さ\(H_1'\)と\(H_2');に分けられます.引理二によって、きっと一番いいのが分かります.構造方式のこの二つの区間は必ず直接につなぎ合わせられます.しかも$H'=H_1'+H_2'$2.\(H'\)の中に等しいブロックが一つしかない場合、任意の等しいブロックよりも大きいと証明する必要がある\(H\)は全部優れていません.\(i\)は区分\(H\)の最後の満足\(i\)と\(i＋1\)の異なるブロックの点であると仮定する.\(H'[1,i]\)を考慮して、\(i\)を設定するブロックは\([j,i]\)であり、\(i＋1\)から\(n\)の間に必ず最初の\(k\)が存在します.\([j,i]\)と\(i＋1,k);;$v[j,i]\lt v[i＋1,n] , v[j,i]\ge v[i＋1,k]$したがって、$v[k＋1,n]\gt v[j,i]\ge v[i＋1,k]$だから\(H'[1,k]+H'[k+1,n]\)はきっと合法的で、しかも\(H\)より優れています. これまでは修正しない時に問題を解決できます. Part 2 は、\([1,i-1]\)と\([i,i]\)と\([i＋1,n]\)をどのように合併するかを考え、まず二つの区間を統合する場合について議論する. 定理三:両区間の和の分割方式のいずれかの区分は、サブ区間でも必ず分割点である.左から右に実行すると、必ず左区間の区分点が多くなりません.右から左へ同理して、三点引理によって、複数の区間に広めることができます. 引用三に基づいて、二つの区間を\([1,mid]\)と\([mid+1,n]\)とし、先に\(H'[1,mid-1]\)と\(H'[mid+1,n]\)を処理してもいいです.定理三によって、意味区間要素を変更しやすいように直接に、最終的に結合されるのは、左区間の一部分\Lu 0区間平均を表します. 引理四:右区間の$R\(に加入すると、\)L_を設定します.0$はこの時点でマージされた左エンドポイントで、1.合法的な条件は$v[L_0,R]\gt v_です.｛L 0−1｝ドルで、しかも二分割性があります.2.\(L_0\)は\(v[L,R]\)を最大にする\(L\)です.証明:スタックは単増量であり、合併過程において、加入点の価値の変化は単調で増加しないので、12の証明が得られます. 固定理四:右の1つの等値ブロック\(R\)、\(L\)はリード四の中の\(L_0\)であり、もし:1.\(Rは\(L,R)\ge v{R+1}、\(R\ge R_0\)があれば、\(R\ge R_0\)が満たされていると証明されています(v[L,\\r\r\r\r\r\r\r\r\r\\\\\r\r\r\\\\r\r\r\\r\\\\r\r\r\r\\\\r\\r\\\\r\r\r\r\r\r\r\r\r\\\\\\r\はい、要約仮説\(R\)満足して、左端点を\(L\)とし、\(R＋1\)に対して左端点を\(L'\)とし、引用4と仮説があります.\(v[L',R]\le v[L,R]\lt v{R＋1}\)を得るため、$v[L',R＋1]\lt v唠 四と定理四は中間に修正点\(i\)がある時も適用されます. ですので、[1,i-1]の単調さと[i＋1,n]の単調なスタック(nから1をやり遂げてから後でスタックを退きます)を見つけられます.二分割すればいいです.
長さ\(n\)のシーケンス\(A\)を与えます.
新しいシーケンスを作成する必要があります.満足:
#include
#define ll long long
#define mod 998244353
using namespace std;
const int N=100010;
int n,m,ny[N],pl,pr,len[N],ansl[N],ansr[N],pre[N],ql,qr,ans[N];
struct query{
int x,y,id;
query(int _x=0,int _y=0,int _id=0):x(_x),y(_y),id(_id){};
bool operator =(const data&A)const{return y*A.x>=A.y*x;}
}A[N],L[N],R[N],pR[N],sL[N],sR[N],psR[N],X,Y,Z;
data getL(int l,int r){return sL[r]-sL[l-1];}
data getR(int l,int r){return sR[r]-sR[l-1];}
int cal(data now){
int x=now.x,y=now.y%mod,z=now.z%mod;
int v=(ll)y*ny[x]%mod;
return (z-(ll)v*y*2%mod+(ll)v*v%mod*x%mod+mod)%mod;
}
void lowerL(){
int l=1,r=pl+1;
while(l>1;
Z=Y+getL(mid,pl);
if(Z<=L[mid-1])r=mid-1;
else l=mid;
}
Z=Y+getL(ql=l,pl);
}
void lowerR(){
int l=1,r=pr+1;
while(l>1;
Y=X+getR(mid,pr);
lowerL();
if(Z>=R[mid-1])r=mid-1;
else l=mid;
}
Y=X+getR(qr=r,pr);
lowerL();
}
int main(){
// freopen("sequence.in","r",stdin);
// freopen("sequence.out","w",stdout);
scanf("%d%d",&n,&m);ny[1]=1;
for(int i=2;i<=n;++i){ny[i]=1ll*(mod-mod/i)*ny[mod%i]%mod;}
for(int i=1;i<=n;++i){
int x;scanf("%d",&x);
A[i]=data(1,x,(ll)x*x%mod);
}
for(int i=1;i<=m;++i){
int x,y;scanf("%d%d",&x,&y);
Q[i]=query(x,y,i);
}
sort(Q+1,Q+m+1);
L[0]=data(1,0,0);
R[0]=data(1,1e9+1,0);
for(int i=n;~i;--i){
data now=A[i];
while(now>=R[pr])now=now+R[pr--];
len[i]=++pr;
pR[i]=R[pr];R[pr]=now;
psR[i]=sR[pr];sR[pr]=sR[pr-1]+now;
pre[i]=ansr[pr];ansr[pr]=(ansr[pr-1]+cal(now))%mod;
}
ans[0]=ansr[pr];
for(int i=1,tl=0,tr=1;i<=m;++i){
while(tr