2020-2021:teams:legal_string:jxm2001:整体二分
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:整体二分 [2020/07/30 16:28] jxm2001 |
2020-2021:teams:legal_string:jxm2001:整体二分 [2020/07/30 18:48] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 203: | 行 203: | ||
| _rep(i,1,m) | _rep(i,1,m) | ||
| enter(ans[i]); | enter(ans[i]); | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | ==== 习题二 ==== | ||
| + | |||
| + | [[https://www.luogu.com.cn/problem/P3527|洛谷p3527]] | ||
| + | |||
| + | === 题意 === | ||
| + | |||
| + | 给定一个长度为 $m$ 的环，每个节点有一个所属国家。$k$ 次事件，每次对 $[l,r]$ 顺时针环形区间上的每个点点权加上一个值。 | ||
| + | |||
| + | 每个国家有一个期望值 $p_i$，求每个国家最早多少次操作之后属于该国家的所有点的点权和能不小于 $p_i$。 | ||
| + | |||
| + | === 题解 === | ||
| + | |||
| + | 首先把考虑如何把环上修改转化成线段修改，发现将每个 $[l,r](l\gt r)$ 事件拆成 $[l,m],[1,r]$ 事件即可。 | ||
| + | |||
| + | 接下来直接整体二分，计算贡献时差分 $+$ 树状数组维护区间修改 $+$ 单点查询操作，每个国家暴力查询属于他的点集的点权和。 | ||
| + | |||
| + | 发现每层修改时间复杂度 $O(m\log m)$，查询复杂度也是 $O(m\log m)$，共 $O(\log m)$ 层。 | ||
| + | |||
| + | 于是总时间复杂度 $O(m\log^2 m)$。事实上本题存在 $O(m\log m)$ 做法，有兴趣的可以自行思考。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXN=3e5+5,Inf=1e9; | ||
| + | struct Num{ | ||
| + | int l,r,v,t; | ||
| + | }a[MAXN<<1]; | ||
| + | vector<int> ch[MAXN]; | ||
| + | struct Query{ | ||
| + | int k,id; | ||
| + | }q[MAXN],q1[MAXN],q2[MAXN]; | ||
| + | int m,ans[MAXN]; | ||
| + | LL c[MAXN]; | ||
| + | #define lowbit(x) ((x)&(-x)) | ||
| + | void add(int lef,int rig,int v){ | ||
| + | int pos=lef; | ||
| + | while(pos<=m){ | ||
| + | c[pos]+=v; | ||
| + | pos+=lowbit(pos); | ||
| + | } | ||
| + | pos=rig+1; | ||
| + | while(pos<=m){ | ||
| + | c[pos]-=v; | ||
| + | pos+=lowbit(pos); | ||
| + | } | ||
| + | } | ||
| + | LL query(int idx){ | ||
| + | LL ans=0; | ||
| + | _for(i,0,ch[idx].size()){ | ||
| + | int pos=ch[idx][i]; | ||
| + | while(pos){ | ||
| + | ans+=c[pos]; | ||
| + | pos-=lowbit(pos); | ||
| + | } | ||
| + | if(ans>Inf) | ||
| + | return ans; | ||
| + | } | ||
| + | return ans; | ||
| + | } | ||
| + | void solver(int ql,int qr,int vl,int vr){ | ||
| + | if(ql>qr)return; | ||
| + | int vm=vl+vr>>1; | ||
| + | if(vl==vr){ | ||
| + | _rep(i,ql,qr)ans[q[i].id]=a[vm].t; | ||
| + | return; | ||
| + | } | ||
| + | _rep(i,vl,vm)add(a[i].l,a[i].r,a[i].v); | ||
| + | int cnt1=0,cnt2=0,pos=ql; | ||
| + | _rep(i,ql,qr){ | ||
| + | LL r=query(q[i].id); | ||
| + | if(q[i].k<=r)q1[++cnt1]=q[i]; | ||
| + | else{ | ||
| + | q2[++cnt2]=q[i]; | ||
| + | q2[cnt2].k-=r; | ||
| + | } | ||
| + | } | ||
| + | _rep(i,vl,vm)add(a[i].l,a[i].r,-a[i].v); | ||
| + | _rep(i,1,cnt1)q[pos++]=q1[i]; | ||
| + | _rep(i,1,cnt2)q[pos++]=q2[i]; | ||
| + | solver(ql,qr-cnt2,vl,vm);solver(ql+cnt1,qr,vm+1,vr); | ||
| + | } | ||
| + | int main() | ||
| + | { | ||
| + | int n=read_int(),cnt=0,lef,rig,v; | ||
| + | m=read_int(); | ||
| + | _rep(i,1,m) | ||
| + | ch[read_int()].push_back(i); | ||
| + | _rep(i,1,n) | ||
| + | q[i]=Query{read_int(),i}; | ||
| + | int k=read_int(); | ||
| + | _rep(i,1,k){ | ||
| + | lef=read_int(),rig=read_int(),v=read_int(); | ||
| + | if(lef<=rig) | ||
| + | a[++cnt]=Num{lef,rig,v,i}; | ||
| + | else{ | ||
| + | a[++cnt]=Num{lef,m,v,i}; | ||
| + | a[++cnt]=Num{1,rig,v,i}; | ||
| + | } | ||
| + | } | ||
| + | solver(1,n,1,cnt+1); | ||
| + | _rep(i,1,n){ | ||
| + | if(!ans[i]) | ||
| + | puts("NIE"); | ||
| + | else | ||
| + | enter(ans[i]); | ||
| + | } | ||
| return 0; | return 0; | ||
| } | } | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
2020-2021/teams/legal_string/jxm2001/整体二分.1596097689.txt.gz · 最后更改: 2020/07/30 16:28 由 jxm2001
