【CF 914D】 Bash and a Tough Math Puzzle

原題連結：http://codeforces.com/problemset/problem/914/D
這題我在比賽當中想到詢問O((logn)^2)的作法，雖然壓常數後過了，可是最後還是被system test卡掉QQ
不過在賽後重送一次一模一樣的code卻過了，不知道是不是伺服器負荷量問題...

原題的詢問可以視為，詢問區間內無法被x整除的數字是否超過1個。
則考慮一個gcd線段樹，query的時候在外面開一個「無法被整除數字」的計數器。
函式裡，只要有區間能被x整除就直接return，否則就持續往詢問的區間遞迴。
如果當前node是涵蓋在詢問區間裡的：
case 1: l==r(node的區間只代表一個數字)
　　因為能遞迴到這裡表示一定不能整除，計數器+1
case 2: otherwise
　　暴力往下遞迴

最後在函式的開頭補上，計數器>1就直接return。
可以觀察到，會暴力遞迴到底的次數頂多只有兩次，兩次後計數器會>1，其他的待跑函式會全部return，複雜度O(logn)

總複雜度O(N+Qlogn)(不含修改，修改約O(logn*logC)，但gcd的期望值和單點修改的常數都遠比預計的小，所以可以不用在意)

	#pragma GCC optimize ("Ofast")
	#include <stdio.h>
	#include <algorithm>
	using namespace std;
	int seg[2000004],n,place[500001],counts;
	void build(int l,int r,int rt)
	{
	if(l==r)
	{
	scanf("%d",&seg[rt]),place[l]=rt;
	return ;
	}
	int m=(l+r)>>1;
	build(l,m,rt<<1),build(m+1,r,rt<<1|1);
	seg[rt]=__gcd(seg[rt<<1],seg[rt<<1|1]);
	}
	void query(int L,int R,int l,int r,int rt,int x)
	{
	if(counts>1 || seg[rt]%x==0) return;
	int m=(l+r)>>1;
	if(L<=l && R>=r)
	{
	if(l==r) ++counts;
	else
	{
	if(L<=m) query(L,R,l,m,rt<<1,x);
	if(R>m) query(L,R,m+1,r,rt<<1|1,x);
	}
	}
	else
	{
	if(L<=m) query(L,R,l,m,rt<<1,x);
	if(R>m) query(L,R,m+1,r,rt<<1|1,x);
	}
	}
	int main()
	{
	int q,k,l,r,x,a,b,m;
	bool tmp;
	scanf("%d",&n);
	build(1,n,1);
	scanf("%d",&q);
	while(q--)
	{
	scanf("%d%d",&k,&l);
	if(k==1)
	{
	scanf("%d%d",&r,&x);
	counts=0,query(l,r,1,n,1,x);
	if(counts>1) puts("NO");
	else puts("YES");
	}
	else
	{
	scanf("%d",&x);
	for(seg[a=place[l]]=x;a>1;)
	a>>=1,seg[a]=__gcd(seg[a<<1],seg[a<<1|1]);
	}
	}
	}

view raw gistfile1.txt hosted with ❤ by GitHub