P2650 彈幕考察 題解

題目鏈接

本人博客

前言

做法1：樹狀數組

做法2：二分

以上兩個做法在本篇題解中均會涉及。

筆者一拿到這個題，就想到了用數據結構維護一個查詢區間內原區間的個數。再一看是明顯是離線查詢，故想到了樹狀數組。打完之后點開標簽，發現竟然有二分的標簽，于是看了題解，才恍然大悟，發現原來這個題原來可以這么簡單？！

有些人啊，就是學數據結構學傻了。
連差分都要用線段樹做。
—— XXXXXXX

做法1：樹狀數組

從后往前維護樹狀數組，統計答案。

注意到數據，發現沒有辦法維護如此之巨大的樹狀數組，怎么辦？

答案就是-離散化！

\(\color{red}{\text{注意：離散化后數組大小一定想好要開多大！}}\) 筆者就是這里被卡了 \(5\) 發。

代碼

#include<cstdio>
#include<iostream> 
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
#define int long long 
inline int Read(){
	int x=0,f=1;
	char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=x*10+c-48;c=getchar();}
	return x*f;
}
inline void Write(int x){
	if(x<0){x=-x;putchar('-');}
	if(x>9) Write(x/10);
	putchar(x%10+'0');
}
const int N=1e6+10;
int n,m,rr;
//rr：統計離散化后最右邊的數字
int li[N],totl=0;
int ans[N];
struct node{
	int l,r,id;
}a[N],q[N]; 
//a:原區間,q:查詢區間
bool cmp1(node A,node B){return A.r>B.r;}
bool cmp2(node A,node B){return A.l>B.l;}
//樹狀數組板子
int c[N*5];
int lowbit(int x){
	return x&(-x);
}
void change(int pos,int v){
	while(pos<=rr){
		c[pos]+=v;
		pos+=lowbit(pos);
	}
}
int query(int pos){
	int res=0;
	while(pos){
		res+=c[pos];
		pos-=lowbit(pos);
	}
	return res;
}
signed main(){
	n=Read();m=Read();
	for(int i=1;i<=n;i++){
		a[i].l=Read()+1,a[i].r=Read()+a[i].l;
		li[++totl]=a[i].l,li[++totl]=a[i].r;
	}
	for(int i=1;i<=m;i++){
		q[i].l=Read()+1,q[i].r=Read()+q[i].l;
		li[++totl]=q[i].l,li[++totl]=q[i].r;
		q[i].id=i;
	}
        //離散化
	sort(li+1,li+totl+1);
	int cnt=unique(li+1,li+totl+1)-(li+1);
	for(int i=1;i<=n;i++) {
		a[i].l=lower_bound(li+1,li+cnt+1,a[i].l)-li;
		a[i].r=lower_bound(li+1,li+cnt+1,a[i].r)-li;
		rr=max(rr,a[i].r);
	}
	for(int i=1;i<=m;i++){
		q[i].l=lower_bound(li+1,li+cnt+1,q[i].l)-li;
		q[i].r=lower_bound(li+1,li+cnt+1,q[i].r)-li;
		rr=max(rr,q[i].r);
	}
	sort(a+1,a+n+1,cmp1);
	sort(q+1,q+m+1,cmp2);
	int j=1;
	for(int i=1;i<=m;i++){
		while(a[j].r>q[i].l) {
			change(a[j].l,1);
			j++;
		}
		ans[q[i].id]=query(q[i].r-1);
	}
	for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);
	return 0; 
}

做法2：二分

考慮什么時候原區間對查詢區間有貢獻。

設原區間為 \([x,y]\)，查詢區間為 \([l,r]\)。

當 \(y < l\) 或者 \(x > r\) 的時候原區間不在查詢區間的覆蓋范圍內，此時無貢獻。如下圖。

所以只需要統計查詢區間右端點前原區間左端點的個數，減去查詢區間左端點前原區間右端點的個數。

代碼

#include<cstdio>
#include<iostream> 
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
#define int long long 
inline int Read(){
	int x=0,f=1;
	char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=x*10+c-48;c=getchar();}
	return x*f;
}
inline void Write(int x){
	if(x<0){x=-x;putchar('-');}
	if(x>9) Write(x/10);
	putchar(x%10+'0');
}
const int N=1e5+10;
int n,m,l[N],r[N];
signed main(){
	n=Read();m=Read();
	for(int i=1;i<=n;i++){
		l[i]=Read(),r[i]=Read()+l[i]-1;//注意這里是左閉右開
	}
	sort(l+1,l+n+1);
	sort(r+1,r+n+1);//二分需要滿足單調性
	for(int i=1;i<=m;i++){
		int x=Read(),y=Read()+x;
		int ans=lower_bound(l+1,l+n+1,y)-(l+1);
		ans-=lower_bound(r+1,r+n+1,x)-(r+1);
		printf("%lld\n",ans);
	}
	return 0; 
}