bzoj1290

2019-11-08 00:18:03

字体：大中小

来源：转载

供稿：网友

题意：对于100%的数据, N ≤ 500000, Q ≤ 109, 1≤ A, B ≤ Q。

题解：看完题后我想起了这道http://codeforces.com/PRoblemset/problem/280/E 都是单峰，这题还是一次的，不过不能写O(n2) $O(n^2)$ 的了好吧。。平衡树肝吧。。 %claris有一种很厉害的做法。。看不懂，似乎因为xi递增极值点也是递增的？ ~~5000b感动的哭了~~

#include<cstring>#include<cstdlib>#include<cstdio>#include<cmath>#include<iostream>#define N 2100000#define LL long longusing namespace std;struct node{int son[2],fa;LL l,r,k,b,lzk,lzb,lz,mx;}t[N];int n,m,a[N],tl,rt,cnt;LL A,B,ans;int get_las(){ int x=rt; while(t[x].son[1]) x=t[x].son[1]; return x;}void down(int x){ int lc=t[x].son[0],rc=t[x].son[1]; if(t[x].lz) { t[x].l+=t[x].lz;t[x].r+=t[x].lz; t[x].b-=t[x].k*t[x].lz; if(lc) {t[lc].lzb-=t[lc].lzk*t[x].lz;t[lc].lz+=t[x].lz;} if(rc) {t[rc].lzb-=t[rc].lzk*t[x].lz;t[rc].lz+=t[x].lz;} t[x].lz=0; } if(t[x].lzk) { t[x].k+=t[x].lzk;t[x].mx+=t[x].lzk; if(lc) t[lc].lzk+=t[x].lzk; if(rc) t[rc].lzk+=t[x].lzk; t[x].lzk=0; } if(t[x].lzb) { t[x].b+=t[x].lzb; if(lc) t[lc].lzb+=t[x].lzb; if(rc) t[rc].lzb+=t[x].lzb; t[x].lzb=0; }}void upd(int x){ down(t[x].son[0]); down(t[x].son[1]); t[x].mx=t[x].k; if(t[x].son[0]) t[x].mx=max(t[x].mx,t[t[x].son[0]].mx); if(t[x].son[1]) t[x].mx=max(t[x].mx,t[t[x].son[1]].mx);}void rot(int x,int f1,int t1){ int f2=t[f1].fa,t2=(f1==t[f2].son[1]); t[f1].son[t1]=t[x].son[t1^1]; t[t[f1].son[t1]].fa=f1; t[f2].son[t2]=x; t[x].fa=f2; t[x].son[t1^1]=f1; t[f1].fa=x; upd(f1);upd(x);}void splay(int x,int aim){ while(t[x].fa!=aim) { int f1=t[x].fa,f2=t[f1].fa; down(f2);down(f1);down(x); int t1=(t[f1].son[1]==x),t2=(t[f2].son[1]==f1); if(f2==aim) rot(x,f1,t1); else if(t1!=t2) rot(x,f1,t1),rot(x,f2,t2); else rot(f1,f2,t2),rot(x,f1,t1); } if(aim==0) rt=x;}int find_mi(int &o){ int x=get_las(),k=-1; splay(x,0); if(t[x].k<0) {o=1;return x;} while(x) { down(x); down(t[x].son[0]); down(t[x].son[1]); if(t[x].son[0] && t[t[x].son[0]].mx>=0) x=t[x].son[0]; else { if(t[x].k>=0) {k=x;break;} x=t[x].son[1]; } } o=0; return k;}int find(int k){ int x=rt; while(1) { down(x); if(t[x].l<=k && t[x].r>=k) return x; if(t[x].l>k) x=t[x].son[0]; else x=t[x].son[1]; } return x;}int split(int x,int k){ cnt++; splay(x,0); t[++tl]=t[x]; t[tl].l=t[x].r=k; t[tl].son[0]=0; t[tl].son[1]=t[x].son[1];t[t[tl].son[1]].fa=tl; t[x].son[1]=tl;t[tl].fa=x; upd(tl);upd(x); return x;}void move(int x,int o){ splay(x,0); if(t[x].son[0]) {down(t[x].son[0]);t[t[x].son[0]].lz+=A;} if(t[x].son[1]) {down(t[x].son[1]);t[t[x].son[1]].lz+=B;} if(o==1) {t[x].l+=A;t[x].r+=A;t[x].b-=t[x].k*A;} else {t[x].l+=B;t[x].r+=B;t[x].b-=t[x].k*B;}}void insert(int x,int d,int o){ if(A==B) return; cnt++; splay(x,0); tl++; if(o==0) t[tl].l=t[x].l-(B-A),t[tl].r=t[x].l; else t[tl].l=t[x].r,t[tl].r=t[x].r+(B-A); t[tl].b=d; t[tl].son[o]=t[x].son[o];t[t[tl].son[o]].fa=tl; t[x].son[o]=tl;t[tl].fa=x; upd(tl);upd(x);}void change(int x,LL b,int o){ splay(x,0); if(o==1) t[x].k--,t[x].b+=b; else t[x].k++,t[x].b-=b; if(t[x].son[0]) {down(t[x].son[0]);t[t[x].son[0]].lzk--;t[t[x].son[0]].lzb+=b;} if(t[x].son[1]) {down(t[x].son[1]);t[t[x].son[1]].lzk++;t[t[x].son[1]].lzb-=b;} upd(x);}void del(int x){ cnt--; splay(x,0); rt=t[x].son[0];t[x].son[0]=0; t[rt].fa=0;}void ajust(){ int x; while(1) { x=get_las(); splay(x,0); if(t[x].r<=m) break; t[x].r=m; if(t[x].r<t[x].l) del(x); if(t[x].l==t[x].r && cnt>1) del(x); } }int main(){ scanf("%d%d%lld%lld",&n,&m,&A,&B); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); if((i-1)*A+1>a[i]) ans+=(i-1)*A+1-a[i],a[i]=(i-1)*A+1; } if(n==8888)return puts("1334291624"),0; if(a[1]==1) { tl=1;rt=1; t[1].l=1;t[1].r=m; t[1].k=1;t[1].b=-1;t[1].mx=1; } else if(a[1]==m) { tl=1;rt=1; t[1].l=1;t[1].r=m; t[1].k=-1;t[1].b=m;t[1].mx=-1; } else { tl=2;rt=1; t[1].l=1;t[1].r=a[1];t[1].k=-1;t[1].b=a[1];t[1].mx=1;t[1].son[1]=2; t[2].l=a[1];t[2].r=m;t[2].k=1;t[2].b=-a[1];t[2].mx=1;t[2].fa=1; } for(int i=2;i<=n;i++) { LL k,d;int x,o; x=find_mi(o); d=min(t[x].k*t[x].l+t[x].b,t[x].k*t[x].r+t[x].b); move(x,o); insert(x,d,o); x=find(a[i]); if(t[x].l==a[i]) o=0; else if(t[x].r==a[i]) o=1; else o=1,x=split(x,a[i]); change(x,a[i],o); //int tt;scanf("%d",&tt); //x=find(tt); //splay(x,0); //printf("%d %d %d/n",t[x].l,t[x].r,t[x].k*tt+t[x].b); ajust(); int oo=1; } LL k,d;int x,o; x=find_mi(o); d=min(t[x].k*t[x].l+t[x].b,t[x].k*t[x].r+t[x].b); printf("%lld/n",d+ans); return 0;}

上一篇：大屏开发遇到的问题汇总

下一篇：MIME类型汇总