[CC-ANUGCD]Maximum number, GCD condition

题目大意：

一个长度为\(n(n\le10^5)\)的数列\(A(A_i\le10^5)\)，\(m(m\le10^5)\)次询问，每次询问\(l\sim r\)中不与\(g\)互质的数中的最大数以及最大数的个数。

思路：

对于每个质数维护一棵线段树，记录区间内包含这个质数的数的和。询问时将\(g\)分解质因数，在线段树上寻找最大值。

统计个数时将所有数以数值为第一关键字、下标为第二关键字排序后二分即可。

源代码：

#include<cstdio>

#include<cctype>

#include<algorithm>

inline int getint() {

	register char ch;

	while(!isdigit(ch=getchar()));

	register int x=ch^'0';

	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

	return x;

}

const int N=1e5+1,P=9593;

int p[P];

bool vis[N];

std::pair<int,int> v[N];

inline void sieve() {

	for(register int i=2;i<N;i++) {

		if(!vis[i]) p[++p[0]]=i;

		for(register int j=1;j<=p[0]&&i*p[j]<N;j++) {

			vis[i*p[j]]=true;

			if(i%p[j]==0) break;

		}

	}

}

class SegmentTree {

	#define mid ((b+e)>>1)

	private:

		struct Node {

			int val;

			Node *left,*right;

			Node() {

				val=-1;

				left=right=NULL;

			}

		};

	public:

		Node *root;

		void modify(Node* &p,const int &b,const int &e,const int &x,const int &y) {

			if(!p) p=new Node();

			p->val=std::max(p->val,y);

			if(b==e) return;

			if(x<=mid) modify(p->left,b,mid,x,y);

			if(x>mid) modify(p->right,mid+1,e,x,y);

		}

		int query(const Node* const &p,const int &b,const int &e,const int &l,const int &r) const {

			if(!p) return -1;

			if(b==l&&e==r) return p->val;

			int ret=-1;

			if(l<=mid) ret=std::max(ret,query(p->left,b,mid,l,std::min(mid,r)));

			if(r>mid) ret=std::max(ret,query(p->right,mid+1,e,std::max(mid+1,l),r));

			return ret;

		}

	#undef mid

};

SegmentTree t[P];

int main() {

	sieve();

	const int n=getint(),m=getint();

	for(register int i=1,b;i<=n;i++) {

		v[i].first=b=getint();

		v[i].second=i;

		for(register int j=1;p[j]*p[j]<=b;j++) {

			if(b%p[j]!=0) continue;

			while(b%p[j]==0) b/=p[j];

			t[j].modify(t[j].root,1,n,i,v[i].first);

		}

		if(b!=1) {

			const int j=std::lower_bound(&p[1],&p[p[0]]+1,b)-p;

			t[j].modify(t[j].root,1,n,i,v[i].first);

		}

	}

	std::sort(&v[1],&v[n]+1);

	for(register int i=0;i<m;i++) {

		int g=getint();

		const int l=getint(),r=getint();

		int max=-1;

		for(register int i=1;p[i]*p[i]<=g;i++) {

			if(g%p[i]!=0) continue;

			while(g%p[i]==0) g/=p[i];

			max=std::max(max,t[i].query(t[i].root,1,n,l,r));

		}

		if(g!=1) {

			const int &i=std::lower_bound(&p[1],&p[p[0]]+1,g)-p;

			max=std::max(max,t[i].query(t[i].root,1,n,l,r));

		}

		const int cnt=std::upper_bound(&v[1],&v[n]+1,std::make_pair(max,r))-std::lower_bound(&v[1],&v[n]+1,std::make_pair(max,l));

		printf("%d %d\n",max,cnt?:-1);

	}

	return 0;

}

巴特西

[CC-ANUGCD]Maximum number, GCD condition

[CC-ANUGCD]Maximum number, GCD condition

题目大意：

思路：

源代码：

最新文章

热门文章