欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Jzoj4747 被粉碎的线段树

程序员文章站 2024-02-11 13:19:28
...

Jzoj4747 被粉碎的线段树

额这个题么

有一个很关键的点:结点个数依然为2N-1(证明可以看sam的讲稿)

不难发现以下性质:区间定位个数+区间所覆盖的节点个数=2*区间长度

所以问题变为,一个区间覆盖了多少个节点?

我们可以求出所有的节点,然后这个问题就是一个二维偏序计数问题了

具体用离线+按照r排序套上树状数组即可

#include<stdio.h>
#include<algorithm>
using namespace std;
inline int c(int x){ return x&-x; }
struct E{ int l,r,k,a; } s[100010];
struct P{ int l,r; } w[200010];
inline bool c1(P a,P b){ return a.r<b.r; }
inline bool c2(E a,E b){ return a.r<b.r; }
inline bool c3(E a,E b){ return a.k<b.k; }
int n,m,t=0,b[100010];
inline void add(int x){ for(;x<=n;x+=c(x)) b[x]++; }
inline int sum(int x,int k=0){ for(;x;x^=c(x)) k+=b[x]; return k; }
void build(int l,int r){
	w[t++]=(P){l,r};
	if(l==r) return;
	int m; scanf("%d",&m);
	build(l,m); build(m+1,r);
}
int main(){
	scanf("%d%d",&n,&m);
	build(1,n);
	sort(w,w+t,c1);
	for(int i=0;i<m;s[i].k=i,++i)
		scanf("%d%d",&s[i].l,&s[i].r);
	sort(s,s+m,c2);
	for(int i=0,j=0;i<m;){
		for(add(w[j++].l);w[j].r==w[j-1].r;add(w[j++].l));
		for(;s[i].r==w[j-1].r;++i) s[i].a=sum(s[i].r)-sum(s[i].l-1);
	}
	sort(s,s+m,c3);
	for(int i=0;i<m;++i) printf("%d\n",(s[i].r-s[i].l+1)*2-s[i].a);
}