ABC467

D计算几何给四个点其中两个pq属于一个圆另外两个rs属于另一个圆。问有没有可能这两个圆的圆心相同给了圆上两点可以确定圆心在这两点形成的线段的中垂线上。如果两个中垂线有交点则交点就是公共圆心。转化为直线交点问题如果两个中垂线不平行则一定有交点如果平行则只有两个直线重合时才有交点。于是问题转化成判断两个中垂线是否平行这可以用向量叉乘等于0来表示。获取两个直线的方向向量太麻烦的话由于都是中垂线可以直接看pq,rs两个向量是否平行是等价的。判断两个中垂线是否重合如果是手算这不难列出两个直线表达式然后看化简后是否相同。但是这是计算几何系数化简并不好做。考虑重合时满足的其他特征如果重合那么pq,rs平行且pq rs的中垂线相同那么pqsr构成一个梯形检查梯形的性质是好做的比如可以检查对角线相等且斜边相等计算线段长度就可以这是简单的structpoint{intx,y;voidread(){cinxy;}};intcross(via,vib){returna[0]*b[1]-a[1]*b[0];}voidsolve(){point p,q,r,s;p.read();q.read();r.read();s.read();vi pq{p.x-q.x,p.y-q.y};vi rs{r.x-s.x,r.y-s.y};if(cross(pq,rs)0){// cout ok ;if(dis(p.x,p.y,r.x,r.y)dis(q.x,q.y,s.x,s.y)dis(p.x,p.y,s.x,s.y)dis(q.x,q.y,r.x,r.y)){coutYes\n;}else{coutNo\n;}}else{coutYes\n;}}E取模 差分给定A,B一次操作可以给A的一个元素1问最少多少次操作使得AiAi1Bi(modM)A_iA_{i1}B_i(mod M)Ai​Ai1​Bi​(modM)注意到B是确定的那么这个约束其实规定了任意相邻A的递推关系也就是说确定了A1A_1A1​后面的就都确定了只需要考虑A1A_1A1​在[0,M−1][0,M-1][0,M−1]里取什么值。设AiA_iAi​最终加addiadd_iaddi​那么假设add1add_1add1​确定了add2add_2add2​为(A1A2−B1−add1)mod M(A_1A_2-B_1-add_1)\mod M(A1​A2​−B1​−add1​)modM类似地add3add_3add3​为(A2A3−B2−add2)mod M(A_2A_3-B_2-add_2)\mod M(A2​A3​−B2​−add2​)modMaddiadd_iaddi​是可以递推的这和前面的分析一样并且更关键的是注意每一轮递推都会和前一个addi−1add_{i-1}addi−1​符号相反因此add1add_1add1​1所有奇数下标的add都1所有偶数下标的add都-1那么add1add_1add1​1对整体答案的影响是奇数下标个数-偶数下标个数不妨设这个值为diff。此外考虑取模奇数位置1到M了会变成0或者说会-M偶数位置-1到-1了会变成M-1也就是会M。A1A_1A1​能取的值就是[0,M−1][0,M-1][0,M−1]那么add1取值范围也是add_1取值范围也是add1​取值范围也是[0,M-1]最终答案是一个关于最终答案是一个关于最终答案是一个关于add_1$的函数在没有触发取模规则时就是一个线性函数斜率diff触发取模规则的地方会有一些C突变。现在就是求这个函数的最值。考虑枚举自变量取值M1e9M1e9M1e9太大了不行但注意对于每个addiadd_iaddi​最多取模一次因此总的突变位置只有O(n)O(n)O(n)个剩余位置都是线性单增的最值点一定是出现在突变位置具体来说由于CC正负都有可能最值可能是突变点或前一个位置但绝不可能是线性单增过程中的某个点。于是我们用差分标记所有突变位置然后做一次前缀和累加只计算所有突变点和前一个点更新最值。中间的线性部分跳过线性部分的贡献可以O(1)O(1)O(1)计算。需要注意线性段有一种情况下可能是最值就是定义域右端点上要么收的特判一下这个点要么在记录差分的map力给m−1m-1m−1点也做一个0的标记这样也会计算这个点的答案。voidsolve(){intn,m;cinnm;via(n1),b(n);rep(i,1,n){cina[i];}rep(i,1,n-1){cinb[i];}intsum0;viadd(n1);rep(i,2,n){intxb[i-1]-a[i]-a[i-1]-add[i-1];x(x%mm)%m;sumx;add[i]x;}intanssum;intk0;rep(i,1,n){if(i%2){k;}else{k--;}}mapint,intmp;rep(i,1,n){if(i%2){mp[m-add[i]]-m;}else{mp[add[i]1]m;}}intpre0;if(!mp.count(m-1)){mp[m-1]0;}for(auto[cur,dif]:mp){if(curm)break;sum(cur-pre-1)*k;ansmin(ans,sum);sumkdif;ansmin(ans,sum);precur;}coutans;}F线段树 离散化 贪心带修规划问题每个任务准备需要ai准备完了还需要bi的延迟延迟期间可以干别的。问做完所有任务的最短时间。每次会修改一个任务的a或b询问新的结果。这种都先考虑不带修怎么做。这种题要是能做要么DP要么贪心。从简单的开始思考先考虑贪心。贪心策略无非就是按A或B的大小排序。实际答案就是按B排序可以用交换贪心证明在按B降序的基础上交换任意两个任务都是不会更优的。如果不带修按B排序后一次扫描即可确定答案。具体过程是每次在最后新增一个任务答案要么不变前面某个任务的延迟b很大覆盖了这个新任务的ab 要么是这个新任务的结束时间也就是所有a的和加上这个新任务的b发现这个过程可以用线段树维护。于是考虑线段树由于必须按B降序考虑用B作为线段树下标。考虑合并两个区间合并时类似前面的分析答案要么是左区间的答案最后一个结束的任务在左区间有一个超大b比右区间总时间都长要么是左区间的a的和加上右区间的延迟最后一个结束的任务在右区间左区间的b不用考虑了只考虑a带来的延迟于是线段树每个节点需要保存区间内a的和以及区间内所有任务的总时间。更新时如果改的是a改属性a。如果改的是b由于b是作为下标的意味着要在线段树上取消一个元素然后在另一个下标新增一个元素。由于b很大需要离散化再建树。这里有个问题一个b可能同时有多个任务但我们这个设计一个叶子只能对应一个元素所以需要区分b相同的多个元素。具体做法是离散化时对b,id二元组离散化不只对b离散化这样任何一个修改都对应线段树上一个唯一叶子。structTree{#definelsu1#definersu1|1structNode{intl,r,mx,sum;Node operator(constNodeo){Node res;res.mxmax(mx,o.mxsum);res.ll;res.ro.r;res.sumsumo.sum;returnres;}}tr[N2];voidpushup(intu){tr[u]tr[ls]tr[rs];}voidbuild(intu,intl,intr){tr[u]{l,r,0,0};if(lr)return;intmid(lr)1;build(ls,l,mid);build(rs,mid1,r);pushup(u);}voidmodify(intu,intidx,pii val){if(tr[u].ltr[u].r){tr[u].sumval.fi;tr[u].mxval.fival.se;return;}else{intmid(tr[u].ltr[u].r)1;if(mididx)modify(ls,idx,val);elsemodify(rs,idx,val);pushup(u);}}Nodequery(intu,intl,intr){if(ltr[u].ltr[u].rr)returntr[u];intmid(tr[u].ltr[u].r)1;if(rmid)returnquery(ls,l,r);if(lmid)returnquery(rs,l,r);returnquery(ls,l,r)query(rs,l,r);}}t;voidsolve(){intn,q;cinnq;via(n1),b(n1);rep(i,1,n){cina[i];}vectorpiiall;rep(i,1,n){cinb[i];all.push_back({b[i],i});}viop(q1),idx(q1),val(q1);rep(i,1,q){cinop[i]idx[i]val[i];if(op[i]2)all.push_back({val[i],idx[i]});}sort(all.begin(),all.end(),[](piia,piib){returna.fib.fi;});all.erase(unique(all.begin(),all.end()),all.end());inttotall.size()10;viitop(n1);mappii,intmp;intcnt0;for(autop:all){mp[p]cnt;}t.build(1,1,tot);rep(i,1,n){itop[i]mp[{b[i],i}];t.modify(1,itop[i],{a[i],b[i]});}rep(i,1,q){intididx[i];if(op[i]1){a[id]val[i];t.modify(1,itop[id],{a[id],b[id]});}else{t.modify(1,itop[id],{0,0});b[id]val[i];itop[id]mp[{b[id],id}];t.modify(1,itop[id],{a[id],b[id]});}coutt.query(1,1,tot).mx\n;}}