题目链接 "
- K - Party https://vjudge.net/problem/HDU-6521
- HDU - 6521"
题目大意: n 个人排成一列, 一开始他们互不认识, 每次选 [l,r] 上的人开 party, 使他们互相认识, 求出每次 party 之后新互相认识的人的对数.
具体思路: 一个人, 认识的人是连续的, 所以我们维护一个人的最远能到达的 R. 所以每一段区间我们维护这个区间能到的最短的距离.
AC 代码:
- #include<iostream>
- #include<stdio.h>
- #include<cmath>
- #include<string>
- #include<algorithm>
- using namespace std;
- # define ll long long
- # define inf 0x3f3f3f3f
- # define lson l,mid,rt<<1
- # define rson mid+1,r,rt<<1|1
- const int maxn = 2e6+100;
- const int mod = 1e9;
- int tree[maxn];
- void up(int rt)
- {
- tree[rt]=min(tree[rt<<1],tree[rt<<1|1]);
- }
- void buildtree(int l,int r,int rt)
- {
- tree[rt]=0;
- if(l==r)
- {
- tree[rt]=l;
- return ;
- }
- int mid=l+r>>1;
- buildtree(lson);
- buildtree(rson);
- up(rt);
- }
- int ans;
- void update(int l,int r,int rt,int L,int R)
- {
- if(R<l||L>r||tree[rt]>R)
- return ;
- if(l==r)
- {
- ans+=(R-tree[rt]);
- tree[rt]=R;
- return ;
- }
- int mid=l+r>>1;
- update(lson,L,R);
- update(rson,L,R);
- up(rt);
- }
- int main()
- {
- int n,m;
- while(~scanf("%d %d",&n,&m))
- {
- int st,ed;
- buildtree(1,n,1);
- for(int i=1; i<=m; i++)
- {
- scanf("%d %d",&st,&ed);
- ans=0;
- update(1,n,1,st,ed);
- printf("%d\n",ans);
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3043155.html