题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6521
题目大意
给定n和m个操作,
n代表序列长度,
每个操作给定一个区间,
代表把这个区间的人聚到一起,
其区间效率是这个区间中多少对人没有在之前的区间中
已经聚过.
题目分析
线段树+思维转化,
我们可以对每个人,维护一个
数组代表其最远认识到右边的哪一个人,
比如如果区间1,4操作后,那么1最远可以认识到4,
考虑到相互性,我们只需要对每个人维护一端即可.
初始化每个人对应的就是他自己的位置.
更新不难,但查询有点困难,对于区间中数组值
大于右端点的,没有贡献,而在右端点之内的,产生与右端点之差的贡献,
我们无法通过普通的区间求和去表示这一关系.
考虑其数组值的单调性,不难发现我们定义的数组值始终是不减的,
那么我们就可以二分出最大的权重小于右端点的位置点,
有了这个点后就可以进行传统的区间更新了,
我们维护最大值和一个区间和,
注意懒惰标记的更新不是直接赋值而是直接取max,越大越好,
其他一些细节就是数据范围的问题了.
#include<bits/stdc++.h>
using namespace std;#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define ll long long#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define root l,r,rt
#define mst(a,b) memset((a),(b),sizeof(a))
#define pii pair<int,int>
#define fi first
#define se second
#define mk(x,y) make_pair(x,y)
const int mod=1e9+7;
const int maxn=5e5+10;
const int ub=1e6;
const int INF=-1e9;
ll powmod(ll x,ll y){ll t; for(t=1;y;y>>=1,x=x*x%mod) if(y&1) t=t*x%mod; return t;}
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
/*
题目大意:
给定n和m个操作,
n代表序列长度,
每个操作给定一个区间,
代表把这个区间的人聚到一起,
其区间效率是这个区间中多少对人没有在之前的区间中
已经聚过.题目分析:
线段树+思维转化,
我们可以对每个人,维护一个
数组代表其最远认识到右边的哪一个人,
比如如果区间1,4操作后,那么1最远可以认识到4,
考虑到相互性,我们只需要对每个人维护一端即可.
初始化每个人对应的就是他自己的位置.
更新不难,但查询有点困难,对于区间中数组值
大于右端点的,没有贡献,而在右端点之内的,产生与右端点之差的贡献,
我们无法通过普通的区间求和去表示这一关系.
考虑其数组值的单调性,不难发现我们定义的数组值始终是不减的,
那么我们就可以二分出最大的权重小于右端点的位置点,
有了这个点后就可以进行传统的区间更新了,
我们维护最大值和一个区间和,
注意懒惰标记的更新不是直接赋值而是直接取max,越大越好,
其他一些细节就是数据范围的问题了.
*/
int rt[maxn],minv[maxn<<2],x,y;
int maxv[maxn<<2],lazy[maxn<<2];
ll sum[maxn<<2];
void build(lrt){lazy[rt]=0;if(l==r){sum[rt]=maxv[rt]=l;return ;}int mid=l+r>>1;build(lson),build(rson);maxv[rt]=max(maxv[rt<<1],maxv[rt<<1|1]);sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void pushdown(lrt){int mid=l+r>>1;if(lazy[rt]){lazy[rt<<1]=max(lazy[rt<<1],lazy[rt]);lazy[rt<<1|1]=max(lazy[rt<<1|1],lazy[rt]);maxv[rt<<1]=max(maxv[rt<<1],lazy[rt]);maxv[rt<<1|1]=max(maxv[rt<<1|1],lazy[rt]);sum[rt<<1]=1LL*(mid-l+1)*maxv[rt<<1];sum[rt<<1|1]=1LL*(r-mid)*maxv[rt<<1|1];lazy[rt]=0;}
}
int getpos(lrt,int p){pushdown(root);if(l==r) return maxv[rt];int mid=l+r>>1;if(p<=mid) return getpos(lson,p);else return getpos(rson,p);
}
void update(lrt,int L,int R,int v){if(L<=l&&r<=R){maxv[rt]=max(maxv[rt],v);sum[rt]=1LL*(r-l+1)*maxv[rt];lazy[rt]=max(lazy[rt],v);return;}pushdown(l,r,rt);int mid=l+r>>1;if(L<=mid) update(lson,L,R,v);if(mid<R) update(rson,L,R,v);maxv[rt]=max(maxv[rt<<1],maxv[rt<<1|1]);sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}ll getsum(lrt,int L,int R){if(L<=l&&r<=R) return sum[rt];pushdown(l,r,rt);int mid=l+r>>1;ll ans=0;if(L<=mid) ans+=getsum(lson,L,R);if(mid<R) ans+=getsum(rson,L,R);maxv[rt]=max(maxv[rt<<1],maxv[rt<<1|1]);sum[rt]=sum[rt<<1]+sum[rt<<1|1];return ans;
}
int n,m;
int main(){while(scanf("%d%d",&n,&m)!=EOF){build(1,n,1);rep(i,0,m){scanf("%d%d",&x,&y);int l=1,r=n,p=0;while(l<=r){int mid=l+r>>1;if(getpos(1,n,1,mid)<y){p=mid;l=mid+1;}else{r=mid-1;}}p=min(p,y);if(x<=p){printf("%lld\n",1LL*(p-x+1)*y-getsum(1,n,1,x,p));update(1,n,1,x,p,y);}else{puts("0");}}}return 0;
}