LGP3602 Koishi Loves Segments
原题链接：Koishi Loves Segments
分析
类似反悔贪心吧……就是你排一下序，然后动态维护……做完了！所以，mhh \operatorname{mhh}mhh是对的[拜谢]
正解
#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintN=2000005;intn,m;structnode1{intl,r;}a[N];booloperator<(constnode1&tmp1,constnode1&tmp2){returntmp1.l<tmp2.l;}structnode2{intp,x;}b[N];booloperator<(constnode2&tmp1,constnode2&tmp2){returntmp1.p<tmp2.p;}multiset<int>s;signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m;for(inti=1;i<=n;i++){cin>>a[i].l>>a[i].r;}sort(a+1,a+n+1);for(inti=1;i<=m;i++){cin>>b[i].p>>b[i].x;}sort(b+1,b+m+1);intans=n;for(inti=1,j=1;i<=m;i++){while(j<=n&&a[j].l<=b[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--;}}cout<<ans;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_{j=i}^{i+k}h_jx×k−j=i∑i+khj最小……那不是平均数具有很大的优势吗？为啥是中位数😭
那可以直接写了吧……拿一个主席树就行了……
正解
#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintN=100005,M=1000005;intn,k,h[N];structtree{intp,ls,rs,val;}tr[N<<5];inttot;intrt[N];structpresident_tree{voidpushup(intp){tr[p].p=tr[tr[p].ls].p+tr[tr[p].rs].p;tr[p].val=tr[tr[p].ls].val+tr[tr[p].rs].val;return;}voidmodify(intp,intpre,intl,intr,ints){if(l==r){tr[p].p=tr[pre].p+1;tr[p].val=tr[pre].val+s;return;}intmid=(l+r)>>1;if(s<=mid){tr[p].ls=++tot;tr[p].rs=tr[pre].rs;modify(tr[p].ls,tr[pre].ls,l,mid,s);}else{tr[p].ls=tr[pre].ls;tr[p].rs=++tot;modify(tr[p].rs,tr[pre].rs,mid+1,r,s);}pushup(p);}intquery_kth(intpre,intp,intl,intr,intk){if(l==r)returnl;intmid=(l+r)>>1;inttmp=tr[tr[p].ls].p-tr[tr[pre].ls].p;if(tmp>=k){returnquery_kth(tr[pre].ls,tr[p].ls,l,mid,k);}else{returnquery_kth(tr[pre].rs,tr[p].rs,mid+1,r,k-tmp);}}intquery(intpre,intp,intl,intr,intk){if(l==r){returnmin(k,tr[p].p-tr[pre].p)*l;}intmid=(l+r)>>1;inttmp=tr[tr[p].ls].p-tr[tr[pre].ls].p;if(tmp>=k){returnquery(tr[pre].ls,tr[p].ls,l,mid,k);}else{returntr[tr[p].ls].val-tr[tr[pre].ls].val+query(tr[pre].rs,tr[p].rs,mid+1,r,k-tmp);}}}T;intsum[N],total;signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>k;for(inti=1;i<k;i++){cin>>h[i];rt[i]=++tot;total+=h[i];T.modify(rt[i],rt[i-1],0,1000000,h[i]);}intans=0x3f3f3f3f3f3f3f3f;intpos=0,val=0;for(inti=k;i<=n;i++){cin>>h[i];rt[i]=++tot;total+=h[i]-h[i-k];T.modify(rt[i],rt[i-1],0,1000000,h[i]);intp=(k+1)>>1;inttmp=T.query_kth(rt[i-k],rt[i],0,1000000,p);intres=T.query(rt[i-k],rt[i],0,1000000,p);res=total-2*res-(k-p)*tmp+p*tmp;if(res<ans){ans=res;pos=i;val=tmp;}}cout<<ans<<'\n';for(inti=1;i<=n;i++){if(pos<i+k&&pos>=i){cout<<val<<'\n';}else{cout<<h[i]<<'\n';}}}千万不要写错ans的初值！！！
