相关链接
题目传送门: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; }
楼下是疯子。哈哈
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.
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!
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!!
Good article. I will be facing some of these issues
as well..
Greetings! Very helpful advice in this particular post!
It is the little changes which will make the greatest changes.
Thanks for sharing!
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!
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.
I enjoy what you guys tend to be up too. This sort of clever work and reporting!
Keep up the terrific works guys I’ve added you guys to my own blogroll.
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.
If you are going for finest contents like I do, just pay a quick visit this web page every day since it presents
quality contents, thanks
What’s up, after reading this remarkable article i am as well happy to share my familiarity here with friends.
Ahaa, its pleasant dialogue concerning this article at this place at this weblog, I
have read all that, so at this time me also commenting
here.
You are my intake, I have few web logs and occasionally run out from to post .
You ought to be a part of a contest for one of the highest quality sites online.
I most certainly will recommend this blog!
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.
Hi there, You’ve done a fantastic job. I’ll definitely
digg it and personally recommend to my friends. I am sure
they will be benefited from this website.
These are in fact impressive ideas in on the topic of blogging.
You have touched some pleasant points here. Any way keep up wrinting.
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!
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!
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
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
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…
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.
wonderful points altogether, you just gained a new reader. What might you suggest about your publish that you made a few days in the past? Any certain?