題目傳送門

題目大意

給定 \(n\) 個方程，\(Q\) 次詢問，每次詢問區間 \([l,r]\) 中有多少個數是這 \(n\)

解題思路

算法：離散化 + 前綴和（離線算法）。

前置算法模板：離散化、前綴和。

看到區間首先想到將這 \(n\) 個方程的解標記起來（一個數是方程的解則標記為 \(1\)，否則為 \(0\)），求這個標記數組的區間和，那麼我們可以維護這個數組的前綴和來求解。

但是，且慢！！！

\(1\le |a|,|b|,|c|\le 10^9\)

那麼方程的解就是 \(10^9\)

那麼開 map？

要求前綴和顯然也不現實。

於是我看到了：

\(1\le n,Q\le 2\times 10^5\)

那麼總共在解和詢問中出現的數不會超過 \(6\times 10^5\) 個，可以將他們根據大小映射到 \(1\sim 6\times 10^5\)

代碼用的 STL 版本的離散化，比較通俗易懂。

這裏方程的輸入可以用快讀來避免進行字符串的掃描（因為快讀只會讀數字）。

AC Code

#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 600005
#define int long long
using namespace std;
int n,q,cnt;
int bok[N],sum[N],l[N],r[N],x[N];
int re()//樸素的快讀 
{
	int x=0,p=1;
	char y=getchar();
	for(;y>'9'||y<'0';y=getchar())
		if(y=='-')
			p=-p;
	for(;y>='0'&&y<='9';y=getchar())
		x=x*10+y-'0';
	return x*p;
}
void wr(int x)//樸素的快寫 
{
	if(x<0)
		putchar('-'),x=-x;
	if(x>9)
		wr(x/10);
	putchar(x%10+'0');
}
signed main()
{
	n=re(),q=re();
	for(int i=1;i<=n;i++)
	{
		int a=re(),b=re(),c=re();
		x[i]=(c-b)/a,bok[++cnt]=x[i];//將這個方程解出來，放到待離散化的數組bok中 
	}
	for(int i=1;i<=q;i++)
	{
		l[i]=re(),r[i]=re();
		bok[++cnt]=l[i];
		bok[++cnt]=r[i];//將詢問中的l和r放到待離散化的數組中 
	}
	sort(bok+1,bok+cnt+1);//排序 
	int boks=unique(bok+1,bok+cnt+1)-bok-1;//去重 
	for(int i=1;i<=n;i++)
		x[i]=lower_bound(bok+1,bok+boks+1,x[i])-bok,sum[x[i]]=1;//映射到x數組中並進行標記 
	for(int i=1;i<=q;i++)
		l[i]=lower_bound(bok+1,bok+boks+1,l[i])-bok,
		r[i]=lower_bound(bok+1,bok+boks+1,r[i])-bok;//映射到l和r數組中 
	for(int i=1;i<=boks;i++)
		sum[i]+=sum[i-1];//前綴和 
	for(int i=1;i<=q;i++)
		wr(sum[r[i]]-sum[l[i]-1]),putchar('\n');//樸素的前綴和求區間和 
	return 0;
}