首页 > 代码库 > xdu_1009: Josephus环的复仇(线段树)
xdu_1009: Josephus环的复仇(线段树)
题目链接
题意不难理解,解法具体看代码及注释吧。。
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int maxn=2e5+7; int n,k; int ql,qr; int pos; //当前要出队的人在剩余人中排在第几靠左的地方 struct node { int l,r; int pre; //记录区间中剩余的最靠右的人在所有剩余人中的位置 int lz; //lazy标记 } a[maxn<<2]; void push_up(int rt) { a[rt].pre=max(a[rt<<1].pre,a[rt<<1|1].pre); } void build(int rt,int l,int r) { a[rt].l=l,a[rt].r=r; if(l==r) { a[rt].pre=l; return ; } int mid=(l+r)>>1; build(rt<<1,l,mid); build(rt<<1|1,mid+1,r); push_up(rt); } void update(int rt) { int l=a[rt].l,r=a[rt].r; if(ql<=l&&r<=qr) { --a[rt].pre; --a[rt].lz; return ; } int mid=(l+r)>>1; if(ql<=mid) update(rt<<1); if(qr>mid) update(rt<<1|1); push_up(rt); } void push_down(int rt) { int& lz=a[rt].lz; if(lz==0) return ; a[rt<<1].lz+=lz; a[rt<<1|1].lz+=lz; a[rt<<1].pre+=lz; a[rt<<1|1].pre+=lz; lz=0; } int query(int rt) { int l=a[rt].l,r=a[rt].r; if(l==r) return l; push_down(rt); int mid=(l+r)>>1; if(a[rt<<1].pre>=pos) return query(rt<<1); else return query(rt<<1|1); } int main() { scanf("%d%d",&n,&k); build(1,1,n); int cnt=n; pos=1; for(int i=0;i<n;i++) { pos=(pos-2+k+cnt*2)%cnt+1; //当前位置变更 --cnt; //少了个人 int p=query(1); //出队人在原队伍中的位置 printf("%d%c",p,i==n-1? ‘\n‘:‘ ‘); ql=p,qr=n; //出队后,pre发生变化的区间范围 update(1); } }
xdu_1009: Josephus环的复仇(线段树)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。