[莫队算法] - cool's Blog
[莫队算法]
最近又看了一下莫队，发现我以前完全理解错了莫队算法。
莫队算法适用于无修（带修不会啊QAQ@lbn187）的区间询问且若已知[L,R]的答案能够以较快的速度求出[L-1,R],[L+1,R],[L,R-1],[L,R+1],那么就可以使用莫队。
莫队是将所有区间按照一定顺序排序，使得这个区间移动次数较少。
最优的方法就是曼哈顿距离的最小生成树。但写起来太麻烦。
用这种方法排序是比较优秀的：如果L1/blk=L2/blk，那么就按R排序，否则按L排序。
经典例题小Z的袜子（叫你每天代码抄抄）
[51nod1290]询问区间内多少对数差的绝对值<=k，k为全局给定。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define rep(i,a,b) for (int i = a;i <= b;i++)
#define N 50010
#define M 150010
#define ll long long
using namespace std;
struct zhl
{
int l,r,id;
zhl(){}
zhl(int L,int R,int ID):l(L), r(R), id(ID){}
}eg[N];
int l,r,n,k,q,pos[N],blk,len,gg[M],a[N],b[N],c[N],x,y;
ll Ans,ans[N];
int cmp(zhl x,zhl y)
{
return pos[x.l]^pos[y.l]?x.l < y.l:x.r < y.r;
}
int g[M];
void update(int x,int y)
{
for (;x <= len;x += x&-x)
g[x] += y;
}
int query(int x)
{
int y = 0;
for (;x;x -= x&-x)
y += g[x];
return y;
}
void solve()
{
l = r = 1, Ans = 0;
update(a[1],1);
rep(i,1,q)
{
int L = eg[i].l,R = eg[i].r;
for (;l < L;l++) update(a[l],-1),Ans -= query(c[l])-query(b[l]-1);
for (;l > L;update(a[l],1)) l--,Ans += query(c[l])-query(b[l]-1);
for (;r < R;update(a[r],1)) r++,Ans += query(c[r])-query(b[r]-1);
for (;r > R;r--) update(a[r],-1),Ans -= query(c[r])-query(b[r]-1);
ans[eg[i].id] = Ans;
}
}
int main()
{
scanf("%d%d%d",&n,&k,&q); blk = sqrt(n);
rep(i,1,n)
{
scanf("%d",&a[i]);
gg[++len] = a[i];
gg[++len] = a[i]+k;
gg[++len] = a[i]-k;
}
sort(gg+1,gg+len+1);
len = unique(gg+1,gg+len+1)-gg-1;
rep(i,1,n)
{
b[i] = lower_bound(gg+1,gg+len+1,a[i]-k)-gg;
c[i] = lower_bound(gg+1,gg+len+1,a[i]+k)-gg;
a[i] = lower_bound(gg+1,gg+len+1,a[i])-gg;
pos[i] = (i-1)/blk;
}
rep(i,1,q)
{
scanf("%d%d",&x,&y);
eg[i] = zhl(x+1,y+1,i);
}
sort(eg+1,eg+q+1,cmp);
solve();
rep(i,1,q) printf("%lld\n",ans[i]);
return 0;
}
[bzoj4540]求一段区间的所有子区间的最小值的和。
考虑加入一个数的贡献，令p为[L,R]的最小值。
那么（p-L+1）*a[p]是其中一部分的贡献，还有的贡献在[p+1,R]。
令sl[i]为1~i的答案，那么sl[R]-sl[p]就是[p+1,R]的答案。
为什么呢？因为p是最小值，也就是说[p+1,R]的所有值的sl都是以sl[p]为基础转移的。
还有一点，莫队的时候应该先增加区间，再减小区间，不然有可能会有L>R的情况，会biubiu。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#define rep(i,a,b) for (int i = a;i <= b;i++)
#define drep(i,a,b) for (int i = a;i >= b;i--)
#define ist insert
#define ers erase
#define clr(a,b) memset(a,b,sizeof a)
#define ll long long
#define inf 1000000000
#define zhl 1000000007
template<class T>void Swap(T &a,T &b){ T c = a;a = b;b = c; }
template<class T>T max(T& a,T& b){ return a<b?b:a; }
template<class T>T min(T& a,T& b){ return a>b?b:a; }
using namespace std;
#define N 100010
int L[N],R[N],stk[N],pos[N],pw[20],n,q,top,blk,Left,Right;
ll sl[N],sr[N],a[N],ans[N],now;
int lg[N],f[N][20];
struct xfy
{
int l,r,id;
}eg[N];
void checkmin(int& x,int y)
{
if (a[x] > a[y]) x = y;
}
int getmin(int x,int y)
{
if (x > y) Swap(x,y);
int l = lg[y-x+1],r1 = f[x][l],r2 = f[y-pw[l]+1][l];
return a[r1]<a[r2]?r1:r2;
}
void updatel(int l,int r,int ty)
{
int o = getmin(l,r);
ll res = a[o]*(r-o+1)+sr[l]-sr[o];
now += res*ty;
}
void updater(int l,int r,int ty)
{
int o = getmin(l,r);
ll res = a[o]*(o-l+1)+sl[r]-sl[o];
now += res*ty;
}
int cmp(xfy x,xfy y)
{
return pos[x.l] == pos[y.l]?x.r<y.r:x.l<y.l;
}
int main()
{
scanf("%d%d",&n,&q); blk = sqrt(n);
pw[0] = 1;
rep(i,1,18) pw[i] = pw[i-1]+pw[i-1];
rep(i,1,n) scanf("%lld",&a[i]);
rep(i,1,n)
{
for (;top&&a[stk[top]]>=a[i];R[stk[top--]]=i);
stk[++top] = i;
}
for (;top;R[stk[top--]]=n+1);
drep(i,n,1)
{
for (;top&&a[stk[top]]>a[i];L[stk[top--]]=i);
stk[++top] = i;
}
for (;top;L[stk[top--]]=0);
rep(i,1,n) sl[i] = sl[L[i]]+a[i]*(i-L[i]);
drep(i,n,1) sr[i] = sr[R[i]]+a[i]*(R[i]-i);
lg[0] = -1;
rep(i,1,n) lg[i] = lg[i>>1]+1,pos[i] = (i-1)/blk,f[i][0] = i;
rep(j,1,18)
{
rep(i,1,n)
{
f[i][j] = f[i][j-1];
if (i+pw[j-1] <= n) checkmin(f[i][j],f[i+pw[j-1]][j-1]);
}
}
rep(i,1,q) scanf("%d%d",&eg[i].l,&eg[i].r),eg[i].id = i;
sort(eg+1,eg+q+1,cmp);
Left = Right = 1;now = a[1];
rep(i,1,q)
{
int l = eg[i].l,r = eg[i].r;
for (;Right < r;Right++) updater(Left,Right+1,1);
for (;Left > l;Left--) updatel(Left-1,Right,1);
for (;Right > r;Right--) updater(Left,Right,-1);
for (;Left < l;Left++) updatel(Left,Right,-1);
ans[eg[i].id] = now;
}
rep(i,1,q) printf("%lld\n",ans[i]);
return 0;
}
2022年8月07日 15:10
The HPSEB Bill Payment, new connection and other grievances taken up through an online portal. There are various other sources, through which the payment of HPSEB electricity bill processed to ensure customers provide better opportunities. The payment gateway of electricity bills online makes it easy for consumers to ensure they don’t miss the due date and timely make payment of their dues to enjoy unbreakable electricity service. HPSEB online bill payment Himachal Pradesh State Electricity Board does undertake the electricity supply to the customer in the state. It is a state-owned department which is fully under control of the state electricity board and provides various services of electricity to every domestic and commercial purpose.
2025年3月07日 18:07
Nice post. I discover some thing much harder on various blogs everyday. Most commonly it is stimulating to read content off their writers and rehearse something at their store. I’d opt to use some using the content in my small weblog no matter whether you don’t mind. Natually I’ll offer you a link with your internet weblog. Thank you sharing. Binary Signals
2025年3月11日 15:44
Real informative and fantastic anatomical structure of subject material , now that’s user pleasant . http://www.5starsstocks.com/
2025年3月16日 00:18
There are incredibly plenty of details like that take into consideration. That is the fantastic specify raise up. I offer the thoughts above as general inspiration but clearly you can find questions such as the one you raise up where the most critical factor will probably be doing work in honest very good faith. I don?t know if guidelines have emerged about things like that, but More than likely that your particular job is clearly identified as a fair game. Both boys and girls notice the impact of a moment’s pleasure, for the rest of their lives. Binary Options
2025年3月21日 23:42
You should get involved in a contest for example of the most useful blogs on-line. Let me recommend this page! heads or tails
2025年3月24日 22:17
Hello! I just now wish to provide a huge thumbs up for the great information you could have here during this post. We are coming back to your website for further soon. 바카라 사이트
2025年3月28日 14:24
Thank you for your own hard work on this website. Ellie enjoys conducting investigation and it is obvious why. All of us learn all of the compelling mode you produce simple tricks through this blog and as well cause participation from other ones about this area of interest then our daughter is now starting to learn a lot of things. Take advantage of the rest of the new year. You have been conducting a very good job. binary options signals
2025年3月31日 20:08
My brother suggested I could like this weblog. He was totally suitable. This publish truly created my day. You cann’t imagine merely how much time I had spent for this info! Thanks! crypto bot
2025年4月20日 23:57
Thank you so much for giving my family an update on this issue on your web-site. Please realise that if a brand new post appears or if perhaps any adjustments occur to the current post, I would be interested in reading a lot more and focusing on how to make good use of those strategies you reveal. Thanks for your efforts and consideration of other people by making this web site available. افلام مترجمة
2025年4月25日 03:03
Aw, this was a very nice post. In concept I wish to put in writing like this moreover ?taking time and precise effort to make an excellent article?but what can I say?I procrastinate alot and certainly not appear to get one thing done. mobile trading platform
2025年5月26日 15:51
As I website owner I believe the articles here is really fantastic , thankyou for your efforts. binary options trading
2025年6月05日 01:02
You completed several nice points there. I did a search on the subject and found a good number of persons will consent with your blog. binary trading signals
2025年6月13日 23:57
we may always need to do some credit specially if we weant to invest on something” verhuisfirma antwerpen
========================
It is an extremely amazing powerful resource that you’re offering and you just provide it away cost-free!! I comparable to discovering websites ones comprehend the particular valuation on supplying you with a excellent learning resource for zero cost. We truly dearly loved examining this web site. Regards! YouTube MP3
===========================
I have seen similar about this expression. But it seems your’s is different and best. filmyzilla
2025年6月17日 21:09
It was a real pleasure getting to your site a short while ago. I came here this day hoping to find out something new. And I was not upset. Your ideas about new solutions on this subject were helpful and a good help to me. Thank you for making time to write out these things as well as sharing your thinking. Paul Feller
============================
I was just having a conversation over this I am glad I came across this it cleared some of the questions I had. binary option bots
2025年7月04日 02:15
Can I just now say such a relief to uncover a person that actually knows what theyre preaching about over the internet. You actually have learned to bring a worry to light and produce it important. More people need to look at this and can see this side with the story. I cant think youre less popular simply because you definitely provide the gift. trading system
2025年7月09日 17:28
Hi. Thank you for making this site . I m working on betting online niche and have found this site using search on bing . Will be sure to look more of your content.CLICK HERE best ranked private servers
2025年7月14日 04:29
We will provide deal reviews, deal coaching, and follow up to ensure you win the deals you can’t afford to lose. escort girls
2025年7月16日 03:25
Can I recently say what a relief to seek out someone who really knows what theyre discussing over the internet. You certainly learn how to bring a concern to light and produce it critical. The best way to ought to look at this and fully grasp this side from the story. I cant think youre less popular because you absolutely contain the gift. Signals for mobile trading
2025年7月24日 17:22
Some really choice content on this internet site . Texas easy divorce
=============================
There is noticeably a lot of money to understand about this. I suppose you made particular nice points in functions also. 300 Gallon Mixing Tank
2025年8月01日 23:59
That is the proper weblog for anyone who desires to search out out about this topic. You realize so much its nearly exhausting to argue with you (not that I truly would need…HaHa). You positively put a brand new spin on a topic thats been written about for years. Nice stuff, simply great! how to trade binary options
2025年8月25日 02:11
Well done! I thank you your contribution to this matter. It has been useful. my blog: binary options trading
2025年9月07日 00:11
Intimately, the post is actually the sweetest on that worthw hile topic. I harmonise with your conclusions and also will certainly eagerly look forward to your incoming updates. Saying thanks will certainly not simply be enough, for the extraordinary clarity in your writing. I can perfect away grab your rss feed to stay informed of any kind of updates. Solid work and also much success in your business dealings! binary options
2025年9月28日 20:32
Hi. Thank you for making this site . I m working on betting online niche and have found this site using search on bing . Will be sure to look more of your content.CLICK HERE binary trading
2025年10月29日 16:14
Brilliant post and useful information. I think this is what I read somewhere but I dont know with your experience Artículos sobre la regulación cripto
2025年11月24日 01:55
I am extremely a new comer to the web and necessary to review this subject. Thought it absolutely was a great article perfectly written and helpful. I’ll definitely be time for your internet site to read more articles as i loved that one.. toiture pas chère hauts de seine
2026年3月26日 15:39
This can be neat article along with i quite like you just read this specific article. your blog can be amazing so you get very good staff members as part of your web site. wonderful expressing continue. North Carolina
2026年3月28日 01:37
Many thanks with regard to supplying current improvements concerning the issue, We anticipate study much more. omar afra free press
This can be a excellent ideas particularly in order to individuals a new comer to blogosphere, short as well as precise information… Many thanks with regard to discussing that one. Essential study post. Jonathan s bean news
That i taken aback when using the exploration everyone intended to get this to selected present astounding. Terrific process! las vegas longevity medicine
This can be quite a wonderful recommendations primarily so that you can dozens of a newcomer to blogosphere, limited plus genuine information… With thanks to obtain spreading brussels. Extremely important learn posting. omar afra events houston
2026年4月06日 19:40
Thanks for every other informative site. The place else may just I get that kind of information written in such an ideal means? I have a venture that I’m just now operating on, and I have been on the look out for such information. Watch This Before You Buy PuroAir 400
2026年4月19日 23:56
Wow! Such an amazing and helpful post this is. I really really love it. It's so good and so awesome. I'm just amazed. I am hoping that you continue to complete work such as this as time goes on also Longevity treatments Las Vegas Nevada
===========================================
Thanks because you have been willing to talk about information with us. we will always appreciate all you have done here because I understand you are very focused on our. Stem cell therapy Las Vegas
===========================================
Thank you so much for such a well-written article. It’s full of insightful information. Your point of view is the best among many without fail.For certain, It is one of the best blogs in my opinion. Anti-aging clinic Las Vegas NV
2026年5月17日 19:53
Now i'm enthusiastic any placed. It is actually great to see a lot of people verbalize from the character not forgetting capacity about in which essential matter location are often perfectly identified. what makes john spencer ellis an expert in business transformation
2026年6月10日 16:39
Usually I do not learn post on blogs, but I would like to say that this write-up very forced me to check out and do so! Your writing style has been amazed me. Thank you, quite nice article. Brinztech