LGP3602 Koishi Loves Segments原题链接Koishi Loves Segments分析类似反悔贪心吧……就是你排一下序然后动态维护……做完了所以mhh ⁡ \operatorname{mhh}mhh是对的[拜谢]正解#includebits/stdc.h#defineintlonglongusingnamespacestd;constintN2000005;intn,m;structnode1{intl,r;}a[N];booloperator(constnode1tmp1,constnode1tmp2){returntmp1.ltmp2.l;}structnode2{intp,x;}b[N];booloperator(constnode2tmp1,constnode2tmp2){returntmp1.ptmp2.p;}multisetints;signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinnm;for(inti1;in;i){cina[i].la[i].r;}sort(a1,an1);for(inti1;im;i){cinb[i].pb[i].x;}sort(b1,bm1);intansn;for(inti1,j1;im;i){while(jna[j].lb[i].p){s.insert(a[j].r);}while(!s.empty()*s.begin()b[i].p){s.erase(s.begin());}while((longlong)s.size()b[i].x){s.erase(--s.end());ans--;}}coutans;return0;}LGP3466 [POI 2008] KLO-Building blocks原题链接[POI 2008] KLO-Building blocks分析就是我们其实可以枚举然后在线段树上找……别急这是对的吗那你要是这样的话其实只是把O ( m n ) O(mn)O(mn)降到了O ( n 2 ) O(n^2)O(n2)优化不多……怎么贪呢……换句话说我要找到一个x xx使得x × k − ∑ j i i k h j x\times k-\sum\limits_{ji}^{ik}h_jx×k−ji∑ik​hj​最小……那不是平均数具有很大的优势吗为啥是中位数那可以直接写了吧……拿一个主席树就行了……正解#includebits/stdc.h#defineintlonglongusingnamespacestd;constintN100005,M1000005;intn,k,h[N];structtree{intp,ls,rs,val;}tr[N5];inttot;intrt[N];structpresident_tree{voidpushup(intp){tr[p].ptr[tr[p].ls].ptr[tr[p].rs].p;tr[p].valtr[tr[p].ls].valtr[tr[p].rs].val;return;}voidmodify(intp,intpre,intl,intr,ints){if(lr){tr[p].ptr[pre].p1;tr[p].valtr[pre].vals;return;}intmid(lr)1;if(smid){tr[p].lstot;tr[p].rstr[pre].rs;modify(tr[p].ls,tr[pre].ls,l,mid,s);}else{tr[p].lstr[pre].ls;tr[p].rstot;modify(tr[p].rs,tr[pre].rs,mid1,r,s);}pushup(p);}intquery_kth(intpre,intp,intl,intr,intk){if(lr)returnl;intmid(lr)1;inttmptr[tr[p].ls].p-tr[tr[pre].ls].p;if(tmpk){returnquery_kth(tr[pre].ls,tr[p].ls,l,mid,k);}else{returnquery_kth(tr[pre].rs,tr[p].rs,mid1,r,k-tmp);}}intquery(intpre,intp,intl,intr,intk){if(lr){returnmin(k,tr[p].p-tr[pre].p)*l;}intmid(lr)1;inttmptr[tr[p].ls].p-tr[tr[pre].ls].p;if(tmpk){returnquery(tr[pre].ls,tr[p].ls,l,mid,k);}else{returntr[tr[p].ls].val-tr[tr[pre].ls].valquery(tr[pre].rs,tr[p].rs,mid1,r,k-tmp);}}}T;intsum[N],total;signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinnk;for(inti1;ik;i){cinh[i];rt[i]tot;totalh[i];T.modify(rt[i],rt[i-1],0,1000000,h[i]);}intans0x3f3f3f3f3f3f3f3f;intpos0,val0;for(intik;in;i){cinh[i];rt[i]tot;totalh[i]-h[i-k];T.modify(rt[i],rt[i-1],0,1000000,h[i]);intp(k1)1;inttmpT.query_kth(rt[i-k],rt[i],0,1000000,p);intresT.query(rt[i-k],rt[i],0,1000000,p);restotal-2*res-(k-p)*tmpp*tmp;if(resans){ansres;posi;valtmp;}}coutans\n;for(inti1;in;i){if(posikposi){coutval\n;}else{couth[i]\n;}}}千万不要写错ans的初值