【HDU 4630】No Pain No Game

相关链接

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=4630
神犇题解:http://www.cnblogs.com/zhsl/p/3234099.html

吐槽

最开始写了一个复杂度玄学的莫队,然后被卡$T$了
然后又写了一个$O(n \log n \sqrt{n \log n})$的$KD-Tree$,然后又被卡$T$了

然后看了题解就给跪了,这™不是傻逼题吗?

解题报告

我们将询问按照左端点排序,然后降序处理
这样每一次询问就相当于问一个后缀的前缀

然后考虑新加入最左边一个数$a_i$对于答案的影响
显然我们可以枚举因数$v$,然后记$v$上一次出现的位置为$last_v$
那么右端点在$i \sim last_v$之间的询问都会计算到这个$\gcd$
于是我们用$BIT$维护一个前缀最值就可以了
时间复杂度:$O(n \log^2 n)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 50009;

int n,m,pos[N],arr[N],last[N],ans[N];
struct Query{
	int l,r,id;
	inline bool operator < (const Query &Q) const {
		return l < Q.l;
	}
}q[N];
vector<int> que[N];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

class Fenwick_Tree{
	#define lowbit(x) ((x)&-(x))
	int mx[N];
	public:
		inline void init() {
			memset(mx, 0, sizeof(mx));
		}
		inline void modify(int p, int v) {
			for (int i=p;i<=n;i+=lowbit(i)) {
				mx[i] = max(mx[i], v);
			}
		}
		inline int query(int p) {
			int ret = 1;
			for (int i=p;i;i-=lowbit(i)) {
				ret = max(ret, mx[i]);
			}
			return ret;
		}
}BIT;

int main() {
	for (int T=read();T;T--) {
		n = read();
		for (int i=1;i<=n;i++) {
			que[i].clear();
			arr[i] = read();
			pos[arr[i]] = i; 
		}
		for (int i=2;i<n;i++) {
			for (int j=i;j<=n;j+=i) {
				que[pos[j]].push_back(i);
			}
		} 
		m = read();
		for (int i=1,l,r;i<=m;i++) {
			q[i].l = read();
			q[i].r = read();
			q[i].id = i;
		}
		sort(q+1, q+1+m);
		BIT.init();
		memset(last,60,sizeof(last));
		for (int i=m,cur=n+1;i;i--) {
			while (cur > q[i].l) {
				--cur;
				for (int j=0;j<que[cur].size();j++) {
					int v = que[cur][j];
					if (last[v] <= n) {
						BIT.modify(last[v], v);
					}
					last[v] = cur;
				}
			}
			if (q[i].l == q[i].r) ans[q[i].id] = 0;
			else ans[q[i].id] = BIT.query(q[i].r);
		}
		for (int i=1;i<=m;i++) {
			printf("%d\n",ans[i]);
		}
	}
	return 0;
}

25 thoughts to “【HDU 4630】No Pain No Game”

  1. Thank you for another informative web site.
    Where else could I get that type of information written in such
    a perfect approach? I have a undertaking that I am just now working on, and I have been at the look out for such info.

  2. You actually make it appear so easy with your presentation but I find this
    topic to be really something which I feel I would by no means understand.

    It kind of feels too complicated and extremely huge for me.
    I am looking ahead to your subsequent submit,
    I will attempt to get the hang of it!

  3. Hello, i think that i saw you visited my blog
    so i came to “return the favor”.I’m trying to find things to enhance
    my site!I suppose its ok to use some of your ideas!!

  4. You really make it seem really easy along with your presentation but I to find this topic to
    be actually something which I feel I might by no means understand.
    It sort of feels too complicated and extremely large for me.
    I’m taking a look ahead to your subsequent publish, I’ll attempt to get the cling of it!

  5. Helpful information. Lucky me I found your web site by accident, and I am surprised why this coincidence didn’t came about in advance!
    I bookmarked it.

  6. Aw, this was an incredibly good post. Taking the time and actual effort to create a really good article… but what can I say… I hesitate a lot and never manage
    to get nearly anything done.

  7. Heya i’m for the first time here. I came across this board and I find It really useful & it helped me out a
    lot. I hope to give something back and help others like
    you helped me.

  8. Hey! This is my first visit to your blog! We are a team of
    volunteers and starting a new project in a community
    in the same niche. Your blog provided us
    valuable information to work on. You have done a extraordinary job!

  9. Hello, I think your website might be having browser compatibility issues.
    When I look at your blog site in Safari, it looks fine but when opening in Internet Explorer, it has some
    overlapping. I just wanted to give you a quick heads up!
    Other then that, fantastic blog!

  10. Neat blog! Is your theme custom made or did you download
    it from somewhere? A theme like yours with
    a few simple adjustements would really make
    my blog jump out. Please let me know where you got your theme.
    Cheers

  11. I love your blog.. very nice colors & theme. Did you create this website
    yourself or did you hire someone to do it for you?

    Plz respond as I’m looking to construct my own blog and would
    like to know where u got this from. thanks a lot

  12. I need to to thank you for this excellent read!!
    I definitely enjoyed every little bit of it. I have got
    you book-marked to look at new things you post…

  13. Does your blog have a contact page? I’m having problems locating it but, I’d like to shoot you an e-mail.

    I’ve got some recommendations for your blog you might be interested in hearing.
    Either way, great site and I look forward to seeing it expand over time.

Leave a Reply

Your email address will not be published. Required fields are marked *