[C++知识库][复习]杜教筛

杜教筛的推导过程懒得写了，反正是复习，记个结论吧。

对于我们要筛的积性函数 $f$ ，构造一个函数 $g$，记 $f?g=h$。

我们的目标是求 $f$ 前缀和 $s$。

那么有

$$g(1)s(n)=\sum _{i=1}^{n}h(i)?\sum _{i=2}^{n}g(i)s(?\frac{n}{i}?)$$

睿智的发文助手再次表示我太短了。那就写点常见函数如何构造 $g$ 吧。

$\mu (i)$：构造 $I(i)$，$f?I=e$，前缀和显然非常好求。

$\mu (i)i$：构造 $id(i)$，卷积结果是 $n{\sum }_{d|n}\mu (d)$，后面部分不就是莫反吗，前缀和非常好求。

$\mu (i)i^2$：构造 $id(i)$，卷积结果是 $n^2{\sum }_{d|n}\mu (d)$，后面部分不就是莫反吗，前缀和非常好求。

$?(i)$：构造 $I$，$??I=id$，前缀和非常好求。

睿智的发文助手再次表示我太短了，单调栈镇楼：

#include<bits/stdc++.h>
using namespace std;
int n,q;
const int maxn=2e6+5;
int S[maxn],tp;
int id[maxn];
int a[maxn],b[maxn];
static char buf[1000000],*p1=buf,*p2=buf,obuf[1000000],*p3=obuf;
#define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++
#define putchar(x) (p3-obuf<1000000)?(*p3++=x):(fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=x)
template<typename item>
inline void read(register item &x)
{
    x=0;register char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
static char cc[10000];
template<typename item>
inline void print(register item x)
{ 
	register long long len=0;
	while(x)cc[len++]=x%10+'0',x/=10;
	while(len--)putchar(cc[len]);
}
struct pt{
	int x,y;
}p[maxn];
int t2=1;
int data[2];
struct BIT{
	int C[maxn];
	#define lowbit(i) i&(-i)
	void add(int x,int k){
		x++;
		while(x<=data[t2]){
			C[x]+=k;
			x+=lowbit(x);	
		}
	}
	int sum(int x){
		x++;
		int ans=0;
		while(x){
			ans+=C[x];
			x-=lowbit(x);
		}
		return ans;
	}
}T;
int ans[maxn];
struct query{
	int x,y,id,k;
}qr[maxn];
bool cmpq(query a,query b){ 
	if(a.y==b.y)return a.x<b.x;
	return a.y<b.y;
}
int qc=0;
int l[maxn],r[maxn];
bool cmp(pt a,pt b){
	if(a.y==b.y)return a.x<b.x;
	return a.y<b.y;
}
int main(){
//	freopen("stack.in","r",stdin);
//	freopen("stack.out","w",stdout);
	read(n);
	read(q);
	for(int i=1;i<=n;i++)read(a[i]);
	for(int i=1;i<=n;i++)read(b[i]);
	data[1]=n+1;
	tp=0;
	for(int i=1;i<=n;i++){
		while(tp&&(a[S[tp]]==a[i]||b[S[tp]]<=b[i]))tp--;
		id[i]=S[tp];
		S[++tp]=i;
		p[i]=(pt){i,id[i]};
//		cout<<i<<" "<<id[i]<<endl;
	}
	for(int i=1;i<=q;i++){ 
		read(l[i]); 
		read(r[i]);
		qr[++qc]=(query){r[i],r[i],i,1};
		qr[++qc]=(query){l[i]-1,l[i]-1,i,1};
		qr[++qc]=(query){l[i]-1,r[i],i,-1};
		qr[++qc]=(query){r[i],l[i]-1,i,-1};
	}
	sort(qr+1,qr+qc+1,cmpq);
	sort(p+1,p+n+1,cmp);
	int now=1;
	for(int i=1;i<=qc;i++){
//		cout<<qr[i].x<<" "<<qr[i].y<<endl;
		while((p[now].y<qr[i].y||(p[now].y==qr[i].y&&p[now].x<=qr[i].x))&&now<=n)T.add(p[now].x,1),now++;
		ans[qr[i].id]+=qr[i].k*T.sum(qr[i].x); 
//		cout<<T.sum(qr[i ].x)<<"!"<<endl;
	}
	for(int i=1;i<=q;i++){
		int res=r[i]-l[i]+1-ans[i];
		if(res)print(res);
		else putchar('0'); 
		putchar('\n');
	}
	fwrite(obuf,p3-obuf,1,stdout);
	return 0;
}